1

我正在尝试在 c 中实现 wikipedia 给出的 a* 算法的伪代码，但我真的坚持理解什么是reconstruct_path 函数，有人可以向我解释这个函数中的变量是什么（p，p+current_node，set）代表？

function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor] 
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

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

谢谢

4

2 回答 2

2

came_from就像评论说的那样，是导航节点的地图。它可以通过多种方式实现，但经典地图应该可以用于此目的（即使是列表也可以）。

如果您不熟悉地图，请查看 std::map。

的目标A*是找到一个移动列表，这将解决给定的问题（表示为图表）。解决方案是通过图形的路径。

在提议的伪代码中，came_from存储您实际评估的解决方案的“历史”（因此可能是通过图表的路径）。

当您探索一个节点（新节点或已访问列表中成本较低的节点）时：

if neighbor not in openset or tentative_g_score < g_score[neighbor] 
    came_from[neighbor] := current

您正在came_from地图中保存您来自的节点。（将其视为移动的有序列表更简单，直到到达解决方案节点。使用地图而不是列表来解决性能问题）。

上面的行基本上意味着：

"Now I'll visit neighbor node. Remember that I reached neighbor node coming from current node".

When goal node is reached, A* needs to return the list of moves from start node to goal. You have the reference to the goal node, so you can now recontruct the list(reconstruct_path) of moves to reach it coming from start node, because you stored the list of moves in came_from map.

于 2013-03-02T18:06:28.943 回答
0

您有一组节点，路径中的每个节点都可以“指向”其前身（您来自该节点的节点） - 这就是 come_from 地图存储的内容。

您希望您的 a* 函数返回路径中的节点列表*。

现在，回到return (p + current_node)- 这段代码基本上意味着返回一个列表，其中包含来自 p 的所有元素，最后是 current_node 。所以它的p末尾添加了 1 个元素p。

你可以看到，因为这个函数是递归的，所以一开始它将包含一个元素——首先在你的路径中，这将是一个开始。然后，您将向其中添加新元素，最后以goal元素结尾。

你也可以这样看：你的算法允许你找到一条从goal到的路径start（你只需要跟随came_from你的节点）。这个函数允许你遍历你的路径start，goal谢谢你的递归，所以你应该最终得到一个列表，其中包含正确顺序的路径。

*我所说的列表是指一些表示元素序列而不是集合的结构。

于 2013-03-02T18:04:13.907 回答