Алгоритм A*

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

Описание

В процессе работы алгоритма для вершин рассчитывается функция [math]f(v) = g(v) + h(v)[/math], где

• [math]g(v)[/math] — наименьшая стоимость пути в [math]v[/math] из стартовой вершины,
• [math]h(v)[/math] — эвристическое приближение стоимости пути от [math]v[/math] до конечной цели. [math]h(v)[/math] должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели.

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

Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит

Пример А* на сетке с возможностью ходить в восьми напрвлениях

от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой.

• Если мы можем перемещаться в четырех направлениях, в качестве эвристики стоит выбрать манхэттенское расстояние
  [math]h(v) = |{v.x-goal.x}| + |{v.y-goal.y}|[/math].

• Расстояние Чебышева применяется когда к четырем направлениям добавляются диагонали:
  [math]h(v) = \max{(|{v.x-goal.x}|, |{v.y-goal.y}|)}[/math].

• Если передвижение не ограниченно сеткой, то можно использовать евклидово расстояние по прямой:
  [math]h(v) = \sqrt{(v.x-goal.x)^2 + (v.y-goal.y)^2}[/math].

Также стоит обратить внимание на то как соотносятся [math]f(v)[/math] и [math]h(v)[/math]. Если они измеряются в разных величинах (например, [math]g(v)[/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]) // можно улучшить расстояние до y                
                    tentative_is_better = true   
                else
                    tentative_is_better = false  
            if (tentative_is_better == true) // найден новый, более короткий путь до y                          
                parent[y] = x;
                g[y] = tmp;
                f[y] = g[y] + h[y];            
    return failure; // Наша цель недостижима из start

Свойства

Корректность

Если [math]h(v)[/math] всегда меньше либо равна истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм.

Теорема:

Пусть G - граф, h(v) - допустимая эвристическая функция. Тогда после завершения работы будет найдено кратчайшее расстояние до целевой вершины.

Доказательство:

[math]\triangleright[/math]

Когда A* завершает поиск, он, согласно определению, нашёл путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимым.

[math]\triangleleft[/math]

Оптимальность

Любой другой алгоритм, использующий ту же эвристическую функцию [math]h(v)[/math], рассмотрит не меньше вершин, чем А*.

Ссылки

• Википедия:Алгоритм_поиска_A*
• Wikipedia:A*_search_algorithm
• Статья о поиске кратчайших путей
• Generalized best-first search strategies and the optimality of A*