Как A * может отказаться от неэффективного пути, следующего по лучшему?

Question

Рассмотрим алгоритм A *.

В Google можно найти хороший псевдокод:

function A*(start,goal)
     closedset := the empty set                 // The set of nodes already evaluated.     
     openset := set containing the initial node // The set of tentative nodes to be evaluated.
     came_from := the empty map                 // The map of navigated nodes.
     g_score[start] := 0                        // Distance from start along optimal path.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x

                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
                 Update(closedset,y)  
                 Update(openset,y)  

     return failure

 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

Что ж, есть одна вещь, которую я не понимаю:ситуация на картинке:

Как A * может измениться с a-> b-> c на a-> d ... ???Ну, я имею в виду, A * начинается с узла и перемещается по узлам.В определенный момент узел имеет более одного соседа, хорошо, A * может следовать по пути, сгенерированному соседом, но в определенный момент он может переключиться ... и вернуться к своим шагам, начиная с предыдущегоузел и переходя на другую дорогу ДАЖЕ, если заброшенный путь не пересекает этот ...

В коде, каково условие, которое позволяет эту среду?

Answer 1

A * является обобщением алгоритма Дейкстры, который снова является обобщением поиска в ширину (BFS). Похоже, вы можете быть озадачены «переключением пути», потому что вы думаете о поисковой операции как о чем-то похожем на поиск в глубину (DFS). DFS следует до конца, затем немного возвращается назад и пробует другие пути, затем возвращается еще дальше и так далее. Это соответствует тому, как вы выполняете операцию поиска в реальной жизни (то есть, если вам нужно было найти выход из лабиринта). BFS, с другой стороны, поддерживает очередь узлов, которые она намеревается посетить. На каждой итерации он выбирает узел в начале очереди, проверяет своих соседей и добавляет непосещенных соседей в конец очереди. Затем он переходит к следующему узлу в начале очереди. Это невозможно сделать в реальной жизни, поскольку это потребует возможности телепортироваться между различными узлами. :-) Dijkstra и A * основаны на одной и той же идее, но вместо этого они используют очередь с приоритетами, в которой вы всегда выбираете «незаконченный» узел, ближайший к начальному узлу. Таким образом, эти алгоритмы фактически построены на идее всегда переключения путей: всегда исследуйте узел, который в настоящее время, кажется, предлагает лучший путь.