76
правок
Изменения
→Псевдокод
Все вершины графа перевзвешиваются и 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
}
==Доказательство оптимальности и корректности==
