A *（A Star）算法澄清

我試圖實現一個基於維基百科僞碼的簡單A *搜索程序。但是，它對於openset的解釋對我來說還不太清楚。我知道開始節點最初將添加到openset。但是，代碼執行會在remove current from openset處引發錯誤，這很有意義，因爲current在第一次迭代期間從未添加到openset。看來openset還需要在循環之前添加起始節點的8個鄰居。有人可以請指點我正確的方向嗎？A *（A Star）算法澄清

感謝，

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

來源

2012-11-27 archenil

的「開集」是一組節點，我們選擇從current - 也就是說，它包含了我們可能感興趣的看着旁邊的所有節點。「閉集」是我們已經考慮的節點集合。通常，我們只會在每個Node上設置一個標誌，名稱爲HasBeenVisited或類似的標誌，而不是實際的封閉標誌。

最初，開集只包含start，所以在第一次迭代我們刪除start，增加它的鄰居開集，並添加start到閉集。然後我們在開集的下一個節點，加上其鄰居，等

假設你的啓發是consistent，他們沒有得到重新添加到open設置一次刪除。

來源

2012-11-27 16:50:15

我們有算法處理不一致的啓發式嗎？我四處搜尋，但沒有任何進展。 – GabrielChu

A *（A Star）算法澄清

回答

相關問題