Поиск точки перехода: различия между версиями
MagnusFit (обсуждение | вклад) Перевод из Английской Википедии |
(нет различий)
|
Версия от 10:33, 14 сентября 2021
В информатике Поиск точки перехода (ПТП) (англ. Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа[1], удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой, как это учитывает обычный A*[2].
Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его выполнения на порядок[1].
История
В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников[1]. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми).
Авторы представили изменённые правила обрезки для приложений, в которых обрезка углов запрещена в следующем году[3]. В этой статье также представлен алгоритм предварительной обработки сетки для минимизации времени поиска в Интернете.
В 2014 году авторы опубликовали ряд дополнительных оптимизаций[4]. Эти оптимизации включают изучение столбцов или строк узлов вместо отдельных узлов, предварительное вычисление переходов в сетке и более строгие правила отсечения.
Будущая работа
Хотя поиск точки перехода ограничен сетками с однородными затратами и агентами с однородным размером, в будущем авторы планируют использовать ПТП с существующими методами ускорения на основе сетки, такими как иерархические сетки[4][5].
Примечания
- ↑ 1 2 3 Даниэль Харабор, Альбан Грастиен (2011). Сокращение онлайн-графа для поиска пути на сеточных картах (PDF). 25-я Национальная конференция по искусственному интеллекту. AAAI.
- ↑ Натан Уитмер. Объяснение поиска точки перехода. zerowidth positive lookahead (5 мая 2013). Дата обращения: 9 марта 2014.
- ↑ Д. Харабор, А. Грастиен (2012). Система поиска пути JPS. 26-я Национальная конференция по искусственному интеллекту. AAAI.
- ↑ 1 2 Д. Харабор, А. Грастиен. Улучшение поиска точки перехода. Колледж инженерии и информатики Австралийского национального университета. Ассоциация развития искусственного интеллекта (www.aaai.org). Дата обращения: 11 июля 2015.
- ↑ Ади Ботеа, Мартин Мюллер. Поиск почти оптимального иерархического пути. University of Alberta. Альбертский университет (2004).