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

Ссылки

• Алгоритм_поиска_A* Википедия
• A*_search_algorithm Wikipedia
• Статья о поиске кратчайших путей и различных оптимизациях А* в частности
• Статья на ACM Digital Library