我一直在阅读关于迭代加深的内容，但我不明白它与深度优先搜索有什么不同。
我的理解是深度优先搜索会不断地向更深层搜索。
在迭代加深中，你会设定一个层数值，如果在该层级没有找到解决方案，你会增加这个数值，然后从头（根节点）重新开始。
这不就和深度优先搜索一样了吗？
我的意思是你会不断地增加层数，不断地向更深层搜索，直到找到解决方案。我认为这和深度优先搜索是一样的！我会沿着相同的分支向下搜索，因为如果我从头重新开始，我也会沿着之前的那个分支向下搜索。
回答：
在深度优先搜索中，你从图中的某个节点开始，不断地向图中更深层探索，只要你能找到尚未到达的新节点（或者直到找到解决方案）。任何时候，DFS 无法继续前进时，它会回溯到最近一个可以做出不同选择的点，然后从那里开始探索。如果你的图非常大，并且只有一个解决方案，这可能会是一个严重的问题，因为你最终可能会沿着一条 DFS 路径探索整个图，最终在查看每个节点后才找到解决方案。更糟糕的是，如果图是无限的（例如，你的图由所有数字组成），搜索可能不会终止。此外，一旦找到你要寻找的节点，你可能没有找到到达该节点的最佳路径（你可能在图中循环了很长时间来寻找解决方案，即使它就在起始节点旁边！）
解决此问题的一个潜在方法是限制 DFS 所采用的任何一条路径的深度。例如，我们可以进行 DFS 搜索，但如果遇到的路径长度大于 5，则停止搜索。这确保了我们永远不会探索距离起始节点大于 5 的节点，这意味着我们永远不会无限地探索，或者（除非图非常密集）我们不会搜索整个图。但是，这确实意味着我们可能找不到我们正在寻找的节点，因为我们不一定探索整个图。
迭代加深背后的思想是使用第二种方法，但不断增加每个级别的深度。换句话说，我们可能会尝试使用长度为 1 的所有路径进行探索，然后是长度为 2 的所有路径，然后是长度为 3 的路径，等等，直到我们最终找到所讨论的节点。这意味着我们永远不会沿着无限的死胡同路径进行探索，因为每条路径的长度在每个步骤都受到限制。这也意味着我们找到了到达目标节点的最短路径，因为如果我们未能在深度 d 找到该节点，但在深度 d + 1 找到了它，则不可能存在长度为 d 的路径（否则我们就会采用它），因此长度为 d + 1 的路径确实是最佳的。
这与 DFS 的不同之处在于，它永远不会遇到在图中采取非常长且迂回的路径而永远无法终止的情况。路径的长度始终受到限制，因此我们永远不会探索不必要的分支。
这与 BFS 的不同之处在于，在 BFS 中，你必须一次将所有边缘节点保存在内存中。这需要 O(bd) 的内存，其中 b 是分支因子。将其与迭代加深中的 O(d) 内存使用量进行比较（用于保存当前路径中每个 d 节点的状态）。当然，BFS 永远不会多次探索同一路径，而迭代加深可能会随着深度限制的增加而多次探索任何路径。然而，渐近地，两者具有相同的运行时间。BFS 在考虑了距离 d 处的所有 O(bd) 节点后，在 O(bd) 步内终止。迭代加深在每个级别使用 O(bd) 时间，总计为 O(bd)，但具有更高的常数因子。
简而言之：
- DFS 不能保证找到最佳路径；迭代加深可以。
- DFS 可能会在找到目标节点之前探索整个图；迭代加深只有在起始节点和结束节点之间的距离是图中的最大值时才会这样做。
- BFS 和迭代加深都在 O(bd) 时间内运行，但迭代加深可能具有更高的常数因子。
- BFS 使用 O(bd) 内存，而迭代加深仅使用 O(d)。
