Изменения

Алгоритм '''А*'''("англ. ''A star", "А звёздочка"'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Чем меньше , тем раньше вершина будет открыта и исследована алгоритмом. Таким образом открытые алгоритмом вершины хранятся в очереди с приоритетом по значению <tex>f(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>. А* действует подобно [[Файл:Diagonal.pngАлгоритм Дейкстры |thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвленияхалгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими. <br clear="all">==Свойства==Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.{{Определение|definition=Говорят, что эвристическая оценка <tex>h(v)</tex> '''допустима''', если для любой вершины <tex>v</tex> значение <tex>h(v)</tex> меньше или равно весу кратчайшего пути от постановки задачи<tex>v</tex> до цели. Часто А* используется }} Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле. <br>Второе, более сильное условие {{---}} функция <tex>h(v)</tex> должна быть '''монотонной'''. {{Определение|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>, а эвристическая оценка целевого состояния равна нулю.}} {{Теорема|statement=Любая монотонная эвристика допустима, однако обратное неверно.|proof=Пусть <tex>k(v)</tex> {{---}} длина кратчайшего пути из вершины <tex>v</tex> до цели. Докажем индукцией по поверхностичислу шагов до цели, покрытой [http:что <tex>h(v) \leqslant k(v)</tex>.<br><br>Если до цели расстояние <tex>0</tex>, то <tex>v</deeptex> {{-beta--}} цель и <tex>h(v) = 0 \leqslant k(v)</tex>.co<br><br>Пусть <tex>v</tex> находится на расстоянии <tex>i</tex> от цели.ukТогда существует потомок <tex>v'</wptex>, который находится на кратчайшем пути от <tex>v</tex> до цели и <tex>v'</tex>лежит на расстоянии <tex>i -content1</uploadstex> шагов до цели. Следовательно, <tex>h(v) \leqslant c(v, v') + h(v')</2010tex>. <br>По предположению, <tex>h(v') \leqslant k(v')</11tex>. Следовательно, <tex>h(v) \leqslant c(v, v') + k(v') = k(v)</terraintex>.0<br><br>Таким образом, монотонная эвристика <tex>h(v)</tex> допустима.}} {{Утверждение|statement=Если <tex>h(v)</tex> монотонна, то последовательность значений <tex>f(v)</tex> на любом пути неубывает.|proof=Доказательство следует из определения монотонности.3<br>Пусть <tex>v'</tex> {{---}} потомок <tex>v</tex>, тогда <tex>g(v') = g(v) +gridc(v, v')</tex>.png координатной сеткой]<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* Если мы можем перемещаться в четырех направленияхявляется оптимальным, в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]<br> если функция <tex>h(v) = |{v</tex> монотонна.x-goal.x}| + |{v.y-goal.y}|proof=Последовательность вершин "развёрнутых" во время работы алгоритма находится в неубывающем порядке значений <tex>f</tex>. Поэтому очередная выбираемая вершина должна представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими. }}

* ==Примеры эвристик==Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[httpФайл://ru.wikipediaDiagonal.org/wiki/Расстояние_Чебышева Расстояние Чебышева] применяется когда к четырем направлениям добавляются диагонали:<br> <tex>h(v) = \max{(png|{v.x-goal.x}thumb|, right|{vПример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи.y-goal.y}|)}</tex>Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.

* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<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>Q</tex> {{---}} множество вершин, которые требуется рассмотреть,* <tex>U</tex> {{---}} множество рассмотренных вершин,* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>,* <tex>g[Файл:Astar_progress_animationx]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>,* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.gif|thumb|right|Пример На каждом этапе работы А*алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Пустые кружки принадлежат к открытому спискуДля каждого из соседей обновляется расстояние, а окрашенные к закрытомузначение эвристической функции и он добавляется в множество <tex>Q</tex>.]]<br>Псевдокод: void '''bool''' A*(start,goal) ''':''' { U = <tex> \varnothing </tex> closed :Q = {}; <tex> \varnothing <// Множество вершин расстояние до которых мы уже оценилиtex> openQ.push(start);// Очередь с приоритетом g[start] = 0 f[start] = g[start] + h[(start]; parent[start] = start;) '''while (open''' Q.size() != 0) { x :current = open.pop(); вершина из <tex>Q</tex> с минимальным значением <tex>f</tex> '''if (x ''' current == goal) '''return succsess(x);''' ''true'' <font color="green">// Кратчайший нашли путь найден до нужной вершины</font> closedQ.pushremove(xcurrent); for U.push(y : xy in Ecurrent) {'''for''' v : смежные с current вершины if (y in closed) continue; tmp :tentativeScore = g[xcurrent] + d[x(current,y] v) <font color="green">// Стоимость пути до y через х if d(y not in opencurrent, v) { open.push(y); tentative_is_better = true; {---}}стоимость пути между current и v</font> else '''if (tmp ''' <tex>v \in U< /tex> '''and''' tentativeScore >= g[yv]) // можно улучшить расстояние до y tentative_is_better = true else tentative_is_better = false '''continue''' '''if (tentative_is_better == true) ''' <tex>v \notin U<// найден новый, более короткий путь до y { tex> '''or''' tentativeScore < g[v] parent[yv] = x;current g[yv] = tmp;tentativeScore f[yv] = g[yv] + h[y];(v) } '''if''' <tex>v \notin Q</tex> } } Q.push(v) '''return failure; // Наша цель недостижима из start''' ''false'' }==СвойстваСм. также==* [[Эвристики для поиска кратчайших путей]]* [[Алгоритм Флойда]]* [[Алгоритм Дейкстры]]* [[Алгоритм Форда-Беллмана]] ===Корректность=Примечания== Если <tex>h(v)<references/tex> всегда меньше либо равна истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.{{Теорема|statement=Пусть G - граф, h(v) - допустимая эвристическая функция. Тогда после завершения работы будет найдено кратчайшее расстояние до целевой вершины.|proof=Когда A* завершает поиск, он, согласно определению, нашёл путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимым.}}

===Оптимальность=Источники информации==Любой другой алгоритм* С. Рассел, использующий ту же эвристическую функцию <tex>h(v)</tex>П. Норвиг {{---}} Искусственный интеллект. Современный подход, рассмотрит не меньше вершин, чем А*. ==Ссылки==2е издание*[httphttps://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Википедия:Алгоритм_поиска_A{{---}} Алгоритм поиска A*]*[httphttps://en.wikipedia.org/wiki/A*_search_algorithm Wikipedia:{{---}} A*_search_algorithmsearch 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*]