|
|
| (не показаны 2 промежуточные версии этого же участника) |
| Строка 1: |
Строка 1: |
| В [[Информатика|информатике]] '''Поиск точки перехода''' ('''ПТП''') ([[Английский язык|англ.]] '''Jump point search''' ('''JPS''')) — это оптимизация [[Алгоритм поиска A*|'''алгоритма поиска A*''']] для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа<ref name="harabor2011">{{cite conference|author=Даниэль Харабор, Альбан Грастиен|year=2011|title=Сокращение онлайн-графа для поиска пути на сеточных картах|conference=25-я Национальная конференция по искусственному интеллекту|publisher=AAAI|url=http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf|access-date=2021-09-14|archive-date=2014-12-16|archive-url=https://web.archive.org/web/20141216222556/http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf|deadlink=no}}</ref>, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные ''скачки'' по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой, как это учитывает обычный '''A*'''<ref>{{cite web|url=http://zerowidth.com/2013/05/05/jump-point-search-explained.html|title=Объяснение поиска точки перехода|accessdate=9 March 2014|date=5 мая 2013 года|website=zerowidth positive lookahead|author=Натан Уитмер|archive-date=2014-03-10|archive-url=https://web.archive.org/web/20140310022652/http://zerowidth.com/2013/05/05/jump-point-search-explained.html|deadlink=yes}}</ref>. | | В [[Информатика|информатике]] '''Поиск точки перехода''' ('''ПТП''') '''Jump point search''' ('''JPS''')) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные ''скачки'' по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой |
|
| |
|
| Поиск точки перехода сохраняет оптимальность '''A*''', потенциально сокращая время его выполнения на порядок<ref name="harabor2011"/>. | | Поиск точки перехода сохраняет оптимальность '''A*''', потенциально сокращая время его выполнения на порядок. |
|
| |
|
| == История == | | == История == |
| В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников<ref name="harabor2011"/>. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми). | | В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными [[агент]]ами (например, [[робототехника|робототехникой]]), либо [[симуляция]]ми (например, многими играми). |
|
| |
|
| Авторы представили изменённые правила обрезки для приложений, в которых обрезка углов запрещена в следующем году<ref name="harabor2012">{{cite conference|author=Д. Харабор, А. Грастиен|year=2012|title=Система поиска пути JPS|conference=26-я Национальная конференция по искусственному интеллекту|publisher=AAAI|url=http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/viewFile/5396/5212|access-date=2021-09-14|archive-date=2020-11-09|archive-url=https://web.archive.org/web/20201109054616/http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/viewFile/5396/5212|deadlink=no}}</ref>. В этой статье также представлен алгоритм предварительной обработки сетки для минимизации времени поиска в Интернете.
| |
|
| |
|
| В 2014 году авторы опубликовали ряд дополнительных оптимизаций<ref name=Harabor2014>{{cite web|author=Д. Харабор, А. Грастиен|title=Улучшение поиска точки перехода|url=http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-icaps14.pdf|website=Колледж инженерии и информатики [[Австралийский национальный университет|Австралийского национального университета]]|publisher=Ассоциация развития искусственного интеллекта (www.aaai.org)|accessdate=11 July 2015|archive-date=2015-07-12|archive-url=https://web.archive.org/web/20150712192204/http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-icaps14.pdf|deadlink=no}}</ref>. Эти оптимизации включают изучение столбцов или строк узлов вместо отдельных узлов, предварительное вычисление ''переходов'' в сетке и более строгие правила отсечения.
| | ---- |
| | |
| == Будущая работа ==
| |
| Хотя поиск точки перехода ограничен сетками с однородными затратами и агентами с однородным размером, в будущем авторы планируют использовать '''ПТП''' с существующими методами ускорения на основе сетки, такими как иерархические сетки<ref name=Harabor2014 /><ref name=Botea2004>{{cite web|author=Ади Ботеа, Мартин Мюллер|year=2004|title=Поиск почти оптимального иерархического пути|website=University of Alberta|publisher=[[Альбертский университет]]|url=https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf|access-date=2021-09-14|archive-date=2021-09-14|archive-url=https://web.archive.org/web/20210914103325/https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf|deadlink=no}}</ref>.
| |
| | |
| == Примечания ==
| |
| {{примечания}}
| |
| | |
| {{Алгоритмы поиска на графах}}
| |
| | |
| [[Категория:Игровой искусственный интеллект]]
| |
| [[Категория:Алгоритмы на графах]]
| |
| [[Категория:Алгоритмы поиска]] | | [[Категория:Алгоритмы поиска]] |
В информатике Поиск точки перехода (ПТП) Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой
Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его выполнения на порядок.
История
В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников. Первоначальный алгоритм отсечения соседей позволял вырезать углы, что означало, что алгоритм мог использоваться только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми).
