Реализации алгоритмов/Алгоритм поиска A*

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

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

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

 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 := y.g + y.h
             // Обратите внимание, что если происходит обновление свойств - значит 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;

Ссылки[править]

Реализации на различных языках программирования
Доказательство правильности и полноты