迭代加深vs深度優先搜索

Question

我一直在閱讀迭代加深，但我不明白它是如何與深度優先搜索不同。

我明白深度優先搜索越來越深入。

在迭代加深你建立一個公平的值，如果在該級別無解，你增加該值，並從頭開始（根）再次啓動。

難道這與深度優先搜索是一回事嗎？

我的意思是，你會不斷遞增，並且遞增，不斷深入，直到你找到一個解決方案。我認爲這是一回事！我會沿着同一個分支走，因爲如果我從頭開始重新開始，我會像以前一樣走下去。

Answer 1

在深度優先搜索，你開始在圖形中的某個節點，不斷探索越來越深入的圖形，而你可以發現你還沒有達到新的節點（或直到您找到解決方案）。任何時候DFS用完的動作，都會回到最後一點，在那裏做出不同的選擇，然後從那裏探索。如果圖形非常大並且只有一個解決方案，那麼這可能是一個嚴重的問題，因爲您可能最終會沿着一個DFS路徑瀏覽整個圖表，以便在查看每個節點後查找解決方案。更糟糕的是，如果圖形是無限的（也許你的圖形包含所有數字），搜索可能不會終止。此外，一旦你找到你要找的節點上，你可能沒有它的最佳路徑（你可以有循環遍佈尋找解決方案，即使它是旁邊的開始節​​點圖！）

解決此問題的一個可能方法是限制DFS採用的任何一條路徑的深度。例如，我們可能會進行DFS搜索，但是如果我們採用的路徑長度大於5，則停止搜索。這確保我們從不探索距離起始節點的距離大於5的任何節點，這意味着我們永遠不會探索（除非圖表非常密集），我們不搜索整個圖表。但是，這確實意味着我們可能找不到我們正在尋找的節點，因爲我們不一定會瀏覽整個圖。

迭代加深背後的想法是使用第二種方法，但不斷增加每個級別的深度。換句話說，我們可以嘗試使用長度爲1的所有路徑，然後是長度爲2的所有路徑，然後是長度爲3的路徑，直到我們最終找到有問題的節點。這意味着我們永遠不會結束探索無限的死路徑，因爲每個路徑的長度在每一步都被限制了一定的長度。這也意味着我們找到到達目的節點的最短路徑，因爲如果我們沒有在深度d找到節點但是在深度d + 1找到它，就不可能有長度爲d的路徑（或者我們會採取它），所以長度d + 1的路徑確實是最佳的。

的原因，這是從DFS不同的是，它從來沒有運行到哪裏它採用圖形圍繞一個極其漫長和曲折的路徑而沒有終止的情況。路徑的長度總是被限制的，所以我們永遠不會去探索不必要的分支。

其原因，這與BFS不同的是，在BFS，你必須保存所有內存中的邊緣節點一次。這需要內存O（b ^d），其中b是分支因子。將它與迭代加深（保持當前路徑中每個d節點的狀態）的O（d）內存使用情況進行比較。當然，BFS不會多次探索相同的路徑，而迭代深化可能會多次探索任何路徑，因爲它會增加深度限制。但是，漸近地，兩者具有相同的運行時間。考慮到距離d處的所有O（b ^d）節點後，BFS終止於O（b ^d）步驟。迭代加深使用O（b ^d）每個級別的時間，總計爲O（b ^d），但是具有較高的常數因子。

簡而言之：

• DFS不能保證找到最佳路徑;迭代深化是。
• DFS可能會在查找目標節點之前瀏覽整個圖形;如果開始和結束節點之間的距離是圖中的最大值，迭代加深只會執行此操作。
• BFS和迭代加深都運行在O（b ^d），但迭代加深具有較高的常數因子。
• BFS使用O（b ^d）內存，而迭代加深只使用O（d）。

希望這有助於！

Answer 2

關於此，wikipedia有一個不錯的頁面。

我認爲你錯過的基本思想是迭代加深主要是啓發式。當一個解決方案可能被發現接近根迭代深化時，會發現它相對較快，而直向深度優先搜索可能會做出「錯誤」的決定，並花費大量時間在無結果的深層分支上。

（這一點尤其重要，當搜索樹可以是無限的。在這種情況下，他們更不等同因爲DFS可以得到永遠困而BFS或迭代深化一定要找到答案如果有一天它的存在）

Answer 3

只需添加已有內容即可，但以下是來自丹佛大學移動AI實驗室的一些視頻，它們顯示了不同之處。

http://movingai.com/dfid.html

您可以在自己的例子中看到迭代深化勝當目標是淺（液的深度3，樹深度）和解決方案是正確的，但DFS勝無論什麼解決的辦法是在最後一行。

我進入了關於國際象棋程序設計的閱讀，接下來我正在考慮quiescence search如果您想了解更多關於AI編程搜索策略的信息，請檢查一下。