Изменения

Алгоритм '''А*'''("англ. ''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> {{-- -}} эвристическое приближение стоимости пути от <tex>v </tex> до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.==Псевдокод== void A*(start,goal) { closed := {}; // Множество вершин расстояние до которых мы уже оценили open.push(start);// Очередь с приоритетом f[start] = g[start] + h[start]; parent[start] = start;

while (open.sizeФактически, функция <tex>f(v) != 0) </tex> {{ x := open.pop---}} длина пути до цели, которая складывается из пройденного расстояния <tex>g(v); if </tex> и оставшегося расстояния <tex>h(x == goalv) return succsess</tex>. Исходя из этого, чем меньше значение <tex>f(xv);</tex>, тем раньше мы откроем вершину <tex>v</ Кратчайший путь найден closedtex>, так как через неё мы предположительно достигнем расстояние до цели быстрее всего.push(x); for Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению <tex>f(y : xy in Ev) { if (y in closed) continue; tmp := g</tex>. А* действует подобно [[xАлгоритм Дейкстры | алгоритму Дейкстры]] + d[xи просматривает среди всех маршрутов ведущих к цели сначала те,y] // Стоимость пути до y if которые благодаря имеющейся информации (y not in openэвристическая функция) { openв данный момент являются наилучшими.push(y); tentative_is_better <br clear= true;"all"> }==Свойства== else if Чтобы A* был оптимален, выбранная функция <tex>h(tmp v)< g[y]) /tex> должна быть '''допустимой''' эвристической функцией. tentative_is_better := true {{Определение else tentative_is_better :|definition= false if Говорят, что эвристическая оценка <tex>h(tentative_is_better == truev)</tex> '''допустима''', если для любой вершины <tex>v</ { parent[y] = x; g[y] = tmp; f[y] = g[y] + tex> значение <tex>h[y]; } } } return failure; (v)</tex> меньше или равно весу кратчайшего пути от <tex>v</ Наша цель недостижима из starttex> до цели. }}

==Доказательство оптимальности и корректности==Алгоритм 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>[https://ru.wikipedia.org/wiki/Расстояние_Чебышева Википедия {{---}} Расстояние Чебышева]</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е издание*[httphttps://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Алгоритм_поиска_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 Generalized best-first search strategies and the optimality of A* в частности]