广度首次搜索和迭代性深化之间的差异

Question

我了解BFS和DFS，但是对于我的一生，我无法弄清迭代加深和BFS之间的区别。显然，迭代加深与DFS具有相同的内存使用率，但是我看不到这是怎么可能的，因为它只是像BF一样不断扩展。如果有人能澄清一下，那真是太棒了。

如果需要的话，可以处理：

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

据我了解，迭代加深会使DFS降至深度1，然后DFS将DFS降至2 ...向下到深度N，依此类推，依此类推，直到它没有更多的水平

例如，我认为那棵树会被阅读

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

我相信它几乎可以为每个级别的深度限制做一个单独的DFS并丢弃记忆。

Answer 2

从我对算法的理解来看，IDDF（迭代深度深度搜索）只是多次执行的深度优先搜索，从而加深了每次迭代中搜索的节点的水平。因此，内存需求与深度优先搜索相同，因为最大深度迭代只是完整的深度优先搜索。

因此，以您给出的树的示例，第一次迭代将访问节点A，第二个迭代将访问Nodes A，B和C，并且第三个迭代将访问树的所有节点。

这样实现的原因是，如果搜索有时间限制，那么该算法至少将对“良好得分”节点有所了解，如果它在完成完整的遍历之前达到了时间限制那个树。

这与广度优先的搜索不同，因为在每次迭代中，节点都会像在深度搜索中一样，而不是在广度优先的搜索中。通常，IDDFS算法可能会存储从每次迭代中找到的“最佳评分”节点。

Answer 3

内存使用情况是它在任何时候节省的最大节点数量。不是访问的节点的数量。

在任何时候，IDFS都需要在分支中仅存储节点。 BFS必须保存其搜索深度的所有节点。要查看效果，带有分支因子8而不是2的树，要搜索到3的深度，BFS需要存储一个大量的64个节点。 IDF只需要3个。

Answer 4

在每次迭代迭代搜索的迭代中，我们都有一个限制，我们使用DFS方法遍历图，但是，对于每次迭代的每个步骤，我们只需要跟踪从根到深度D的路径内的节点。这就是记忆中的节省。

例如，查看下图的最后一行。如果我们使用BFS，我们必须跟踪所有节点至深度2。但是，由于我们使用的是DFS，因此我们不需要将所有节点保留在记忆中，因为这两个节点已经访问过，所以我们不这样需要它们，或者还没有访问，因此我们稍后会添加。我们只是将路径保持到根（灰色路径）。

图片来自彼得·诺维格（Peter Norvig）和斯图尔特·罗素（Stuart Russel）的人工智能书籍