a *算法僞代碼

我想在c中實現維基百科給出的*算法的僞代碼，但我真的被困在瞭解什麼是reconstruct_path函數，有人可以向我解釋什麼在這個函數中的變量（p ，p + current_node，set）表示？a *算法僞代碼

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

     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 

function reconstruct_path(came_from, current_node) 
if came_from[current_node] in set 
    p := reconstruct_path(came_from, came_from[current_node]) 
    return (p + current_node) 
else 
    return current_node

謝謝

來源

2013-03-02 user2102173

came_from是導航節點的地圖，就像評論說的那樣。它可以通過多種方式實現，但一個經典的地圖應該可以用於這個目的（甚至列表也可以）。

如果您不熟悉地圖，請檢查std::map。

A*的目標是找到一個移動列表，它將解決給定的問題（表示爲一個圖）。解決方案是通過圖表的路徑。

在提出的僞代碼中，came_from存儲了您實際評估的解決方案的「歷史記錄」（因此可能是通過圖表的路徑）。

當你探索一個節點（新節點或者一個與已訪問列表成本更低）：

if neighbor not in openset or tentative_g_score < g_score[neighbor] 
    came_from[neighbor] := current

你在came_from保存地圖，您來自的節點。（將它視爲有序的移動列表，直到達到解決方案節點爲止更簡單。使用映射代替性能問題列表）。

上面的線基本上意味着：

「現在，我將前往鄰居節點請記住，我從達到目前節點未來的鄰居節點。」

當達到goal節點，A*需要從start節點返回的動作列表中goal。因爲您存儲了came_from地圖中的移動列表，所以您現在可以重建移動的列表（reconstruct_path）以達到它來自start節點。

來源

2013-03-02 18:06:28 Heisenbug

非常感謝您的回答，我還有一個問題：如果設置了came_from [current_node]，行中設置了什麼？ – user2102173 2013-03-02 18:53:01

我認爲它檢查結束條件，因爲它是一個遞歸函數。我認爲語義是「是否came_from [current_node]是列表中的最後一個節點？」 – Heisenbug 2013-03-02 19:00:36

謝謝，但是提到的是什麼列表：openset或者closedset或者其他什麼？ – user2102173 2013-03-02 19:06:18

你有一組節點，並在您的路徑每個節點都可以「點」，它的前身（從你從這個節點傳來的節點） - 這是came_from地圖正在儲存。

您希望您的a *函數返回路徑中的節點列表*。

現在回到return (p + current_node) - 此代碼基本上意味着返回一個列表，其中包含來自p的所有元素，並在最後包含current_node。所以這是p與1元素添加到p的末尾。

你可以看到，因爲這個函數是遞歸的，所以在開始時它將包含一個元素 - 首先在你的路徑中，這將是一個開始。然後，您將添加新元素，最後以goal元素結尾。你也可以這樣看待：你的算法允許你找到從goal到start（你只需要按照你的節點的came_from）的路徑。這個函數允許你遍歷你的從start到goal的路徑，謝謝你的遞歸，所以你最終應該列出一些排序，包含正確順序的路徑。

*按列表我是指代表一系列元素而不是一組元素的結構。

來源

2013-03-02 18:04:13

a *算法僞代碼

回答

相關問題