A*（A星）算法澄清解释

Question

A*（A星）算法澄清解释

3

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

- archenil

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BlueRaja - Danny Pflughoeft · Accepted Answer

“开放集”是我们选择“current”节点的集合-也就是说，它包含了所有我们可能有兴趣下一步查看的节点。“封闭集”是我们已经考虑过的节点的集合。通常情况下，我们不会实际使用一个封闭集，而是在每个“Node”上设置一个标志，命名为“HasBeenVisited”或类似的名称。

最初，“Open set”仅包含“start”，因此在第一次迭代中，我们将删除“start”，将其邻居添加到“Open set”中，并将“start”添加到“Closed set”中。然后，我们取出“Open set”中的下一个节点，添加其邻居等。

假设您的启发式方法是consistent，则一旦被移除，它们就不会再被添加到“open”集中。