Алгоритм A*
Алгоритм А*("A star", "А звёздочка") — алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Описание
В процессе работы алгоритма для вершин рассчитывается функция , где
- — наименьшая стоимость пути в из стартовой вершины,
- — эвристическое приближение стоимости пути от до конечной цели. должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
Чем меньше , тем раньше вершина будет открыта и исследована алгоритмом. Таким образом множество альтернативных путей хранится в очереди с приоритетом. А* действует подобно алгоритму Дейкстры и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими, причем алгоритм учитывает путь уже пройденный до текущей вершины.
Псевдокод
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
}
Свойства
Корректность
Если всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.
Оптимальность
Любой другой алгоритм, использующий ту же эвристическую функцию , рассмотрит не меньше вершин, чем А*.
