如何理解廣度優先搜索的內存問題分支和約束

Question

我被分支和綁定的方法混淆最近。有分支定界方法三種搜索策略：走向深沉優先搜索，廣度優先搜索和最佳優先搜索。所有的書籍和文獻指出廣度優先和最佳優先將使用的計算機的內存越多。如何理解這一點？採取二叉樹爲例，從現場節點列表來處理採取的節點（父節點）時，兩個子節點（或子節點）生成並插入到活節點列表，但父親節點應刪除，因此，只有一個節點的內存增加。從這個角度來看，所有三個搜索策略以計算機相同的回憶。 我對不對？它讓我困惑了很久。任何人都可以給我一些建議嗎？

Answer 1

好，

你能想到的數據結構：

廣度優先搜索： It's實現爲隊列。當你展開一個節點（父節點）時，你在隊列中包含子節點。父節點被刪除。 Let's做出了榜樣：

1. 展開：我們包括在隊列中20和70，並刪除45這樣：

   20 | 70

2. 展開：我們擴大從隊列中第一個節點，包括他的兒子：

   70 | 10 | 28

3. 展開：我們擴大從隊列中第一個節點，包括他的兒子：

   10 | 28 | 60 | 85

   等等...

正如你可以看到的空間複雜度是指數：O（）（B =支化因子; d =深度，初始爲0）

走向深沉優先搜索：它真實實現爲堆棧：

1. 展開：我們包括在堆棧20和70，並刪除45這樣：

   20 | 70

2. 展開：我們擴大從堆棧頂部的第一個節點，包括他的兒子：

   10 | 28 | 70

3. 展開：我們擴大從堆棧頂部的第一個節點，包括他的兒子：

   1 | 18 | 28 | 70

   等等......

現在空間複雜度爲線性：O（d）。兩種算法的時間複雜度都是O（）。

最佳優先搜索：排序根據啓發式評價函數F（N）的隊列和膨脹具有最佳F（N）的 succesor。空間複雜度是線性的：O（d）。

希望這會有所幫助。