Изменения

Алгоритм '''А*'''("англ. ''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> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.

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

{{Определение|definition==Доказательство оптимальности и корректности==Полное доказательство расположено [http:Эвристическая функция <tex>h(v)</tex> называется '''монотонной''' (или '''преемственной'''), если для любой вершины <tex>v_1</www.cs.auckland.ac.nztex> и ее потомка <tex>v_2</compsci709s2ctex> разность <tex>h(v_1)</resourcestex> и <tex>h(v_2)</Mike.d/astarNilsson.pdf здесь]. Здесь приведем основные факты.Алгоритм является допустимымtex> не превышает фактического веса ребра <tex>c(корректнымv_1, v_2) если он гарантированно находит оптимальный путь из </tex> от <tex>Sv_1</tex> до целевой вершины<tex>v_2</tex>, а эвристическая оценка целевого состояния равна нулю. Допустимые алгоритмы могут различаться числом рассмотренных вершин и порядком просмотра вершин.}}

Лемма 1. Для любой незакрытой вершины {{Утверждение|statement=Если <tex>nh(v)</tex> и любого оптимального пути монотонна, то последовательность значений <tex>Pf(v)</tex> на любом пути неубывает.|proof=Доказательство следует из определения монотонности.<br>Пусть <tex>Sv'</tex> в {{---}} потомок <tex>nv</tex> существует открытая вершина , тогда <tex>ng(v') = g(v) + c(v, v')</tex>. <br>Следовательно, лежащая на этом пути, для которой найденная стоимость пути из <tex>Sf(v') = g(v') + h(v') = g(v) + c(v, v') + h(v') \geqslant g(v) + h(v) = f(v)</tex> оптимальна.}}

Теорема 1{{Утверждение|statement=Алгоритм A* является оптимальным, если функция <tex>h(v)</tex> монотонна.|proof=Последовательность вершин "развёрнутых" во время работы алгоритма находится в неубывающем порядке значений <tex>f</tex>. Если для любой вершины эвристика не переоценивает настоящую стоимость минимального пути до целевой вершиныПоэтому очередная выбираемая вершина должна представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, то А* допустимпо меньшей мере, столь же дорогостоящими.}}

Оптимальность ==Примеры эвристик==Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А*на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.

Лемма 2. Предположим* Если мы можем перемещаться в четырех направлениях, что то в процессе работы А* вершина качестве эвристики стоит выбрать манхэттенское расстояние<ref>[https://en.wikipedia.org/wiki/Manhattan_distance Wikipedia {{---}} Manhattan distance]</ref><br> <tex>nh(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex> была закрыта и эвристика монотонна. Тогда вычисленный до нее путь из стартовой вершины оптимален.

Теорема 2* Расстояние Чебышева<ref>[https://ru. Пусть А допустимый алгоритм информированный не больше чем А* и эвристика допустима и монотоннаwikipedia.Тогда если А* рассмотрела в процессе выполнения некоторую вершину org/wiki/Расстояние_Чебышева Википедия {{---}} Расстояние Чебышева]</ref> применяется, когда к четырем направлениям добавляются диагонали:<br> <tex>nh(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 Статья на ACM Digital LibraryGeneralized best-first search strategies and the optimality of A*]