Алгоритм A* — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 1: Строка 1:
 
Алгоритм '''А*''' (англ. ''A star'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
Алгоритм '''А*''' (англ. ''A star'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
==Описание==
 
==Описание==
 +
[[Файл:Astar_progress_animation.gif|right|frame|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
 
В процессе работы алгоритма для вершин рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где  
 
В процессе работы алгоритма для вершин рассчитывается функция <tex>f(v) = g(v) + h(v)</tex>, где  
 
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>v</tex> из стартовой вершины,  
 
*<tex>g(v)</tex> {{---}} наименьшая стоимость пути в <tex>v</tex> из стартовой вершины,  
Строка 7: Строка 8:
 
Фактически, функция <tex>f(v)</tex> {{---}} длина пути до цели, которая складывается из пройденного расстояния <tex>g(v)</tex> и оставшегося расстояния <tex>h(v)</tex>. Исходя из этого, чем меньше значение <tex>f(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>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.  
 
Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению <tex>f(v)</tex>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.  
 
+
<br clear="all">
 
==Свойства==
 
==Свойства==
 
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
 
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
Строка 42: Строка 43:
  
 
==Примеры эвристик==
 
==Примеры эвристик==
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].
+
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.
  
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]<br> <tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.  
+
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<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>.  
  
* [http://ru.wikipedia.org/wiki/Расстояние_Чебышева Расстояние Чебышева] применяется когда к четырем направлениям добавляются диагонали:<br> <tex>h(v) = \max{(|{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>.
 
* Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:<br> <tex>h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}</tex>.
Строка 54: Строка 55:
 
==Реализация==
 
==Реализация==
 
В приведённой реализации:
 
В приведённой реализации:
* <tex>Q</tex> {{---}} множество вершин, которые требуется рассмотреть
+
* <tex>Q</tex> {{---}} множество вершин, которые требуется рассмотреть,
* <tex>U</tex> {{---}} множество рассмотренных вершин
+
* <tex>U</tex> {{---}} множество рассмотренных вершин,
* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>
+
* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>,
* <tex>g[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>
+
* <tex>g[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>,
 
* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.
 
* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.
На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновлятся расстояние, значение эвристическо функции и он добавляется в множество <tex>Q</tex>.<br>
+
На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество <tex>Q</tex>.<br>
 
Псевдокод:
 
Псевдокод:
 
  '''bool''' A*(start, goal)''':'''
 
  '''bool''' A*(start, goal)''':'''
Строка 74: Строка 75:
 
         U.push(current)
 
         U.push(current)
 
         '''for''' v : смежные с current вершины
 
         '''for''' v : смежные с current вершины
             tentative_score = g[current] + d(current, v)         <font color="green">// d(current, v) {{---}} стоимость пути между current и v</font>  
+
             tentativeScore = g[current] + d(current, v)           <font color="green">// d(current, v) {{---}} стоимость пути между current и v</font>  
             '''if''' <tex>v \in U</tex> '''and''' tentative_score >= g[v]
+
             '''if''' <tex>v \in U</tex> '''and''' tentativeScore >= g[v]
 
                 '''continue'''
 
                 '''continue'''
             '''if''' <tex>v \notin U</tex> '''or''' tentative_score < g[v]
+
             '''if''' <tex>v \notin U</tex> '''or''' tentativeScore < g[v]
 
                 parent[v] = current
 
                 parent[v] = current
                 g[v] = tentative_score
+
                 g[v] = tentativeScore
 
                 f[v] = g[v] + h(v)
 
                 f[v] = g[v] + h(v)
 
                 '''if''' <tex>v \notin Q</tex>
 
                 '''if''' <tex>v \notin Q</tex>
Строка 87: Строка 88:
 
==См. также==
 
==См. также==
 
* [[Эвристики для поиска кратчайших путей]]
 
* [[Эвристики для поиска кратчайших путей]]
 +
* [[Алгоритм Флойда]]
 +
* [[Алгоритм Дейкстры]]
 +
* [[Алгоритм Форда-Беллмана]]
 +
 +
==Примечания==
 +
<references/>
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 22:59, 6 мая 2019

Алгоритм А* (англ. A star) — алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

Описание

Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.

В процессе работы алгоритма для вершин рассчитывается функция [math]f(v) = g(v) + h(v)[/math], где

  • [math]g(v)[/math] — наименьшая стоимость пути в [math]v[/math] из стартовой вершины,
  • [math]h(v)[/math] — эвристическое приближение стоимости пути от [math]v[/math] до конечной цели.

Фактически, функция [math]f(v)[/math] — длина пути до цели, которая складывается из пройденного расстояния [math]g(v)[/math] и оставшегося расстояния [math]h(v)[/math]. Исходя из этого, чем меньше значение [math]f(v)[/math], тем раньше мы откроем вершину [math]v[/math], так как через неё мы предположительно достигнем расстояние до цели быстрее всего. Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению [math]f(v)[/math]. А* действует подобно алгоритму Дейкстры и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.

Свойства

Чтобы A* был оптимален, выбранная функция [math]h(v)[/math] должна быть допустимой эвристической функцией.

Определение:
Говорят, что эвристическая оценка [math]h(v)[/math] допустима, если для любой вершины [math]v[/math] значение [math]h(v)[/math] меньше или равно весу кратчайшего пути от [math]v[/math] до цели.


Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле.
Второе, более сильное условие — функция [math]h(v)[/math] должна быть монотонной.


Определение:
Эвристическая функция [math]h(v)[/math] называется монотонной (или преемственной), если для любой вершины [math]v_1[/math] и ее потомка [math]v_2[/math] разность [math]h(v_1)[/math] и [math]h(v_2)[/math] не превышает фактического веса ребра [math]c(v_1, v_2)[/math] от [math]v_1[/math] до [math]v_2[/math], а эвристическая оценка целевого состояния равна нулю.


Теорема:
Любая монотонная эвристика допустима, однако обратное неверно.
Доказательство:
[math]\triangleright[/math]

Пусть [math]k(v)[/math] — длина кратчайшего пути из вершины [math]v[/math] до цели. Докажем индукцией по числу шагов до цели, что [math]h(v) \leqslant k(v)[/math].

Если до цели расстояние [math]0[/math], то [math]v[/math] — цель и [math]h(v) = 0 \leqslant k(v)[/math].

Пусть [math]v[/math] находится на расстоянии [math]i[/math] от цели. Тогда существует потомок [math]v'[/math], который находится на кратчайшем пути от [math]v[/math] до цели и [math]v'[/math]лежит на расстоянии [math]i - 1[/math] шагов до цели. Следовательно, [math]h(v) \leqslant c(v, v') + h(v')[/math].

По предположению, [math]h(v') \leqslant k(v')[/math]. Следовательно, [math]h(v) \leqslant c(v, v') + k(v') = k(v)[/math].

Таким образом, монотонная эвристика [math]h(v)[/math] допустима.
[math]\triangleleft[/math]
Утверждение:
Если [math]h(v)[/math] монотонна, то последовательность значений [math]f(v)[/math] на любом пути неубывает.
[math]\triangleright[/math]

Доказательство следует из определения монотонности.

Пусть [math]v'[/math] — потомок [math]v[/math], тогда [math]g(v') = g(v) + c(v, v')[/math].
Следовательно, [math]f(v') = g(v') + h(v') = g(v) + c(v, v') + h(v') \geqslant g(v) + h(v) = f(v)[/math].
[math]\triangleleft[/math]
Утверждение:
Алгоритм A* является оптимальным, если функция [math]h(v)[/math] монотонна.
[math]\triangleright[/math]
Последовательность вершин "развёрнутых" во время работы алгоритма находится в неубывающем порядке значений [math]f[/math]. Поэтому очередная выбираемая вершина должна представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими.
[math]\triangleleft[/math]

Примеры эвристик

Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит
Пример А* на сетке с возможностью ходить в восьми напрвлениях
от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.
  • Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние[1]
    [math]h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|[/math].
  • Расстояние Чебышева[2] применяется, когда к четырем направлениям добавляются диагонали:
    [math]h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}[/math].
  • Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:
    [math]h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}[/math].

Также стоит обратить внимание на то как соотносятся [math]f(v)[/math] и [math]h(v)[/math]. Если они измеряются в разных величинах (например, [math]g(v)[/math] — это расстояние в километрах, а [math]h(v)[/math] — оценка времени пути в часах) А* может выдать некорректный результат.

Реализация

В приведённой реализации:

  • [math]Q[/math] — множество вершин, которые требуется рассмотреть,
  • [math]U[/math] — множество рассмотренных вершин,
  • [math]f[x][/math] — значение эвристической функции "расстояние + стоимость" для вершины [math]x[/math],
  • [math]g[x][/math] — стоимость пути от начальной вершины до [math]x[/math],
  • [math]h(x)[/math] — эвристическая оценка расстояния от вершины [math]x[/math] до конечной вершины.

На каждом этапе работы алгоритма из множества [math]Q[/math] выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество [math]Q[/math].
Псевдокод:

bool A*(start, goal):
    U = [math] \varnothing [/math]
    Q = [math] \varnothing [/math]
    Q.push(start)
    g[start] = 0
    f[start] = g[start] + h(start)
    while Q.size() != 0
        current = вершина из [math]Q[/math] с минимальным значением [math]f[/math]
        if current == goal
            return true                                           // нашли путь до нужной вершины
        Q.remove(current)
        U.push(current)
        for v : смежные с current вершины
            tentativeScore = g[current] + d(current, v)           // d(current, v) — стоимость пути между current и v 
            if [math]v \in U[/math] and tentativeScore >= g[v]
                continue
            if [math]v \notin U[/math] or tentativeScore < g[v]
                parent[v] = current
                g[v] = tentativeScore
                f[v] = g[v] + h(v)
                if [math]v \notin Q[/math]
                    Q.push(v)
    return false

См. также

Примечания

Источники информации