Алгоритм A*
Алгоритм А*("A star", "А звёздочка") — информированный алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Эвристика
В процессе работы алгоритма для вершин используется функция , где - наименьшая стоимость пути в из стартовой вершины, — эвристическое приближение стоимости пути от 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
}
