Поиск точки перехода - История изменений

Patarakin в 13:33, 1 декабря 2022

2022-12-01T13:33:56Z

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

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

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


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

Patarakin в 13:16, 23 ноября 2022

2022-11-23T13:16:00Z

← Предыдущая версия		Версия от 16:16, 23 ноября 2022
Строка 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="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>.

	~~== Примечания ==~~
	~~{{примечания}}~~

	~~{{Алгоритмы поиска на графах}}~~

	~~[[Категория:Игровой искусственный интеллект]]~~
	~~[[Категория:Алгоритмы на графах]]~~
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:55:03Z

1 версия импортирована

← Предыдущая версия	Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>InternetArchiveBot: Спасено источников — 4, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

2022-07-26T05:11:52Z

Спасено источников — 4, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

Новая страница

В [[Информатика|информатике]] '''Поиск точки перехода''' ('''ПТП''') ([[Английский язык|англ.]] '''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>.

Поиск точки перехода сохраняет оптимальность '''A*''', потенциально сокращая время его выполнения на порядок<ref name="harabor2011"/>.

== История ==
В оригинальной публикации Харабора и Грастиена представлены алгоритмы отсечения соседей и определения преемников<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>.

== Примечания ==
{{примечания}}

{{Алгоритмы поиска на графах}}

[[Категория:Игровой искусственный интеллект]]
[[Категория:Алгоритмы на графах]]
[[Категория:Алгоритмы поиска]]