我了解 BFS 和 DFS，但是对于我的生活来说，我无法弄清楚迭代深化和 BFS 之间的区别。显然，迭代深化与 DFS 具有相同的内存使用量，但我无法看到这是怎么可能的，因为它只是像 BFS 一样不断扩展。如果有人能澄清那将是很棒的。
如果需要，可以处理的树：
A
/ \
B C
/ / \
D E F
问问题
36349 次
4 回答
20
据我了解，迭代深化将 DFS 降至深度 1 然后将 DFS 降至深度 2 ...直至深度 n ，依此类推，直到找不到更多级别
例如，我认为那棵树会被读取
read visited depth
A A 1
ABC ABAC 2
ABDCEF ABDBACECF 3
我相信它几乎是在为每个级别做一个具有深度限制的单独 DFS 并丢弃内存。
于 2010-06-08T01:06:37.267 回答
20
从我对算法的理解来看，IDDFS（iterative-deepening depth-first search）简单来说就是多次执行深度优先搜索，加深每次迭代时搜索到的节点的层次。因此，内存要求与深度优先搜索相同，因为最大深度迭代只是完整的深度优先搜索。
因此，对于您给出的树的示例，第一次迭代将访问节点 A，第二次迭代将访问节点 A、B 和 C，第三次迭代将访问树的所有节点。
这样做的原因是，如果搜索有时间限制，那么算法至少会知道如果它在完全遍历那个树。
这与广度优先搜索不同，因为在每次迭代中，访问节点就像在深度优先搜索中一样，而不是在广度优先搜索中。通常，IDDFS 算法可能会存储从每次迭代中找到的“最佳评分”节点。
于 2010-06-08T01:11:34.193 回答
6
内存使用量是它在任何时候保存的最大节点数。不是访问的节点数。
在任何时候，IDFS 只需要存储它正在扩展的分支中的节点。如果我们正在扩展 C（在您的例如），则只存储 A 和 C。BFS 必须保存它正在搜索的深度的所有节点。要查看效果，请使用分支因子为 8 而不是 2 的树。要搜索深度为 3，BFS 需要存储大量 64 个节点。IDFS 只需要 3 个。
于 2012-01-15T18:35:32.787 回答
4
在迭代深度搜索的每次迭代中，我们都有一个限制，我们使用 DFS 方法遍历图，但是，对于每次迭代的每一步，我们只需要跟踪从根到深度 d 的路径内的节点. 这就是内存的节省。
例如，看下图的最后一行。如果我们使用了 BFS，我们必须跟踪深度为 2 的所有节点。但是因为我们使用的是 DFS，所以我们不需要将所有节点都保存在内存中，因为其中一些节点已经被访问过，所以我们不需要需要它们，或者还没有访问过，所以我们稍后会添加它。我们只保留通往根的路径（灰色路径）。
图片来自 Peter Norvig 和 Stuart Russel 的《人工智能》一书
于 2018-09-27T06:06:39.660 回答