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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Алгоритм '''А*'''("A star", "А звёздочка") {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
+
Алгоритм '''А*''' (англ. ''A star'') {{---}} алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
 
==Описание==
 
==Описание==
 
В процессе работы алгоритма для вершин рассчитывается функция <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> из стартовой вершины,  
*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать расстояние до цели.
+
*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели.  
Чем меньше <tex>h</tex>, тем раньше вершина будет открыта и исследована алгоритмом. Таким образом открытые алгоритмом вершины хранятся в очереди с приоритетом по значению <tex>f(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>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.
 +
 +
==Свойства==
 +
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
 +
{{Определение
 +
|definition=Говорят, что эвристическая оценка <tex>h(v)</tex> '''допустима''', если для любой вершины <tex>v</tex> значение <tex>h(v)</tex> меньше или равно весу кратчайшего пути от <tex>v</tex> до цели.
 +
}}
 +
 +
Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле. <br>
 +
Второе, более сильное условие {{---}} функция <tex>h(v)</tex> должна быть '''монотонной'''.
 +
 +
{{Определение
 +
|definition=Эвристическая функция <tex>h(v)</tex> называется '''монотонной''' (или '''преемственной'''), если для любой вершины <tex>v_1</tex> и ее потомка <tex>v_2</tex> разность <tex>h(v_1)</tex> и <tex>h(v_2)</tex> не превышает фактического веса ребра <tex>c(v_1, v_2)</tex> от <tex>v_1</tex> до <tex>v_2</tex>, а эвристическая оценка целевого состояния равна нулю.
 +
}}
 +
 +
{{Теорема
 +
|statement=Любая монотонная эвристика допустима, однако обратное неверно.
 +
|proof=Пусть <tex>k(v)</tex> {{---}} длина кратчайшего пути из вершины <tex>v</tex> до цели.
 +
Докажем индукцией по числу шагов до цели, что <tex>h(v) \leqslant k(v)</tex>.<br><br>
 +
Если до цели расстояние <tex>0</tex>, то <tex>v</tex> {{---}} цель и <tex>h(v) = 0 \leqslant k(v)</tex>.<br><br>
 +
Пусть <tex>v</tex> находится на расстоянии <tex>i</tex> от цели. Тогда существует потомок <tex>v'</tex>, который находится на кратчайшем пути от <tex>v</tex> до цели и <tex>v'</tex>лежит на расстоянии <tex>i - 1</tex> шагов до цели. Следовательно, <tex>h(v) \leqslant c(v, v') + h(v')</tex>. <br>
 +
По предположению, <tex>h(v') \leqslant k(v')</tex>. Следовательно, <tex>h(v) \leqslant c(v, v') + k(v') = k(v)</tex>. <br><br>Таким образом, монотонная эвристика <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|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].
 
Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит[[Файл:Diagonal.png|thumb|right|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой [http://deep-beta.co.uk/wp-content/uploads/2010/11/terrain.0.3+grid.png координатной сеткой].
  
* Если мы можем перемещаться в четырех направлениях, в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]<br> <tex>h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|</tex>.  
+
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать [http://en.wikipedia.org/wiki/Manhattan_distance манхэттенское расстояние]<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>.
+
* [http://ru.wikipedia.org/wiki/Расстояние_Чебышева Расстояние Чебышева] применяется когда к четырем направлениям добавляются диагонали:<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>.
  
 
Также стоит обратить внимание на то как соотносятся <tex>f(v)</tex> и <tex>h(v)</tex>. Если они измеряются в разных величинах (например, <tex>g(v)</tex> {{---}} это расстояние в километрах, а <tex>h(v)</tex> {{---}} оценка времени пути в часах) А* может выдать некорректный результат.
 
Также стоит обратить внимание на то как соотносятся <tex>f(v)</tex> и <tex>h(v)</tex>. Если они измеряются в разных величинах (например, <tex>g(v)</tex> {{---}} это расстояние в километрах, а <tex>h(v)</tex> {{---}} оценка времени пути в часах) А* может выдать некорректный результат.
  
==Псевдокод==
+
==Реализация==
+
В приведённой реализации:
[[Файл:Astar_progress_animation.gif|thumb|right|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
+
* <tex>Q</tex> {{---}} множество вершин, которые требуется рассмотреть
  void A*(start,goal)  
+
* <tex>U</tex> {{---}} множество рассмотренных вершин
     closed := {}; // Множество вершин расстояние до которых мы уже оценили
+
* <tex>f[x]</tex> {{---}} значение эвристической функции "расстояние + стоимость" для вершины <tex>x</tex>
     open.push(start);// Очередь с приоритетом
+
* <tex>g[x]</tex> {{---}} стоимость пути от начальной вершины до <tex>x</tex>
     f[start] = g[start] + h[start];
+
* <tex>h(x)</tex> {{---}} эвристическая оценка расстояния от вершины <tex>x</tex> до конечной вершины.
    parent[start] = start;
+
На каждом этапе работы алгоритма из множества <tex>Q</tex> выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновлятся расстояние, значение эвристическо функции и он добавляется в множество <tex>Q</tex>.<br>
     while (open.size() != 0)
+
Псевдокод:
         x := open.pop();
+
  '''bool''' A*(start, goal)''':'''
         if (x == goal)
+
     U = <tex> \varnothing </tex>
             return succsess(x);// Кратчайший путь найден       
+
    Q = <tex> \varnothing </tex>
         closed.push(x)
+
     Q.push(start)
         for (y : xy in E)
+
    g[start] = 0
             if (y in closed)     
+
     f[start] = g[start] + h(start)
                continue;
+
     '''while''' Q.size() != 0
            tmp := g[x] + d[x,y]  // Стоимость пути до y через х
+
         current = вершина из <tex>Q</tex> с минимальным значением <tex>f</tex>
             if (y not in open)
+
         '''if''' current == goal
                open.push(y);
+
             '''return''' ''true''                                          <font color="green">// нашли путь до нужной вершины</font>
                tentative_is_better = true;
+
         Q.remove(current)
            else           
+
        U.push(current)
                if (tmp < g[y]) // можно улучшить расстояние до y               
+
         '''for''' v : смежные с current вершины
                    tentative_is_better = true 
+
             tentative_score = g[current] + d(current, v)          <font color="green">// d(current, v) {{---}} стоимость пути между current и v</font>
                 else
+
             '''if''' <tex>v \in U</tex> '''and''' tentative_score >= g[v]
                    tentative_is_better = false 
+
                 '''continue'''
             if (tentative_is_better == true) // найден новый, более короткий путь до y                         
+
             '''if''' <tex>v \notin U</tex> '''or''' tentative_score < g[v]
                 parent[y] = x;
+
                 parent[v] = current
                 g[y] = tmp;
+
                 g[v] = tentative_score
                 f[y] = g[y] + h[y];           
+
                 f[v] = g[v] + h(v)
     return failure; // Наша цель недостижима из start
+
                '''if''' <tex>v \notin Q</tex>
 +
                    Q.push(v)
 +
     '''return''' ''false''
  
==Свойства==
+
==См. также==
===Корректность===
+
* [[Эвристики для поиска кратчайших путей]]
Если <tex>h(v)</tex> всегда меньше либо равна истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.
 
{{Теорема
 
|statement=Пусть G - граф, h(v) - допустимая эвристическая функция. Тогда после завершения работы будет найдено кратчайшее расстояние до целевой вершины.
 
|proof=Когда A* завершает поиск, он, согласно определению, нашёл путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимым.
 
}}
 
  
===Оптимальность===
+
==Источники информации==
Любой другой алгоритм, использующий ту же эвристическую функцию <tex>h(v)</tex>, рассмотрит не меньше вершин, чем А*.
+
* С. Рассел, П. Норвиг {{---}} Искусственный интеллект. Современный подход, 2е издание
==Ссылки==
+
* [https://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Википедия {{---}} Алгоритм поиска A*]
*[http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Википедия:Алгоритм_поиска_A*]
+
* [https://en.wikipedia.org/wiki/A*_search_algorithm Wikipedia {{---}} A* search algorithm]
*[http://en.wikipedia.org/wiki/A*_search_algorithm Wikipedia:A*_search_algorithm]
+
* [http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей]
*[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*]
*[http://dl.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM Generalized best-first search strategies and the optimality of A*]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах ]]
 
[[Категория: Кратчайшие пути в графах ]]

Версия 18:53, 12 января 2016

Алгоритм А* (англ. 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]

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

Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит
Пример А* на сетке с возможностью ходить в восьми напрвлениях
от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.
  • Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние
    [math]h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|[/math].
  • Расстояние Чебышева применяется когда к четырем направлениям добавляются диагонали:
    [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 вершины
            tentative_score = g[current] + d(current, v)          // d(current, v) — стоимость пути между current и v 
            if [math]v \in U[/math] and tentative_score >= g[v]
                continue
            if [math]v \notin U[/math] or tentative_score < g[v]
                parent[v] = current
                g[v] = tentative_score
                f[v] = g[v] + h(v)
                if [math]v \notin Q[/math]
                    Q.push(v)
    return false

См. также

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