search - 没有指定深度限制的迭代深化

Question

我有一个关于搜索技术迭代深化的问题。我的问题是，正常的深度优先搜索和没有指定深度限制的迭代深化有什么区别？所以我有一棵带有目标节点的树，但在我的迭代深化搜索中没有指定限制。这会输出与我进行常规深度优先搜索相同的遍历序列吗？

Answer 1

假设目标的深度级别为 3（根位于深度 = 0），并且它并非一直位于树的“左侧”（通过深度优先搜索可以立即找到它（ DFS））。

正常的 DFS 可能会花费大量时间在 4、5、6 等深度级别进行搜索，然后再“向上”移动“向右”树，然后最终在深度 3 处找到目标。深化，如果有一个深度 = 3 的目标，你永远不会浪费时间查看深度 = 4 的节点。这是因为迭代深化首先做一个深度限制为 1 的 DFS，然后是一个深度限制为 2 的 DFS ，最后是深度限制为 3 的 DFS（它将找到目标并因此终止搜索）。

请注意，在此示例情况下，广度优先搜索 (BrFS) 也不会在深度 4 处浪费时间，并且由于不重新执行之前已经完成的某些工作，可能会更快一些。不过，这将需要更多的内存。

迭代深化的另一个优点是它不会陷入无限长的路径中。现在在大多数实际情况下，一条无限长的路径无论如何都是不可能的，但这绝对是可能的。DFS 可能会陷入这样的无限路径。

最后，与 DFS 相比，Iterative Deepening 的一个优势在于它可以在由于处理时间耗尽而终止它时提供更有用的结果。这在游戏搜索算法中尤其重要（想想国际象棋引擎）。由于您明确指定您的情况有一个目标节点，我认为这与您无关，但如果您有兴趣，请告诉我，我也可以为这个优势写解释。