0

考虑 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* 能够遵循由邻居生成的路径，但在某一点它能够切换......并从前一个开始返回它的步骤节点并走另一条路，即使废弃的路径没有穿过那条路......

在代码中，启用此环境的条件是什么？

4

1 回答 1

1

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

于 2011-02-23T21:43:14.830 回答