Изменения

Алгоритм '''А*'''("англ. ''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() != 0) { x := open.pop(); if (x == goal) return succsess(x);// Кратчайший путь найден closed.push(x); for (y : xy in E) { if (y in closed) continue; tmp := g[x] + d[x,y] // Стоимость пути до y if (y not in open) { 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)// { parent[y] = x; g[y] = tmp; f[y] = g[y] + h[y]; } } } return failure; // Наша цель недостижима из start }

Фактически, функция <tex>f(v)</tex> {{---}} длина пути до цели, которая складывается из пройденного расстояния <tex>g(v)</tex> и оставшегося расстояния <tex>h(v)</tex>. Исходя из этого, чем меньше значение <tex>f(v)</tex>, тем раньше мы откроем вершину <tex>v</tex>, так как через неё мы предположительно достигнем расстояние до цели быстрее всего.Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими. <br clear="all">==Доказательство оптимальности и корректностиСвойства==Алгоритм Чтобы A* и допустимбыл оптимален, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершинувыбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией. Оптимистичной в том смысле{{Определение|definition=Говорят, чтоэвристическая оценка <tex>h(v)</tex> '''допустима''', если он пойдёт через эту вершину, у алгоритма «есть шанс», что реальная стоимость результата будет равна этой оценке, но никак не для любой вершины <tex>v</tex> значение <tex>h(v)</tex> меньшеили равно весу кратчайшего пути от <tex>v</tex> до цели. Но, поскольку A* является информированным алгоритмом, такое равенство может быть вполне возможным.}}

Когда A* завершает поискДопустимая оценка является оптимистичной, он, согласно определениюпотому что она предполагает, нашёл путь, истинная что стоимость которого решения меньше, чем оценка стоимости любого пути через любой открытый узелоно есть на самом деле. Но поскольку эти оценки являются оптимистичными<br>Второе, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимымболее сильное условие {{---}} функция <tex>h(v)</tex> должна быть '''монотонной'''.

Предположим теперь, что некий алгоритм B вернул в качестве результата путь, длина которого больше оценки стоимости пути через некоторую вершину. На основании эвристической информации{{Определение|definition=Эвристическая функция <tex>h(v)</tex> называется '''монотонной''' (или '''преемственной'''), если для алгоритма B нельзя исключить возможность, что этот путь имел любой вершины <tex>v_1</tex> и ее потомка <tex>v_2</tex> разность <tex>h(v_1)</tex> и меньшую реальную длину, чем результат. Соответственно, пока алгоритм B просмотрел меньше вершин, чем A*, он <tex>h(v_2)</tex> не будет допустимым. Итакпревышает фактического веса ребра <tex>c(v_1, A* проходит наименьшее количество вершин графа среди допустимых алгоритмовv_2)</tex> от <tex>v_1</tex> до <tex>v_2</tex>, использующих такую же точную (или менее точную) эвристикуа эвристическая оценка целевого состояния равна нулю.}}

{{Теорема|statement=Любая монотонная эвристика допустима, однако обратное неверно.|proof=Пусть <tex>k(v)</tex> {{---}} длина кратчайшего пути из вершины <tex>v</tex> до цели. Докажем индукцией по числу шагов до цели, что <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> шагов до цели. Следовательно, <tex>h(v) \leqslant c(v, v') + h(v')</tex>. <br>По предположению, <tex>h(v') \leqslant k(v')</tex>. Следовательно, <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* в частности]