尋找具有最低價值的節點以在具有啓發式的A星中展開的節點的最有效方式是什麼？

即時通訊利用星型算法做8個難題求解器。我在這個求解器中實現了曼哈頓和錯誤的啓發函數。在某些情況下，求解器工作正常。但在某些情況下，找到解決方案需要很長時間。我認爲我的問題之一是在查找打開列表中最低值的節點的功能（等待擴展）。尋找具有最低價值的節點以在具有啓發式的A星中展開的節點的最有效方式是什麼？

a part of psedocode(from wiki) 
while openset is not empty 
    x := the node in openset having the lowest f_score[] value 
    if x = goal 
     return reconstruct_path(came_from, came_from[goal]) 
    ................................

那麼尋找最低f_score值的最佳方法是什麼？只需找到最小值，或者當我們有一個要添加的狀態時（我們添加狀態時對列表進行排序），我們就必須修改列表，因此最小值將位於第一個位置。

來源

2011-04-05 khpn

保持heap。

鑑於n元素，你可以把他們變成堆。一旦它們成堆，您可以在時間O(log(n))中添加和刪除元素，並且您可以在時間上找到最小元素O(1)。

要實現一個你需要的是一個數組。根節點是0，而ithth之下的節點是2*i+1和2*i + 2。堆狀況是每個節點都比它上面的節點小。最小的始終是根。要添加一個元素，只需將它推到數組上，並讓它「跌倒」到其自然水平。要移除一個元素，取出根元素，將最後一個元素從數組中取出，放在根上，讓它「冒泡」到正確的位置。（在「冒泡」階段，您將它與兩個子節點中較小的節點進行交換，直到它最終在其下面沒有更小的子節點。）要有效地創建數組，您需要從中間元素開始，讓每個元素「冒泡向上」。此操作看起來像O(n log(n))，但仔細分析表明它只有O(n)。

來源

2011-04-05 00:35:21 btilly

在這種情況下，您使用堆作爲[優先隊列]（http://en.wikipedia.org/wiki/Priority_queue）。您選擇的語言可能已經提供了一個優先隊列，比自己維護一個二進制堆更有效。 – DataWraith 2011-04-05 11:03:25

@DataWraith好點。然而，@khpn可能試圖爲了教育目的而實施8難題求解器。編寫自己的堆是一種教育體驗。 – btilly 2011-04-05 13:38:53

尋找具有最低價值的節點以在具有啓發式的A星中展開的節點的最有效方式是什麼？

回答

相關問題