2

我试图根据维基百科的伪代码实现一个简单的 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
4

1 回答 1

3

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

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

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

于 2012-11-27T16:50:15.417 回答