内存使用在迭代式深化DFS（ID-DFS）和BFS

我正在读的演讲中https://www.ics.uci.edu/~welling/teaching/271fall09/UninformedSearch271f09.pdf 内存使用在迭代式深化DFS（ID-DFS）和BFS

在BFS的内存使用情况是O（B^d + 1），和在ID-存储器使用DFS是O（bd）。

有一件事我想检查，为什么ID-DFS不存储所有访问的节点？

我弄清楚的原因是它只需要存储路径和它在路径上展开的节点。对于已经访问过的路径之外的其他节点，可以从树中丢弃（将它们从内存中释放），因为这些节点不会从根节点指向目标节点。

对于BFS，因为我们不知道解决方案在哪里，所以我们不能丢弃我们访问过的节点，直到找到解决方案。

以上是否正确或错误？据我所知，在ID-DFS中，当访问一个节点时，我们应该生成它的所有合法的孩子，比如说n个孩子，并且访问第一个孩子n1。对于第二个孩子n2，它将被访问，直到有限深度DFS搜索完n1。这就是为什么ID-DFS中的内存使用量为O（bd），分支因子乘以深度的原因。对于某些不需要在访问节点时生成所有子节点的应用程序，它可以生成第一个子节点;对于第二个孩子，它可以在搜索n1并返回后生成。对于这种修改，它只需要存储路径，因此其内存使用量为O（d）。

来源

2017-07-07 user3148602

是的，除了您的含义是“等待”由DFS搜索的含义是模糊的。IDFS的唯一成本是为根路径中的每个节点存储某种迭代器（例如，指向子指针数组的索引）。 – Gene

感谢您的评论，我修改了一些单词以使其更全面（我希望），并添加了一些注释来讨论它的内存使用情况。 – user3148602

我假设这是一个AI课程的介入。

让我们首先确定我们正在讨论树搜索而不是图搜索。在树状搜索中，你只需要一个边缘，而在图形搜索中你需要一个边缘和一个接近的集合。边缘将是一个普遍的pripority队列来存储要访问的节点。对于BFS和DFS分别可以分别排队和堆栈。对于图搜索，close集将用于存储所有子节点已访问过的节点，以删除不必要的重复搜索。

考虑一个搜索树，每个节点都有b子节点和m层。

时间复杂度：DFS需要O(b^m)找到一个解决方案，而BFS需要O(b^s)找到一个解决方案，其中s是最浅解决方案的深度。

空间复杂度：这里的空间复杂度是指边缘将会消耗的最大尺寸。 DFS只需要O(bm)因为它只需要将slibing节点存储路径根上，而BFS大致需要的最后一层，即O(b^s)

这里有插图DFS VS BFS：

我们可以很容易地看到，在大多数情况下，使用BFS比使用DFS找到一个解决方案更快，但DFS占用的内存比BFS少。因此，ID-DFS只不过是BFS和DFS的组合。因此，要搜索深度d，内存消耗与DFS相同，即O(bd)。

来源

2017-07-17 19:48:37

感谢您的回答，还有一个问题：为什么我们不需要存储在BFS中生成的所有节点？您推断“BFS取O（b^s）”，而所有生成的节点为1 + b + b^2 + b^3 + ... b^s = 0（b ^（s + 1））。我认为我们需要存储所有生成的节点，然后我们可以知道如何在找到时找到解决方案。 – user3148602

你是什么意思所有生成的节点？ –

@ user3148602这里假定最浅的解决方案是在's'深度。所以边缘的**最大**尺寸是“O（b^s）”，它大致是深度为's'的节点的数量。之前的任何节点都已经从边缘弹出，因此它不会导致最大的内存消耗。 –

内存使用在迭代式深化DFS（ID-DFS）和BFS

回答

相关问题