Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для использования в других целях, см Следопыт (значения) .
Алгоритмы поиска по графам и деревьям
Списки
  • Алгоритмы графа
  • Алгоритмы поиска
  • Список алгоритмов графа
похожие темы
  • Динамическое программирование
  • Обход графа
  • Обход дерева
  • Искать игры
  • Раскраска графика
  • v
  • т
  • е
Эквивалентные пути между A и B в 2D-среде

Первопрохождение или Pathing является построением, с помощью компьютерного приложения, кратчайшего маршрута между двумя точками. Это более практичный вариант решения лабиринтов . Эта область исследований в значительной степени основана на алгоритме Дейкстры для поиска кратчайшего пути на взвешенном графе .

Поиск пути тесно связан с проблемой кратчайшего пути в рамках теории графов , которая исследует, как определить путь, который лучше всего соответствует некоторым критериям (самый короткий, самый дешевый, самый быстрый и т. Д.) Между двумя точками в большой сети.

Алгоритмы [ править ]

По своей сути, метод поиска пути ищет граф , начиная с одной вершины и исследуя соседние узлы до тех пор, пока не будет достигнут целевой узел, обычно с намерением найти самый дешевый маршрут. Хотя методы поиска по графу, такие как поиск в ширину, могли бы найти маршрут, если бы им было уделено достаточно времени, другие методы, которые «исследуют» граф, будут стремиться достичь пункта назначения раньше. Можно провести аналогию с человеком, идущим по комнате; вместо того, чтобы заранее исследовать все возможные маршруты, человек обычно идет в направлении пункта назначения и отклоняется от пути только для того, чтобы избежать препятствия, и делает отклонения как можно более незначительными.

Две основные проблемы поиска пути: (1) найти путь между двумя узлами в графе ; и (2) задача о кратчайшем пути - найти оптимальный кратчайший путь . Базовые алгоритмы, такие как поиск в ширину и в глубину, решают первую проблему, исчерпывая все возможности; начиная с данного узла, они перебирают все возможные пути, пока не достигнут конечного узла. Эти алгоритмы работают за линейное время, где V - количество вершин, а E - количество ребер между вершинами.

Более сложная проблема - найти оптимальный путь. Исчерпывающий подход в этом случае известен как алгоритм Беллмана – Форда , который дает временную сложность или квадратичное время. Однако необязательно перебирать все возможные пути, чтобы найти оптимальный. Такие алгоритмы, как A * и алгоритм Дейкстры, стратегически исключают пути либо с помощью эвристики, либо с помощью динамического программирования . За счет исключения невозможных путей эти алгоритмы могут достичь временной сложности до . [1]

Вышеупомянутые алгоритмы являются одними из лучших общих алгоритмов, которые работают с графом без предварительной обработки. Однако в практических системах маршрутизации путешествий даже лучшие временные сложности могут быть достигнуты с помощью алгоритмов, которые могут предварительно обрабатывать график для достижения лучшей производительности. [2] Одним из таких алгоритмов является сжатие иерархий .

Алгоритм Дейкстры [ править ]

Типичным примером алгоритма поиска пути на основе графа является алгоритм Дейкстры . Этот алгоритм начинается с начального узла и «открытого набора» узлов-кандидатов. На каждом шаге исследуется узел в открытом множестве с наименьшим расстоянием от старта. Узел помечается как «закрытый», и все смежные с ним узлы добавляются в открытый набор, если они еще не были исследованы. Этот процесс повторяется до тех пор, пока не будет найден путь к месту назначения. Поскольку в первую очередь проверяются узлы с наименьшим расстоянием, при первом обнаружении пункта назначения путь к нему будет кратчайшим. [3]

Алгоритм Дейкстры не работает, если вес ребра отрицательный . В гипотетической ситуации, когда узлы A, B и C образуют связный неориентированный граф с ребрами AB = 3, AC = 4 и BC = −2, оптимальный путь от A до C стоит 1, а оптимальный путь от A до B стоит 2. Алгоритм Дейкстры, начиная с A, сначала исследует B, так как он является ближайшим. Он присвоит ему стоимость 3 и пометит его закрытым, что означает, что его стоимость никогда не будет переоценена. Следовательно, метод Дейкстры не может оценивать отрицательные веса ребер. Однако, поскольку для многих практических целей отрицательного веса ребра никогда не будет, алгоритм Дейкстры в значительной степени подходит для поиска пути.

