Алгоритм A*
Алгоритм А* (англ. A star) — алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Описание
В процессе работы алгоритма для вершин рассчитывается функция , где
- — наименьшая стоимость пути в из стартовой вершины,
- — эвристическое приближение стоимости пути от до конечной цели.
Фактически, функция — длина пути до цели, которая складывается из пройденного расстояния и оставшегося расстояния . Исходя из этого, чем меньше значение , тем раньше мы откроем вершину , так как через неё мы предположительно достигнем расстояние до цели быстрее всего.
Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению . А* действует подобно алгоритму Дейкстры и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.
Свойства
Чтобы A* был оптимален, выбранная функция должна быть допустимой эвристической функцией.
| Определение: |
| Говорят, что эвристическая оценка допустима, если для любой вершины значение меньше или равно весу кратчайшего пути от до цели. |
Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле.
Второе, более сильное условие — функция должна быть монотонной.
| Определение: |
| Эвристическая функция называется монотонной (или преемственной), если для любой вершины и ее потомка разность и не превышает фактического веса ребра от до , а эвристическая оценка целевого состояния равна нулю. |
| Теорема: |
Любая монотонная эвристика допустима, однако обратное неверно. |
| Доказательство: |
|
Пусть — длина кратчайшего пути из вершины до цели.
Докажем индукцией по числу шагов до цели, что . Таким образом, монотонная эвристика допустима. |
| Утверждение: |
Если монотонна, то последовательность значений на любом пути неубывает. |
|
Доказательство следует из определения монотонности. Следовательно, . |
| Утверждение: |
Алгоритм A* является оптимальным, если функция монотонна. |
| Последовательность вершин "развёрнутых" во время работы алгоритма находится в неубывающем порядке значений . Поэтому очередная выбираемая вершина должна представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими. |
Примеры эвристик
- Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние[1]
.
- Расстояние Чебышева[2] применяется, когда к четырем направлениям добавляются диагонали:
.
- Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:
.
Также стоит обратить внимание на то как соотносятся и . Если они измеряются в разных величинах (например, — это расстояние в километрах, а — оценка времени пути в часах) А* может выдать некорректный результат.
Реализация
В приведённой реализации:
- — множество вершин, которые требуется рассмотреть,
- — множество рассмотренных вершин,
- — значение эвристической функции "расстояние + стоимость" для вершины ,
- — стоимость пути от начальной вершины до ,
- — эвристическая оценка расстояния от вершины до конечной вершины.
На каждом этапе работы алгоритма из множества выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество .
Псевдокод:
bool A*(start, goal):
U =
Q =
Q.push(start)
g[start] = 0
f[start] = g[start] + h(start)
while Q.size() != 0
current = вершина из с минимальным значением
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 and tentativeScore >= g[v]
continue
if or tentativeScore < g[v]
parent[v] = current
g[v] = tentativeScore
f[v] = g[v] + h(v)
if
Q.push(v)
return false
См. также
Примечания
Источники информации
- С. Рассел, П. Норвиг — Искусственный интеллект. Современный подход, 2е издание
- Википедия — Алгоритм поиска A*
- Wikipedia — A* search algorithm
- Статья о поиске кратчайших путей
- Generalized best-first search strategies and the optimality of A*
