Алгоритм A*

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

См. также

• Эвристики для поиска кратчайших путей
• Алгоритм Флойда
• Алгоритм Дейкстры
• Алгоритм Форда-Беллмана

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

• С. Рассел, П. Норвиг — Искусственный интеллект. Современный подход, 2е издание
• Википедия — Алгоритм поиска A*
• Wikipedia — A* search algorithm
• Статья о поиске кратчайших путей
• Generalized best-first search strategies and the optimality of A*