Алгоритм поиска A*

Алгоритмы поиска на графах
A* B* Алгоритм Беллмана — Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда — Уоршелла

Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.

Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.

Обобщением для него является двунаправленный эвристический алгоритм поиска.

История

В 1964 году Нильс Нильсон изобрел эвристический подход к увеличению скорости алгоритма Дейкстры. Этот алгоритм был назван А1. В 1967 году Бертрам Рафаэль сделал значительные улучшения по этому алгоритму, но ему не удалось достичь оптимальности. Он назвал этот алгоритм A2. Тогда в 1968 году Петр Э. Харт представил аргументы, которые доказывали, что A2 был оптимальным при использовании последовательной эвристики лишь с незначительными изменениями. В его доказательство алгоритма также включен раздел, который показывал, что новый алгоритм A2 был возможно лучшим алгоритмом, учитывая условия. Таким образом, он обозначил новый алгоритм в синтаксисе звездочкой, он начинается на А и включал в себя все возможные номера версий.

Описание алгоритма

Пустые кружки в узлах принадлежат открытому списку, красные/зеленые относятся к закрытому списку.

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья).

Псевдокод:

function A*(start,goal)
     % множество уже пройденных вершин
     var closed := the empty set
     % множество частных решений
     var q := make_queue(path(start))
     while q is not empty
         var p := remove_first(q)
         var x := the last node of p
         if x in closed
             continue
         if x = goal
             return p
         add x to closed
         % добавляем смежные вершины
         foreach y in successors(x)
             enqueue(q, p, y)
     return failure

Псевдокод с подробными комментариями:

 function A*(start,goal)
     closedset := the empty set    // Множество вершин, которые уже были обработаны(раскрыты)
     openset := {start}            // Множество вершин(очередь), которые предстоит обработать(раскрыть). 
                                       // Изначально здесь присутствует только начальная вершина start.
     path_map := the empty set     // Карта пройденных вершин. Используется функцией reconstruct_path
 
     //Заполняем свойства вершины start
     start.g := 0   // g(x). Стоимость пути от начальной вершины. У start g(x) = 0
     start.h := heuristic_cost_estimate(start, goal) // Эвристическая оценка расстояние до цели. h(x)
     start.f := start.g + start.h      // f(x) = g(x) + h(x)
 
     while openset is not empty
         x := вершина из openset имеющая самую низкую оценку f(x)
         if x = goal 
             return reconstruct_path(start,goal) //заполняем карту path_map
 
         remove x from openset // Вершина x пошла на обработку, а значит её следует удалить из очереди на обработку
         add x to closedset    // И добавить в список уже обработанных
         foreach y in neighbor_nodes(x) // Проверяем каждого соседа x
             if y in closedset          // Пропускаем соседей из закрытого списка
                 continue
 
             tentative_g_score := x.g + dist_between(x,y)  // Вычисляем g(x) для обрабатываемого соседа
 
             if y not in openset // Если сосед x ещё не в открытом списке - добавим его туда
                 add y to openset
                 tentative_is_better := true
             else               // Сосед был в открытом списке, а значит мы уже знаем его g(x), h(x) и f(x)
                 if tentative_g_score < y.g  
                     // Вычисленная g(x) оказалась меньше, а значит нужно будет обновить  g(x), h(x), f(x)
                     tentative_is_better := true   
                 else
                     // Вычисленная g(x) оказалась больше, чем имеющаяся в openset. 
                     // Это означает, что из вершины x путь через этого соседа дороже
                     // т.е. существует менее дорогой маршрут, пролегающий через этого соседа (из какой-то другой вершины, не из x)
                     // Поэтому данного соседа мы игнорируем
                     tentative_is_better := false 
 
             // Обновление свойств соседа. 
             if tentative_is_better = true
                 y.came_from := x //Вершина с которой мы пришли. Используется для реконструкции пути.
                 y.g := tentative_g_score
                 y.h := heuristic_cost_estimate(y, goal)
                 y.f := g_score[y] + h_score[y]
             // Обратите внимание, что если происходит обновление свойств - значит y(сосед x) 
             // так или иначе находится в openset.
             // Т.е. при следующей итерации внешнего цикла из openset будет извлечена вершина с наименьшей оценкой f(x)
             // Не исключено, что она окажется соседом нашего x, которого мы только что добавили.
             // В общем это самая важная особенность алгоритма А*
 
     return failure //управление передаётся сюда когда openset пуст, а goal не найден (путь найти не удалось)
 
// Заполняет карту path_map
// Путь можно проследить только от заданной вершины(чаще всего это goal) 
// к старту(каждая вершина имеет свойство came_from, чем мы и воспользуемся)
function reconstruct_path(start_node, goal_node)
// Добавляем в карту все вершины от finish_node до start_node.
     current_node := goal_node // поиск начинается от финиша
     while current_node <> NULL 
             path_map.add_node(current_node) // Добавить вершину в карту
             current_node := current_node.came_from
 
     return path_map

