Поиск точки перехода: различия между версиями
Patarakin (обсуждение | вклад) Нет описания правки |
Patarakin (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
В [[Информатика|информатике]] '''Поиск точки перехода''' ('''ПТП''') | В [[Информатика|информатике]] '''Поиск точки перехода''' ('''ПТП''') '''Jump point search''' ('''JPS''')) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные ''скачки'' по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой | ||
Поиск точки перехода сохраняет оптимальность '''A*''', потенциально сокращая время его выполнения на порядок. | Поиск точки перехода сохраняет оптимальность '''A*''', потенциально сокращая время его выполнения на порядок. | ||
== История == | == История == | ||
В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников | В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными [[агент]]ами (например, [[робототехника|робототехникой]]), либо [[симуляция]]ми (например, многими играми). | ||
---- | |||
[[Категория:Алгоритмы поиска]] | [[Категория:Алгоритмы поиска]] | ||
Текущая версия от 16:33, 1 декабря 2022
В информатике Поиск точки перехода (ПТП) Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой
Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его выполнения на порядок.
История
В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми).
