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

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

История

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

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

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

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

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

Примечания