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