Алгоритм 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
}
Свойства
Корректность
Если всегда меньше либо равна истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.
Оптимальность
Любой другой алгоритм, использующий ту же эвристическую функцию , рассмотрит не меньше вершин, чем А*.
