Поиск точки перехода

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

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

История

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

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

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

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

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

Примечания
  1. Даниэль Харабор, Альбан Грастиен (2011). «Сокращение онлайн-графа для поиска пути на сеточных картах» in 25-я Национальная конференция по искусственному интеллекту., AAAI.
  2. Натан Уитмер. Объяснение поиска точки перехода (недоступная ссылка). zerowidth positive lookahead (5 мая 2013 года). Дата обращения: 9 марта 2014. Архивировано 10 марта 2014 года.
  3. Д. Харабор, А. Грастиен (2012). «Система поиска пути JPS» in 26-я Национальная конференция по искусственному интеллекту., AAAI.
  4. Д. Харабор, А. Грастиен. Улучшение поиска точки перехода. Колледж инженерии и информатики Австралийского национального университета. Ассоциация развития искусственного интеллекта (www.aaai.org). Дата обращения: 11 июля 2015.
  5. Ади Ботеа, Мартин Мюллер. Поиск почти оптимального иерархического пути. University of Alberta. Альбертский университет (2004).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.