Поиск точки перехода - Jump point search

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

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

История

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

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

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

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

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

использованная литература