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