Изменения

Алгоритм '''А*'''("англ. ''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=Доказательство следует из определения монотонности.<br>Пусть <tex>v'</tex> {{---}} потомок <tex>v</tex>, тогда <tex>g(v') = g(v) + c(v, v')</tex>.3<br>Следовательно, <tex>f(v') = g(v') + h(v') = g(v) + c(v, v') +gridh(v') \geqslant g(v) + h(v) = f(v)</tex>.}} {{Утверждение|statement=Алгоритм A* является оптимальным, если функция <tex>h(v)</tex> монотонна.png координатной сеткой]|proof=Последовательность вершин "развёрнутых" во время работы алгоритма находится в неубывающем порядке значений <tex>f</tex>. Поэтому очередная выбираемая вершина должна представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими.}}

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

* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<ref>[httphttps://ruen.wikipedia.org/wiki/Расстояние_Чебышева Расстояние ЧебышеваManhattan_distance Wikipedia {{---}} Manhattan distance] применяется когда к четырем направлениям добавляются диагонали:</ref><br> <tex>h(v) = \max{(|{v.x-goal.x}|, + |{v.y-goal.y}|)}</tex>.

* Если передвижение не ограниченно сеткойРасстояние Чебышева<ref>[https://ru.wikipedia.org/wiki/Расстояние_Чебышева Википедия {{---}} Расстояние Чебышева]</ref> применяется, то можно использовать евклидово расстояние по прямойкогда к четырем направлениям добавляются диагонали:<br> <tex>h(v) = \sqrtmax{(|{v.x-goal.x)^2 + (}|, |{v.y-goal.y}|)^2}</tex>.

Также стоит обратить внимание на * Если передвижение не ограничено сеткой, то как соотносятся можно использовать евклидово расстояние по прямой:<texbr>f(v)</tex> и <tex>h(v)</tex>. Если они измеряются в разных величинах (например, <tex>g= \sqrt{(v.x-goal.x)</tex> {{---}} это расстояние в километрах, а <tex>h^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[Файл: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) { if (y in closed) continue;'''for''' v : смежные с current вершины 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> всегда меньше либо равна истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.

===Оптимальность=Источники информации==Любой другой алгоритм* С. Рассел, использующий ту же эвристическую функцию <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*]