c - a*算法伪代码

Question

我正在尝试在 c 中实现维基百科给出的 a* 算法的伪代码，但我真的无法理解什么是 reconstruct_path 函数，有人可以向我解释这个函数中的变量是什么 (p, p+current_node , 集) 代表?

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

谢谢

Answer 1

came_from 是导航节点的 map ，如评论所述。它可以通过多种方式实现，但经典 map 应该可以满足此目的(即使是列表也可以)。

如果您不熟悉 map ，请查看 std::map .

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

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

当您探索一个节点(一个新节点或在已访问列表中成本较低的节点)时:

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

您正在 came_from 映射中保存您来自的节点。 (将其视为到达解决方案节点之前的有序移动列表更简单。使用 map 而不是性能问题列表)。

上面这行基本意思是:

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

当到达goal节点时，A*需要返回从start节点到goal的移动列表>。您有对 goal 节点的引用，因此您现在可以重新构建移动列表(reconstruct_path)以从 start 节点到达它，因为您将移动列表存储在 came_from map 中。