188
правок
Изменения
Нет описания правки
Алгоритм '''А*''' (англ. ''A star'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
==Описание==
[[Файл:Astar_progress_animation.gif|right|frame|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
В процессе работы алгоритма для вершин рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>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>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.
<br clear="all">
==Свойства==
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
==Примеры эвристик==
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<ref>[httphttps://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояниеWikipedia {{---}} Manhattan distance]</ref><br> <tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.
* Расстояние Чебышева<ref>[httphttps://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[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>,
* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.
На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновлятся расстояние, значение эвристическо функции и он добавляется в множество <tex>Q</tex>.<br>
U.push(current)
'''for''' v : смежные с current вершины
'''continue'''
'''if''' <tex>v \notin U</tex> '''or''' tentative_score tentativeScore < g[v]
parent[v] = current
g[v] = tentative_scoretentativeScore
f[v] = g[v] + h(v)
'''if''' <tex>v \notin Q</tex>
Q.push(v)
'''return''' ''false''
==Примечания==
<references/>
==См. также==
* [[Эвристики для поиска кратчайших путей]]
* [[Алгоритм Флойда]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Форда-Беллмана]]
==Источники информации==
