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