A * алгоритм [ править ]

A * - это вариант алгоритма Дейкстры, обычно используемый в играх. A * назначает вес каждому открытому узлу, равный весу края этого узла плюс приблизительное расстояние между этим узлом и финишем. Это приблизительное расстояние определяется эвристикой и представляет собой минимально возможное расстояние между этим узлом и концом. Это позволяет исключить более длинные пути после того, как будет найден начальный путь. Если между началом и концом есть путь длиной x, а минимальное расстояние между узлом и концом больше x, этот узел не нужно исследовать. [4]

A * использует эту эвристику для улучшения поведения по сравнению с алгоритмом Дейкстры. Когда эвристика дает нулевое значение, A * эквивалентен алгоритму Дейкстры. По мере того, как эвристическая оценка увеличивается и приближается к истинному расстоянию, A * продолжает находить оптимальные пути, но работает быстрее (за счет проверки меньшего количества узлов). Когда значение эвристики точно соответствует истинному расстоянию, A * проверяет наименьшее количество узлов. (Однако, как правило, нецелесообразно писать эвристическую функцию, которая всегда вычисляет истинное расстояние, так как тот же результат сравнения часто можно получить с помощью более простых вычислений - например, используя расстояние Манхэттена над евклидовым расстоянием в двумерном пространстве..) По мере увеличения значения эвристики A * проверяет меньше узлов, но больше не гарантирует оптимальный путь. Во многих приложениях (например, в видеоиграх) это приемлемо и даже желательно, чтобы алгоритм работал быстро.

Пример алгоритма [ править ]

Это довольно простой и понятный алгоритм поиска пути для тайловых карт. Для начала у вас есть карта, координаты начала и координаты пункта назначения. Карта будет выглядеть так: X - стены, S - начало, O - конец, _ - открытые пространства, числа по верхнему и правому краям - номера столбца и строки:

 1 2 3 4 5 6 7 8XXXXXXXXXXХ _ _ _ ХХ _ Х _ Х 1Х _ Х _ _ Х _ _ _ Х 2XSXX _ _ _ X _ X 3X _ X _ _ X _ _ _ X 4Х _ _ _ ХХ _ Х _ Х 5X _ X _ _ X _ X _ X 6X _ XX _ _ _ X _ X 7X _ _ O _ X _ _ _ X 8XXXXXXXXXX

Сначала создайте список координат, который мы будем использовать в качестве очереди. Очередь будет инициализирована одной координатой, конечной координатой. К каждой координате также будет прикреплена переменная счетчика (цель этого скоро станет очевидной). Таким образом, очередь начинается как ((3,8,0)).

Затем просмотрите каждый элемент в очереди, включая новые элементы, добавленные в конец в ходе алгоритма, и для каждого элемента выполните следующие действия:

  1. Создайте список из четырех соседних ячеек с переменной счетчика переменной счетчика текущего элемента + 1 (в нашем примере четыре ячейки: ((2,8,1), (3,7,1), (4, 8,1), (3,9,1)))
  2. Проверьте все ячейки в каждом списке на следующие два условия:
    1. Если ячейка - стена, удалите ее из списка
    2. Если в основном списке есть элемент с такой же координатой, удалите его из списка ячеек.
  3. Добавить все оставшиеся ячейки списка в конец основного списка
  4. Перейти к следующему пункту в списке

Таким образом, после первого хода список элементов следующий: ((3,8,0), (2,8,1), (4,8,1))

  • После 2 ходов: ((3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2))
  • После 3 ходов: (... (1,7,3), (4,6,3), (5,7,3))
  • После 4 ходов: (... (1,6,4), (3,6,4), (6,7,4))
  • После 5 ходов: (... (1,5,5), (3,5,5), (6,6,5), (6,8,5))
  • После 6 ходов: (... (1,4,6), (2,5,6), (3,4,6), (6,5,6), (7,8,6))
  • После 7 ходов: (... (1,3,7)) - проблема решена, завершите этот этап алгоритма - обратите внимание, что если у вас есть несколько юнитов, преследующих одну и ту же цель (как во многих играх - подход от конца к началу алгоритм призван упростить это), вы можете продолжать, пока не будет занята вся карта, все юниты или достигнут установленный предел счетчика

