breadth-first-search - 如何理解分支定界中广度优先搜索的内存问题

Question

我最近对分支定界方法感到困惑。分支定界法有三种搜索策略：深度优先搜索、广度优先搜索和最佳优先搜索。所有书籍和文献都指出，广度优先和最佳优先将占用所用计算机的更多内存。这个怎么理解？以二叉树为例，当从活节点列表中取出一个节点（父节点）进行处理时，会生成两个子节点（或子节点）并插入活节点列表中，但是父节点应该被删除，因此，只有一个节点的内存增加。从这个角度来看，这三种搜索策略都占用了计算机的相同内存。我对吗？这让我困惑了很久。谁能给我一些建议？

Answer 1

出色地，

您可以考虑数据结构：

广度优先搜索：它被实现为一个队列。当您展开一个节点（父节点）时，您会将子节点包括在队列中。父节点被删除。让我们举个例子：

1. 展开45：我们在队列中包括 20 和 70 并删除 45 ，所以：

   20 | 70

2. 展开20：我们展开队列中的第一个节点并包括他的儿子：

   70 | 10 | 28

3. 展开70：我们展开队列中的第一个节点并包括他的儿子：

   10 | 28 | 60 | 85

   等等...

如您所见，空间复杂度是指数级的：O( )（b = 分支因子；d = 深度，最初为 0）

深度优先搜索：它被实现为堆栈：

1. 展开45：我们在堆栈中包含 20 和 70 并删除 45 ，因此：

   20 | 70

2. 展开20：我们展开栈顶的第一个节点并包括他的儿子：

   10 | 28 | 70

3. 展开10：我们展开栈顶的第一个节点并包括他的儿子：

   1 | 18 | 28 |70

   等等...

现在空间复杂度是线性的： O(d)。两种算法的时间复杂度都是 O(· )。

最佳优先搜索：根据启发式评估函数f(n)对队列进行排序，并扩展具有最佳f(n)的后继。空间复杂度是线性的：O(d)。

希望这可以帮助。