Редактирование: Алгоритм A*

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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> из стартовой вершины,  
*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели.  
+
*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</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>. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.
+
<br clear="all">
+
[[Файл:Astar_progress_animation.gif|thumb|right|Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.]]
 +
void A*(start,goal)  
 +
{
 +
    closed := {}; // Множество вершин расстояние до которых мы уже оценили
 +
    open.push(start);// Очередь с приоритетом
 +
    f[start] = g[start] + h[start];
 +
    parent[start] = start;
 +
    while (open.size() != 0)
 +
    {
 +
        x := open.pop();
 +
        if (x == goal)
 +
            return succsess(x);// Кратчайший путь найден       
 +
        closed.push(x); 
 +
        for (y : xy in E)
 +
        {
 +
            if (y in closed)     
 +
                continue;
 +
            tmp := g[x] + d[x,y]  // Стоимость пути до y через х
 +
            if (y not in open)
 +
            {
 +
                open.push(y);
 +
                tentative_is_better = true;
 +
            }
 +
            else           
 +
                if (tmp < g[y]) // можно улучшить расстояние до y               
 +
                    tentative_is_better = true 
 +
                else
 +
                    tentative_is_better = false 
 +
            if (tentative_is_better == true) // найден новый, более короткий путь до y
 +
            {                             
 +
                parent[y] = x;
 +
                g[y] = tmp;
 +
                f[y] = g[y] + h[y];
 +
            }
 +
        }
 +
    }
 +
    return failure; // Наша цель недостижима из start
 +
}
 
==Свойства==
 
==Свойства==
Чтобы A* был оптимален, выбранная функция <tex>h(v)</tex> должна быть '''допустимой''' эвристической функцией.
+
===Корректность===  
{{Определение
+
Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.
|definition=Говорят, что эвристическая оценка <tex>h(v)</tex> '''допустима''', если для любой вершины <tex>v</tex> значение <tex>h(v)</tex> меньше или равно весу кратчайшего пути от <tex>v</tex> до цели.
+
===Оптимальность===
}}
+
Любой другой алгоритм, использующий ту же эвристическую функцию <tex>h(v)</tex>, рассмотрит не меньше вершин, чем А*.  
 
+
==Ссылки==
Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле. <br>
+
*[http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Алгоритм_поиска_A* Википедия]
Второе, более сильное условие {{---}} функция <tex>h(v)</tex> должна быть '''монотонной'''.
+
*[http://en.wikipedia.org/wiki/A*_search_algorithm A*_search_algorithm Wikipedia]
 
+
*[http://theory.stanford.edu/~amitp/GameProgramming/ Статья о поиске кратчайших путей и различных оптимизациях А* в частности]
{{Определение
+
*[http://dl.acm.org/citation.cfm?id=3830&coll=portal&dl=ACM Статья на ACM Digital Library, в которой подробно написано обоснование корректности алгоритма]
|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|Пример А* на сетке с возможностью ходить в восьми напрвлениях]] от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.
 
 
 
* Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние<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е издание
 
* [https://ru.wikipedia.org/wiki/Алгоритм_поиска_A* Википедия {{---}} Алгоритм поиска A*]
 
* [https://en.wikipedia.org/wiki/A*_search_algorithm Wikipedia {{---}} A* search 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*]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах ]]
 
[[Категория: Кратчайшие пути в графах ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)