Просмотр кода страницы Поиск точки перехода

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

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

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


----
[[Категория:Алгоритмы поиска]]