A* 如何能够放弃一条效率较低的路径而选择一条更好的路径？

Question

考虑 A* 算法。

在谷歌中可以找到一个很好的伪代码：

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* 是 Dijkstra 算法的推广，它又是广度优先搜索 (BFS) 的推广。看起来您可能对“路径切换”感到困惑，因为您认为搜索操作类似于深度优先搜索（DFS）。 DFS 沿着一条路径到达终点，然后稍微回溯并尝试其他路径，然后进一步回溯，依此类推。这对应于您在现实生活中执行搜索操作的方式（即，如果您必须找到走出迷宫的路）。另一方面，BFS 维护一个它打算访问的节点队列。在每次迭代中，它从队列的前面挑选节点，检查其邻居并将未访问的邻居添加到队列的后面。然后继续处理队列前面的下一个节点。在现实生活中这是不可能做到的，因为它需要在不同节点之间传送的能力。 :-) Dijkstra 和 A* 基于相同的想法，但它们使用优先级队列，在其中您始终选择最接近起始节点的“未完成”节点。因此，这些算法实际上是围绕始终切换路径的想法构建的：始终调查当前似乎提供最佳路径的节点。