Изменения

Перейти к: навигация, поиск

Алгоритм A*

4365 байт добавлено, 22:59, 6 мая 2019
Реализация
Алгоритм '''А*'''("англ. ''A star", "А звёздочка"'') {{-- информированный -}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.==ЭвристикаОписание==[[Файл:Astar_progress_animation.gif|right|frame|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]В процессе работы алгоритма для вершин используется рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где *<tex>g(v)</tex> {{--- }} наименьшая стоимость пути в <tex>v </tex> из стартовой вершины, *<tex>h(v)</tex> {{-- -}} эвристическое приближение стоимости пути от v до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.К примеру, если <tex>(h(v) == 0)</tex>, то А* превращается в [http://chernykh.net/images/stories/Person/deiksteira.jpg Дейкстру ]. Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до конечной цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.
==Псевдокод==Фактически, функция <tex>f(v)</tex> {{---}} длина пути до цели, которая складывается из пройденного расстояния <tex>g(v)</tex> и оставшегося расстояния <tex>h(v)</tex>. Исходя из этого, чем меньше значение <tex>f(v)</tex>, тем раньше мы откроем вершину <tex>v</tex>, так как через неё мы предположительно достигнем расстояние до цели быстрее всего.Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент похожи на наилучший, причем алгоритм учитывает путь уже пройденный до текущей вершинявляются наилучшими. [[Файл:Astar_progress_animation.gif|thumb|right|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]] void A*(start,goal) { closed := {}; // Множество вершин расстояние до которых мы уже оценили open.push(start);// Очередь с приоритетом f[start] = g[start] + h[start]; parent[start] <br clear= start;"all"> while (open.size() != 0) { x := open.pop(); if (x Свойства== goal) return succsessЧтобы A* был оптимален, выбранная функция <tex>h(xv);/</ Кратчайший путь найден closedtex> должна быть '''допустимой''' эвристической функцией.push(x); for (y : xy in E) {{Определение if |definition=Говорят, что эвристическая оценка <tex>h(y in closedv) continue; tmp := g[x] + d[x</tex> '''допустима''',y] если для любой вершины <tex>v<// Стоимость пути до y if tex> значение <tex>h(y not in openv) { open.push(y); tentative_is_better = true; } else if (tmp < g[y]) tentative_is_better := true else tentative_is_better := false if (tentative_is_better == true)/tex> меньше или равно весу кратчайшего пути от <tex>v</ tex> до цели. { parent[y] = x; g[y] = tmp; f[y] = g[y] + h[y]; } } } return failure; // Наша цель недостижима из start }
==Доказательство оптимальности и корректности==Алгоритм A* и допустим, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершину. Оптимистичной в том смыслеДопустимая оценка является оптимистичной, потому что, если он пойдёт через эту вершину, у алгоритма «есть шанс»она предполагает, что реальная стоимость результата будет равна этой оценкерешения меньше, но никак не меньшечем оно есть на самом деле. Но, поскольку A* является информированным алгоритмом<br>Второе, такое равенство может более сильное условие {{---}} функция <tex>h(v)</tex> должна быть вполне возможным'''монотонной'''.
Когда A* завершает поиск{{Определение|definition=Эвристическая функция <tex>h(v)</tex> называется '''монотонной''' (или '''преемственной'''), онесли для любой вершины <tex>v_1</tex> и ее потомка <tex>v_2</tex> разность <tex>h(v_1)</tex> и <tex>h(v_2)</tex> не превышает фактического веса ребра <tex>c(v_1, согласно определениюv_2)</tex> от <tex>v_1</tex> до <tex>v_2</tex>, нашёл путь, истинная стоимость которого меньше, чем а эвристическая оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимымцелевого состояния равна нулю.}}
Предположим теперь, что некий алгоритм B вернул в качестве результата путь{{Теорема|statement=Любая монотонная эвристика допустима, однако обратное неверно.|proof=Пусть <tex>k(v)</tex> {{---}} длина которого больше оценки стоимости кратчайшего пути через некоторую вершинуиз вершины <tex>v</tex> до цели. На основании эвристической информацииДокажем индукцией по числу шагов до цели, для алгоритма B нельзя исключить возможностьчто <tex>h(v) \leqslant k(v)</tex>.<br><br>Если до цели расстояние <tex>0</tex>, что этот путь имел то <tex>v</tex> {{---}} цель и меньшую реальную длину<tex>h(v) = 0 \leqslant k(v)</tex>.<br><br>Пусть <tex>v</tex> находится на расстоянии <tex>i</tex> от цели. Тогда существует потомок <tex>v'</tex>, чем результаткоторый находится на кратчайшем пути от <tex>v</tex> до цели и <tex>v'</tex>лежит на расстоянии <tex>i - 1</tex> шагов до цели. СоответственноСледовательно, пока алгоритм B просмотрел меньше вершин<tex>h(v) \leqslant c(v, чем A*v') + h(v')</tex>. <br>По предположению, он не будет допустимым<tex>h(v') \leqslant k(v')</tex>. ИтакСледовательно, A* проходит наименьшее количество вершин графа среди допустимых алгоритмов<tex>h(v) \leqslant c(v, v') + k(v') = k(v)</tex>. <br><br>Таким образом, использующих такую же точную монотонная эвристика <tex>h(или менее точнуюv) эвристику</tex> допустима.}}
{{Утверждение|statement=Если <tex>h(v)</tex> монотонна, то последовательность значений <tex>f(v)</tex> на любом пути неубывает.|proof=СсылкиДоказательство следует из определения монотонности.<br>Пусть <tex>v'</tex> {{---}} потомок <tex>v</tex>, тогда <tex>g(v') =g(v) + c(v, v')</tex>. <br>Следовательно, <tex>f(v') = g(v') + h(v') = g(v) + c(v, v') + h(v') \geqslant g(v) + h(v) = f(v)</tex>.}} {{Утверждение|statement=Алгоритм A* является оптимальным, если функция <tex>h(v)</tex> монотонна.|proof=Последовательность вершин "развёрнутых" во время работы алгоритма находится в неубывающем порядке значений <tex>f</tex>. Поэтому очередная выбираемая вершина должна представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими. }} ==Примеры эвристик==Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой. * Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<ref>[https://en.wikipedia.org/wiki/Manhattan_distance Wikipedia {{---}} Manhattan distance]</ref><br> <tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.  *Расстояние Чебышева<ref>[httphttps://ru.wikipedia.org/wiki/Алгоритм_поиска_AРасстояние_Чебышева Википедия {{---}} Расстояние Чебышева]</ref> применяется, когда к четырем направлениям добавляются диагонали:<br> <tex>h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}</tex>. * Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:<br> <tex>h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}</tex>. Также стоит обратить внимание на то как соотносятся <tex>f(v)</tex> и <tex>h(v)</tex>. Если они измеряются в разных величинах (например, <tex>g(v)</tex> {{---}} это расстояние в километрах, а <tex>h(v)</tex> {{---}} оценка времени пути в часах) А* может выдать некорректный результат. ==Реализация==В приведённой реализации:* <tex>Q</tex> {{---}} множество вершин, которые требуется рассмотреть,* <tex>U</tex> {{---}} множество рассмотренных вершин,* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>,* <tex>g[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>,* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество <tex>Q</tex>.<br>Псевдокод: '''bool''' A*(start, goal)''':''' U = <tex> \varnothing </tex> Q = <tex> \varnothing </tex> Q.push(start) g[start] = 0 f[start] = g[start] + h(start) '''while''' Q.size() != 0 current = вершина из <tex>Q</tex> с минимальным значением <tex>f</tex> '''if''' current == goal '''return''' ''true'' <font color="green">// нашли путь до нужной вершины</font> Q.remove(current) U.push(current) '''for''' v : смежные с current вершины tentativeScore = g[current] + d(current, v) <font color="green">// d(current, v) {{---}} стоимость пути между current и v</font> '''if''' <tex>v \in U</tex> '''and''' tentativeScore >= g[v] '''continue''' '''if''' <tex>v \notin U</tex> '''or''' tentativeScore < g[v] parent[v] = current g[v] = tentativeScore f[v] = g[v] + h(v) '''if''' <tex>v \notin Q</tex> Q.push(v) '''return''' ''false'' ==См. также==* [[Эвристики для поиска кратчайших путей]]* [[Алгоритм Флойда]]* [[Алгоритм Дейкстры]]* [[Алгоритм Форда-Беллмана]] ==Примечания==<references/> ==Источники информации==* С. Рассел, П. Норвиг {{---}} Искусственный интеллект. Современный подход, 2е издание* [https://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Википедия{{---}} Алгоритм поиска A*]*[httphttps://en.wikipedia.org/wiki/A*_search_algorithm Wikipedia {{---}} A*_search_algorithm Wikipediasearch algorithm]*[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей и различных оптимизациях А* в частности]*[http://dl.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM Статья на ACM Digital LibraryGeneralized best-first search strategies and the optimality of A*]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
Анонимный участник

Навигация