Поиск точки перехода
В информатике Поиск точки перехода (ПТП) (англ. Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа<ref name="harabor2011">Шаблон:Cite conference</ref>, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой, как это учитывает обычный A*<ref>Шаблон:Cite web</ref>.
Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его выполнения на порядок<ref name="harabor2011"/>.
История
В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников<ref name="harabor2011"/>. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми).
Авторы представили изменённые правила обрезки для приложений, в которых обрезка углов запрещена в следующем году<ref name="harabor2012">Шаблон:Cite conference</ref>. В этой статье также представлен алгоритм предварительной обработки сетки для минимизации времени поиска в Интернете.
В 2014 году авторы опубликовали ряд дополнительных оптимизаций<ref name=Harabor2014>Шаблон:Cite web</ref>. Эти оптимизации включают изучение столбцов или строк узлов вместо отдельных узлов, предварительное вычисление переходов в сетке и более строгие правила отсечения.
Будущая работа
Хотя поиск точки перехода ограничен сетками с однородными затратами и агентами с однородным размером, в будущем авторы планируют использовать ПТП с существующими методами ускорения на основе сетки, такими как иерархические сетки<ref name=Harabor2014 /><ref name=Botea2004>Шаблон:Cite web</ref>.
Примечания
| {{#switch: {{{1}}}
| узкие = columns reflist-narrow
| широкие = columns reflist-wide
| #default = columns
}}
| {{#switch: {{{1}}}
| 1 =
| 2 | 3 = columns
| #default = columns reflist-narrow
}}
}}
| columns
}}
}}" style="{{#if:
| column-width:{{{colwidth}}};
| {{#if:
| {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
| {{#switch: {{{1}}}
| узкие | широкие =
| #default = column-width:{{{1}}};
}}
}}
}}
}} list-style-type: {{#switch:
| upper-alpha
| upper-roman
| lower-alpha
| lower-greek
| lower-roman = {{{group}}}
| #default = decimal
}};">
<references group="" responsive="{{#if:
| 0
| {{#if:
| {{#iferror: {{#expr: {{{1}}} > 1 }}
| {{#switch: {{{1}}}
| узкие | широкие = 1
| #default = 0
}}
| {{#switch: {{{1}}}
| 1 = 0
| #default = 1
}}
}}
| 1
}}
}}"></references>Ошибка скрипта: Модуля «Check for unknown parameters» не существует.
