深度優先搜索打開和關閉列表

Question

我真的被困在當下，我瘋了。

用最簡單的術語來說，您何時停止使用深度優先搜索的打開和關閉列表？

是否打開和關閉每個節點，直到沒有節點？

請幫助，因爲我要在這裏doolally

謝謝

Answer 1

打開清單可幫助您在這兩個深度優先和廣度優先搜索到正確遍歷您的樹。一步一步思考算法。你在一個有很多孩子的節點中，你將會擴展其中的一個。擴展之後，應該有一種機制返回並繼續遍歷。打開列表爲您執行，並告訴您實際上是要展開的下一個節點。該算法僅澄清子插入列表中的順序。

而閉合列表通常會提高算法的速度。它阻止算法擴展預訪問節點。也許你到達節點A，該節點先前通過另一個分支擴展。這會讓你切斷這個分支並嘗試另一條路徑。

啓發式方法有助於擺脫死衚衕。在AI算法中，通常你會面臨許多浪費分支的問題。通過遍歷每一步，您可以將路徑成本添加到變量中，並且當您想要將展開的節點添加到打開的列表中時，考慮到它會幫助您永遠不會通過它們。否則，你將陷入陷阱並且算法掛起。

讓我用一個例子來解釋更多： 考慮遊戲15-puzzles。你將通過算法解決它，你必須檢查所有可能的方法。 （實際上你要製作一棵樹）。當您沿着樹中可能的方向移動瓷磚時，可以在下一級中反向移動瓷磚，對嗎？所以你永遠不會走出這樣的死衚衕，你的算法會掛起。

這是開放和封閉列表的解釋。你問到算法什麼時候結束。其實你會重複展開並添加到打開列表，直到你找到你的目標或者打開清單變空。