Теперь сопоставьте счетчики на карте, получив следующее:

 1 2 3 4 5 6 7 8XXXXXXXXXXХ _ _ _ ХХ _ Х _ Х 1Х _ Х _ _ Х _ _ _ Х 2XSXX _ _ _ X _ X 3Х 6 Х 6 _ Х _ _ _ Х 4Х 5 6 5 Х Х 6 Х _ Х 5Х 4 Х 4 3 Х 5 Х _ Х 6Х 3 ХХ 2 3 4 Х _ Х 7Х 2 1 0 1 Х 5 6 _ Х 8XXXXXXXXXX

Теперь начните с S (7) и перейдите к ближайшей ячейке с наименьшим номером (непроверенные ячейки нельзя переместить). Прослеживаемый путь: (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8,0). В случае, если два числа одинаково малы (например, если S было в (2,5)), выберите случайное направление - длины одинаковы. Алгоритм завершен.

В видеоиграх [ править ]

Крис Кроуфорд в 1982 году описал, как он «потратил много времени», пытаясь решить проблему с поиском пути в Tanktics , когда компьютерные танки оказались в ловушке на суше в U-образных озерах. «После долгих усилий я нашел лучшее решение: удалить U-образные озера с карты», - сказал он. [5]

Иерархический поиск пути [ править ]

Кваддеревья можно использовать для поиска иерархических путей.

Идея была впервые описана индустрией видеоигр , у которой возникла потребность в планировании на больших картах с небольшим количеством процессорного времени . Концепция использования абстракции и эвристики старше и впервые была упомянута под названием ABSTRIPS (Abstraction-Based STRIPS ) [6], который использовался для эффективного поиска в пространствах состояний логических игр. [7] Похожая техника - это навигационные сетки (navmesh), которые используются для геометрического планирования в играх и планирования мультимодальных перевозок, которое используется в задачах коммивояжера с более чем одним транспортным средством.

Карта разделена на кластеры . На высокоуровневом слое планируется путь между кластерами. После того, как план был найден, планируется второй путь в кластере на нижнем уровне. [8] Это означает, что планирование выполняется в два этапа, которые представляют собой управляемый локальный поиск в исходном пространстве. Преимущество состоит в том, что количество узлов меньше, а алгоритм работает очень хорошо. Недостатком является сложность реализации иерархического планировщика путей. [9]

Пример [ править ]

Карта имеет размер 3000x2000 пикселей . Планирование пути на основе пикселей заняло бы очень много времени. Даже эффективный алгоритмпотребуется вычислить множество возможных графиков. Причина в том, что такая карта будет содержать в целом 6 миллионов пикселей, а возможности исследования геометрического пространства чрезвычайно велики. Первым шагом иерархического планировщика путей является разделение карты на более мелкие подкарты. Каждый кластер имеет размер 300x200 пикселей. Общее количество кластеров 10x10 = 100. Во вновь созданном графе количество узлов невелико, можно перемещаться между 100 кластерами, но не в рамках подробной карты. Если действительный путь был найден в высокоуровневом графе, следующим шагом будет планирование пути в каждом кластере. Подкарта имеет размер 300x200 пикселей, что легко может быть обработано обычным планировщиком путей A * .

Алгоритмы, используемые при поиске пути [ править ]

  • Алгоритм Дейкстры
  • Алгоритм поиска A * , частный случай алгоритма Дейкстры
  • D * семейство алгоритмов инкрементального эвристического поиска для задач, в которых ограничения меняются со временем или не полностью известны, когда агент впервые планирует свой путь
  • Алгоритмы планирования пути под любым углом , семейство алгоритмов для планирования путей, которые не ограничиваются движением по краям в графе поиска, разработанные, чтобы иметь возможность принимать любой угол и, таким образом, находить более короткие и прямые пути

Поиск пути с несколькими агентами [ править ]

