Алгоритм A*

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Эвристика

В процессе работы алгоритма для вершин используется функция [math]f(v) = g(v) + h(v)[/math], где [math]g(v)[/math] - наименьшая стоимость пути в v из стартовой вершины, [math]h(v)[/math] - эвристическое приближение стоимости пути от v до конечной цели. [math]h(v)[/math] должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку. К примеру, если [math](h(v) == 0)[/math], то А* превращается в Дейкстру . Если [math]h(v)[/math] всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.

Псевдокод

А* просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации(эвристическая функция) в данный момент похожи на наилучший, причем алгоритм учитывает путь уже пройденный до текущей вершин.

Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.
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* проходит наименьшее количество вершин графа среди допустимых алгоритмов, использующих такую же точную (или менее точную) эвристику.

Ссылки