Пример на Delphi:

procedure SearchPath(x0, y0, x, y: Integer; PrintProc: TCurrentPoint);
type
  pNode = ^TNode;
  TNode = record
    Parent: pNode;
    Pos: TPoint;
    Weight: Integer;
    G: LongInt;
    H, F: Extended;
  end;
var
  i, j, k: Integer;
  OpenList, ClosedList: TList;
  NewNode, Current: pNode;
  FMin: Extended;
  isClosed, isOpen, Complete: Boolean;
begin
  OpenList := TList.Create;
  ClosedList := TList.Create;
  New(NewNode);
  NewNode^.Parent := nil;
  NewNode^.Pos := Point(x0, y0);
  NewNode^.G := 0;
  NewNode^.H := Sqrt(Sqr(x - x0) + Sqr(y - y0));
  NewNode^.F := NewNode^.G + NewNode^.H;
  OpenList.Add(NewNode);
  Complete := False;
  while (OpenList.Count > 0) and not Complete do
  begin
    FMin := 77000;
    Current := nil;
    for i := 0 to OpenList.Count - 1 do
      if pNode(OpenList[i])^.F < FMin then
      begin
        FMin := pNode(OpenList[i])^.F;
        Current := pNode(OpenList[i]);
      end;
    ClosedList.Add(Current);
    OpenList.Remove(Current);
    for i := Current^.Pos.X - 1 to Current^.Pos.X + 1 do
      for j := Current^.Pos.Y - 1 to Current^.Pos.Y + 1 do
      begin
        if (i = Current^.Pos.X) and (j = Current^.Pos.Y) then
          Continue
        else if not Complete then
          Complete := (i = x) and (j = y)
        else
          Break;
        isClosed := False;
        for k := ClosedList.Count - 1 downto 0 do //ищем в закрытом списке
          if (pNode(ClosedList[k])^.Pos.X = i) and (pNode(ClosedList[k])^.Pos.Y = j) then
          begin
            isClosed := True; //в закрытом списке
            Break;
          end;
        if isClosed then
          Continue;
        isOpen := False;
        for k := OpenList.Count - 1 downto 0 do //ищем в открытом списке
          if (pNode(OpenList[k])^.Pos.X = i) and (pNode(OpenList[k])^.Pos.Y = j) then
          begin
            isOpen := True; //в открытом списке
            if pNode(OpenList[k])^.G > (Current^.G + pNode(OpenList[k])^.Weight) then
            begin
              pNode(OpenList[k])^.Parent := Current;
              pNode(OpenList[k])^.G := Current^.G + pNode(OpenList[k])^.Weight;
              pNode(OpenList[k])^.F := pNode(OpenList[k])^.G + pNode(OpenList[k])^.H;
            end;
            Break;
          end;
        if not isOpen then //если еще не открыта
        begin
          //добавляем в открытый список
          New(NewNode);
          NewNode^.Parent := Current;
          NewNode^.Pos := Point(i, j);
          NewNode^.Weight := Weights[i, j];
          NewNode^.G := Current^.G + NewNode^.Weight;
          NewNode^.H := Sqrt(Sqr(x - i) + Sqr(y - j));
          NewNode^.F := NewNode^.G + NewNode^.H;
          OpenList.Add(NewNode);
        end;
      end;
  end;
  for i := OpenList.Count - 1 downto 0 do
    if (pNode(OpenList[i])^.Pos.X = x) and (pNode(OpenList[i])^.Pos.Y = y) then
    begin
      Current := OpenList[i];
      while Current <> nil do
      begin
        PrintProc(Current^.Pos.X, Current^.Pos.Y);
        Current := Current^.Parent;
      end;
    end;
  for i := OpenList.Count - 1 downto 0 do
    Dispose(OpenList[i]);
  OpenList.Free;
  for i := ClosedList.Count - 1 downto 0 do
    Dispose(ClosedList[i]);
  ClosedList.Free;
end;

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

Пример

Примером алгоритма A* в действии, где узлы – это города, связанные дорогами и Н (х) является самым коротким расстоянием до целевой точки:

Ключ: зеленый - начало, синий - цель, оранжевый - посещенные узлы.

Примечание: Этот пример использует запятую как десятичный разделитель.

Свойства

Как и алгоритм поиска в ширину, A* является полным в том смысле, что он всегда находит решение, если таковое существует.

Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. (Монотонность также известна как неравенство треугольника: одна сторона треугольника не может быть длиннее, чем сумма двух других сторон.) Математически, для всех путей x, y (где y — потомок x) выполняется:

$g(x) + h(x) \le g(y) + h(y).$

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

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

Особые случаи

В общем говоря, поиск в глубину и поиск в ширину являются двумя частными случаями алгоритма A*. Для поиска в глубину возьмём глобальную переменную-счётчик С, инициализировав её неким большим значением. Всякий раз при раскрытии вершины будем присваивать значение счётчика смежным вершинам, уменьшая его на единицу после каждого присваивания. Таким образом, чем раньше будет открыта вершина, тем большее значение h(x) она получит, а значит, будет просмотрена в последнюю очередь. Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры.