Поиск пути с несколькими агентами заключается в поиске путей для нескольких агентов от их текущих местоположений до их целевых местоположений без столкновения друг с другом, при одновременной оптимизации функции затрат, например суммы длин путей всех агентов. Это обобщение поиска пути. Многие многоагентные алгоритмы поиска пути являются обобщением A * или сводятся к другим хорошо изученным задачам, таким как целочисленное линейное программирование. [10] Однако такие алгоритмы обычно неполны; другими словами, не доказано, что можно получить решение за полиномиальное время. Другая категория алгоритмов жертвует оптимальностью ради производительности, используя известные шаблоны навигации (например, поток трафика) или топологию проблемного пространства. [11]

См. Также [ править ]

  • Планирование движения
  • Планирование траектории под любым углом

Ссылки [ править ]

  1. ^ "7.2.1 Проблема кратчайшего пути от одного источника: алгоритм Дейкстры" . Архивировано из оригинала на 2016-03-04 . Проверено 18 мая 2012 .
  2. ^ Деллинг, D .; Сандерс, П .; Schultes, D .; Вагнер, Д. (2009). «Инженерные алгоритмы планирования маршрута». Алгоритмика больших и сложных сетей: проектирование, анализ и моделирование . Конспект лекций по информатике. 5515 . Springer. С. 117–139. CiteSeerX 10.1.1.164.8916 . DOI : 10.1007 / 978-3-642-02094-0_7 . ISBN  978-3-642-02093-3.
  3. ^ «5.7.1 Алгоритм Дейкстры» .
  4. ^ «Введение в A * Pathfinding» .
  5. ^ Кроуфорд, Крис (декабрь 1982). «Конструкторские приемы и идеи для компьютерных игр» . БАЙТ . п. 96 . Проверено 19 октября 2013 года .
  6. ^ Сакердоти, граф D (1974). «Планирование в иерархии пространств абстракции» (PDF) . Искусственный интеллект . 5 (2): 115–135. DOI : 10.1016 / 0004-3702 (74) 90026-5 .
  7. ^ Holte, Роберт C и Перес, MB и Zimmer, RM и Макдональд, AJ (1995). Иерархический a * . Симпозиум по абстракции, переформулировке и приближению.CS1 maint: несколько имен: список авторов ( ссылка )
  8. ^ Pelechano, Нурия и Fuentes, Carlos (2016). «Иерархический поиск путей для навигационных сеток (HNA⁎)» (PDF) . Компьютеры и графика . 59 : 68–78. DOI : 10.1016 / j.cag.2016.05.023 . hdl : 2117/98738 . CS1 maint: несколько имен: список авторов ( ссылка )
  9. ^ Botea, Ади и Мюллер, Мартин и Шеффер, Джонатан (2004). «Почти оптимальный иерархический поиск пути». Журнал разработки игр . 1 : 7–28. CiteSeerX 10.1.1.479.4675 . CS1 maint: несколько имен: список авторов ( ссылка )
  10. ↑ Ханг Ма, Свен Кениг, Нора Аянян, Лирон Коэн, Вольфганг Хёниг, Т.К. Сатиш Кумар, Тансель Урас, Хонг Сю, Крейг Тови и Гуни Шарон. Обзор: обобщение многоагентного поиска пути к реальным сценариям. На 25-й Международной совместной конференции по искусственному интеллекту (IJCAI), семинар по поиску путей с несколькими агентами. 2016 г.
  11. ^ Хоршид, Мохтар (2011). «Полиномиальный алгоритм для неоптимального поиска пути с несколькими агентами» . SOCS .

Внешние ссылки [ править ]

  • https://melikpehlivanov.github.io/AlgorithmVisualizer
  • http://sourceforge.net/projects/argorha
  • http://qiao.github.com/PathFinding.js/visual/
  • StraightEdge Open Source Java 2D поиск пути (с использованием A *) и проект освещения. Включает демонстрации апплетов.
  • python-pathfinding. Открытый исходный код Python для поиска двухмерных путей (с использованием алгоритма Дейкстры) и проект освещения.
  • Daedalus Lib с открытым исходным кодом. Daedalus Lib управляет полностью динамическим триангулированным моделированием 2D-среды и поиском пути с помощью алгоритмов A * и воронки.