a-star - A*(A星)算法说明

Question

我试图根据维基百科的伪代码实现一个简单的 A* 搜索程序。但是，它对 openset 的解释对我来说有些不清楚。我知道起始节点最初会添加到 openset 中。但是，代码执行在 remove current from openset 处抛出错误，这是有道理的，因为 current 在第一次迭代期间从未添加到 openset。似乎 openset 在循环之前还需要添加起始节点的 8 个邻居。有人可以指出我正确的方向吗？

谢谢，

 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)
         if neighbor in closedset
             continue
         tentative_g_score := g_score[current] + dist_between(current,neighbor)

         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

Answer 1

“开放集”是我们从中选择当前 的节点集 - 也就是说，它包含我们接下来可能感兴趣的所有节点。 “封闭集”是我们已经考虑过的节点集。通常，我们只是在每个 Node 上设置一个标志，而不是一个实际的封闭集，命名为 HasBeenVisited 或类似的名称。

最初，开放集仅包含start，因此在第一次迭代中我们删除start，将其邻居添加到开放集中，并添加start 到封闭集。然后我们获取开放集中的下一个节点，添加它的邻居等。

假设您的启发式是 consistent , 它们一旦被移除就不会被重新添加到 open 集合中。