Тонкости реализации

Существует несколько особенностей реализации и приёмов, которые могут значительно повлиять на эффективность алгоритма. Первое, на что не мешает обратить внимание — это то, как очередь с приоритетом обрабатывает связи между вершинами. Если вершины добавляются в неё так, что очередь работает по принципу LIFO, то в случае вершин с одинаковой оценкой A* «пойдёт» в глубину. Если же при добавлении вершин реализуется принцип FIFO, то для вершин с одинаковой оценкой алгоритм, напротив, будет реализовывать поиск в ширину. В некоторых случаях это обстоятельство может оказывать существенное значение на производительность.

В случае, если по окончании работы от алгоритма требуется маршрут, вместе с каждой вершиной обычно хранят ссылку на родительский узел. Эти ссылки позволяют реконструировать оптимальный маршрут. Если так, тогда важно, чтобы одна и та же вершина не встречалась в очереди дважды (имея при этом свой маршрут и свою оценку стоимости). Обычно для решения этой проблемы при добавлении вершины проверяют, нет ли записи о ней в очереди. Если она есть, то запись обновляют так, чтобы она соответствовала минимальной стоимости из двух. Для поиска вершины в сортирующем дереве многие стандартные алгоритмы требуют времени O(n). Если усовершенствовать дерево с помощью хеш-таблицы, то можно уменьшить это время.

Почему A* допустим и оптимален

Алгоритм A* и допустим, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершину. Оптимистичной в том смысле, что, если он пойдёт через эту вершину, у алгоритма «есть шанс», что реальная стоимость результата будет равна этой оценке, но никак не меньше. Но, поскольку A* является информированным алгоритмом, такое равенство может быть вполне возможным.

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

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

Оценка сложности

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

$|h(x) - h^*(x)| \leq O(\log h^*(x))$;

где h* — оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели. Другими словами, ошибка h(x) не должна расти быстрее, чем логарифм от оптимальной эвристики.

Но ещё бо́льшую проблему, чем временна́я сложность, представляют собой потребляемые алгоритмом ресурсы памяти. В худшем случае ему приходится помнить экспоненциальное количество узлов. Для борьбы с этим было предложено несколько вариаций алгоритма, таких как алгоритм A* с итеративным углублением (iterative deeping A*, IDA*), A* с ограничением памяти (memory-bounded A*, MA*), упрощённый MA* (simplified MA*, SMA*) и рекурсивный поиск по первому наилучшему совпадению (recursive best-first search, RBFS).

Примеры использования

Классическим примером служит игра Lines (Color Lines, в народе Шарики), изобретённая Олегом Дёминым, Геннадием Денисовым и Игорем Ивкиным и разработанная российской компанией Gamos в 1992 году.

В данной игре на экране показано квадратное поле 9×9 клеток, в случайные клетки на котором программа выставляет три шарика разных цветов. Всего 7 возможных цветов. За один ход игрок может передвинуть один шарик, выделив его и указав его новое местоположение. Для совершения хода необходимо, чтобы между начальной и конечной клетками существовал путь из свободных клеток. Цель игры состоит в удалении максимального количества шариков, которые исчезают при выстраивании шариков одного цвета по пять и более в ряд (по горизонтали, вертикали или диагонали). При исчезновении ряда шариков новые три шарика не выставляются. В остальных случая каждый ход выставляются новые три шарика. Игрок может видеть заранее три шарика, которые появятся в следующем ходу.

Литература

• Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. — М.: Мир, 1991. — С. 238—244. — 20 000 экз, экз. — ISBN 5-03-001408-X
• Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. — 2-е изд.. — М.: Вильямс, 2006. — С. 157—162. — 3 000 экз, экз. — ISBN 5-8459-0887-6
• Нильсон Н. Искусственный интеллект: методы поиска решений = Problem-solving Methods in Artificial Intelligence / Пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. — М.: Мир, 1973. — С. 70 — 80.
• Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. — 1985. — Т. 32. — № 3. — С. 505 — 536.
• Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. — 1968. — № 2. — С. 100 — 107.
• Hart P. E., Nilsson, N. J., Raphael, B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. — 1972. — Т. 37. — С. 28 — 29.
• Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. — Addison-Wesley, 1984. — ISBN 0-201-05594-5

Ссылки

• A* Подробное описание алгоритма А*
• A* построение пути со сглаживанием и реалистичными поворотами — Автор Marco Pinter
• A* Explorer — программа для Windows, позволяющая пошагово просматривать работу A* алгоритма.
• Алгоритм A* — реализация на PHP и визуализация используя Google Map API.
• Amit’s Pages — О поиске пути и A*
• Cupper Принцип работы алгоритма поиска пути Астар (A*). GameDev.ru (17 января 2004 года). Архивировано из первоисточника 14 марта 2012. Проверено 22 июля 2009.