Изменения

Алгоритм '''А*'''("A star", "А звёздочка") {{---}} информированный алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

*<tex>h(v)</tex> {{---}} эвристическое приближение стоимости пути от <tex>v</tex> до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку. Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.Чем меньше <tex>f(v)</tex>, тем раньше вершина будет открыта и исследована алгоритмом. Таким образом множество альтернативных путей хранится в очереди с приоритетом. А* действует подобно [[Алгоритм Дейкстры | алгоритму Дейкстры]] и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент являются наилучшими, причем алгоритм учитывает путь уже пройденный до текущей вершины.

tmp := g[x] + d[x,y] // Стоимость пути до yчерез х

if (tmp < g[y]) // можно улучшить расстояние до y tentative_is_better := true

tentative_is_better := false if (tentative_is_better == true)// найден новый, более короткий путь до y {