48

我一直在阅读有关迭代深化的内容，但我不明白它与深度优先搜索有何不同。

我明白深度优先搜索会越来越深入。

在迭代深化中，您建立一个级别的值，如果在该级别没有解决方案，则增加该值，然后从头开始（根）。

这和深度优先搜索不一样吗？

我的意思是你会不断增加和增加，更深入，直到找到解决方案。我认为这是同一件事！我会沿着同一个分支走，因为如果我从头开始，我会像以前一样沿着同一个分支走。

4

3 回答 3

99

在深度优先搜索中，您从图表中的某个节点开始，不断深入地探索图表，同时您可以找到尚未到达的新节点（或直到您找到解决方案）。每当 DFS 用完移动时，它就会回溯到可以做出不同选择的最新点，然后从那里开始探索。如果您的图非常大并且只有一个解决方案，这可能是一个严重的问题，因为您最终可能会沿着一条 DFS 路径探索整个图，只是在查看每个节点后才找到解决方案。更糟糕的是，如果图是无限的（例如，您的图可能包含所有数字），搜索可能不会终止。此外，一旦你找到你要找的节点，

解决此问题的一个潜在方法是限制 DFS 采用的任何一条路径的深度。例如，我们可能会进行 DFS 搜索，但如果我们采用长度大于 5 的路径，则停止搜索。这确保我们永远不会探索距离起始节点大于 5 的任何节点，这意味着我们永远不会探索无限或（除非图形非常密集）我们不搜索整个图形。但是，这确实意味着我们可能找不到我们正在寻找的节点，因为我们不一定要探索整个图。

迭代深化背后的想法是使用第二种方法，但要不断增加每个级别的深度。换句话说，我们可能会尝试使用所有长度为 1 的路径，然后是所有长度为 2 的路径，然后是长度为 3 的路径，等等，直到我们最终找到有问题的节点。这意味着我们永远不会沿着无限的死胡同探索，因为每条路径的长度在每一步都有一定的长度。这也意味着我们找到了到目标节点的最短路径，因为如果我们在深度 d 处没有找到节点，但在深度 d + 1 处找到了它，就不可能有长度为 d 的路径（或者我们会采取它），所以长度为 d + 1 的路径确实是最优的。

这与 DFS 不同的原因在于，它永远不会遇到这样的情况，即在图上绕着一个非常长且迂回的路径而不会终止。路径的长度总是有上限的，所以我们永远不会探索不必要的分支。

这与 BFS 不同的原因在于，在 BFS 中，您必须一次将所有边缘节点保存在内存中。这需要内存 O(b d )，其中 b 是分支因子。将此与迭代深化的 O(d) 内存使用情况进行比较（以保持当前路径中每个 d 节点的状态）。当然，BFS 永远不会多次探索同一条路径，而迭代深化可能会多次探索任何路径，因为它会增加深度限制。但是，渐近地两者具有相同的运行时间。在考虑距离 d 处的所有 O(b d ) 个节点后， BFS 在 O(b d ) 步中终止。迭代深化每个级别使用 O(b d ) 时间，总和为 O(b d )，但具有更高的常数因子。

简而言之：

  • DFS不能保证找到最优路径；迭代深化是。
  • DFS 可能会在找到目标节点之前探索整个图；仅当开始节点和结束节点之间的距离是图中的最大值时，迭代加深才会这样做。
  • BFS 和迭代深化都在 O(b d ) 时间内运行，但迭代深化可能具有更高的常数因子。
  • BFS 使用 O(b d ) 内存，而迭代深化仅使用 O(d)。

希望这可以帮助！

于 2011-09-13T02:01:38.290 回答
4

维基百科上有一个关于这个的不错的页面。

我认为您错过的基本思想是迭代深化主要是一种启发式. 当可能在根附近找到解决方案时，迭代深化会相对较快地找到它，而直接的深度优先搜索可能会做出“错误”的决定，并在没有结果的深层分支上花费大量时间。

（当搜索树可以是无限的时，这一点尤其重要。在这种情况下，它们的等效性甚至更低，因为 DFS 可能会永远卡住，而 BFS 或迭代深化肯定会在某一天找到答案（如果存在）

于 2011-09-13T02:02:02.923 回答
1

只是添加到这里已经存在的内容，但这里有一些来自丹佛大学移动人工智能实验室的视频，显示了这些差异。

http://movingai.com/dfid.html

您可以在他们的示例中看到，当目标很浅（解决方案深度 3，树深度）并且解决方案位于右侧时，迭代深化获胜，但无论解决方案位于最后一行，DFS 都会获胜。

我开始阅读有关国际象棋编程的文章，接下来我正在考虑静止搜索，如果您想了解更多有关 AI 编程的搜索策略的信息，请查看它。

于 2017-02-06T19:03:05.247 回答