a *算法伪代码

我想在c中实现维基百科给出的*算法的伪代码，但我真的被困在了解什么是reconstruct_path函数，有人可以向我解释什么在这个函数中的变量（p ，p + current_node，set）表示？a *算法伪代码

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

谢谢

来源

2013-03-02 user2102173

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保存地图，您来自的节点。（将它视为有序的移动列表，直到达到解决方案节点为止更简单。使用映射代替性能问题列表）。

上面的线基本上意味着：

“现在，我将前往邻居节点请记住，我从达到目前节点未来的邻居节点。”

当达到goal节点，A*需要从start节点返回的动作列表中goal。因为您存储了came_from地图中的移动列表，所以您现在可以重建移动的列表（reconstruct_path）以达到它来自start节点。

来源

2013-03-02 18:06:28 Heisenbug

非常感谢您的回答，我还有一个问题：如果设置了came_from [current_node]，行中设置了什么？ – user2102173 2013-03-02 18:53:01

我认为它检查结束条件，因为它是一个递归函数。我认为语义是“是否came_from [current_node]是列表中的最后一个节点？” – Heisenbug 2013-03-02 19:00:36

谢谢，但是提到的是什么列表：openset或者closedset或者其他什么？ – user2102173 2013-03-02 19:06:18

你有一组节点，并在您的路径每个节点都可以“点”，它的前身（从你从这个节点传来的节点） - 这是came_from地图正在储存。

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

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

你可以看到，因为这个函数是递归的，所以在开始时它将包含一个元素 - 首先在你的路径中，这将是一个开始。然后，您将添加新元素，最后以goal元素结尾。你也可以这样看待：你的算法允许你找到从goal到start（你只需要按照你的节点的came_from）的路径。这个函数允许你遍历你的从start到goal的路径，谢谢你的递归，所以你最终应该列出一些排序，包含正确顺序的路径。

*按列表我是指代表一系列元素而不是一组元素的结构。

来源

2013-03-02 18:04:13

a *算法伪代码

回答

相关问题