Поиск точки перехода

В информатике Поиск точки перехода (ПТП) (англ. Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа[1], удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой, как это учитывает обычный A*[2].

Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его выполнения на порядок[1].

История

В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников[1]. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми).

Авторы представили изменённые правила обрезки для приложений, в которых обрезка углов запрещена в следующем году[3]. В этой статье также представлен алгоритм предварительной обработки сетки для минимизации времени поиска в Интернете.

В 2014 году авторы опубликовали ряд дополнительных оптимизаций[4]. Эти оптимизации включают изучение столбцов или строк узлов вместо отдельных узлов, предварительное вычисление переходов в сетке и более строгие правила отсечения.

Будущая работа

Хотя поиск точки перехода ограничен сетками с однородными затратами и агентами с однородным размером, в будущем авторы планируют использовать ПТП с существующими методами ускорения на основе сетки, такими как иерархические сетки[4][5].

Примечания

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