如何實現AO *算法？

Question

我注意到當我們實現搜索算法時會使用一些數據結構。 例如，我們使用隊列來實現BFS，堆棧實現DFS和最小堆來實現A *算法。在這些情況下，我們不需要明確構建搜索樹。

但我找不到一個簡單的數據結構來模擬AO *算法的搜索過程。我想知道是否明確構建搜索樹是實現AO *算法的唯一方法？任何人都可以爲我提供有效的實施嗎？我非常感謝你的幫助。

Answer 1

聲明：我沒有實現AO *，因此我可能是錯的。

執行AO *不應該與A *不同。你使用堆而不是隻有一個節點，每個成員應該是一個節點向量（一個或多個節點）。在某種程度上，它取決於（和 - 或）規則如何給予你，但填充堆應該很容易。所以對第一個問題的答案是否定的，沒有必要明確地構造樹，因爲對於A *你不這樣做。記住一堆實際上是一個搜索樹的表示，所以你可以爭辯說，當你遍歷它時你確實構造了樹。關於

任何人都可以提供一個有效的實現嗎？

您需要通過提供至少一些僞代碼或甚至更好的代碼來顯示一些努力，以顯示如何使用您的攻擊問題。然後我們可以提出一些建議，如何通過改進數據結構來提高效率。