Алгоритм A*
Алгоритм А*("A star", "А звёздочка") -- информированный алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Эвристика
Все вершины графа перевзвешиваются и f(v) = g(v) + h(v), где g(v) - наименьшая стоимость пути в v из стартовой вершины, h(v) - эвристическое приближение стоимости пути от v до конечной цели. h(v) должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторй картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
Псевдокод
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])
tentative_is_better := true
else
tentative_is_better := false
if (tentative_is_better == true)//
{
parent[y] = x;
g[y] = tmp;
f[y] = g[y] + h[y];
}
}
}
return failure; // Наша цель недостижима из start
}
Доказательство оптимальности и корректности
Алгоритм A* и допустим, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершину. Оптимистичной в том смысле, что, если он пойдёт через эту вершину, у алгоритма «есть шанс», что реальная стоимость результата будет равна этой оценке, но никак не меньше. Но, поскольку A* является информированным алгоритмом, такое равенство может быть вполне возможным.
Когда A* завершает поиск, он, согласно определению, нашёл путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимым.
Предположим теперь, что некий алгоритм B вернул в качестве результата путь, длина которого больше оценки стоимости пути через некоторую вершину. На основании эвристической информации, для алгоритма B нельзя исключить возможность, что этот путь имел и меньшую реальную длину, чем результат. Соответственно, пока алгоритм B просмотрел меньше вершин, чем A*, он не будет допустимым. Итак, A* проходит наименьшее количество вершин графа среди допустимых алгоритмов, использующих такую же точную (или менее точную) эвристику.
