algorithm - 不知情搜索 : run breadth-first search followed by iterative deepening search on each node in the frontier

Question

我正在尝试结合广度优先搜索和迭代加深搜索。 AI 书 AI - 一种现代方法，第 3 章(第 90 页)中提到了这种方法。思路是从初始状态开始，进行广度优先搜索，直到达到某个恒定的内存限制mB，然后在前沿的每个节点上进行迭代加深搜索。

这个搜索算法可靠吗？完全的？最优？

Answer 1

广度优先搜索本身是可靠的、完整的和最优的。因此，对于 BFS 在达到内存限制之前已经找到解决方案的任何问题，都没有问题。在找到解决方案之前，我们只需要考虑在达到内存限制的情况下会发生什么，例如您将开始在前沿节点上运行 IDS 的问题:

声音？

是的，IDS 永远不会以某种方式返回不正确的结果。

完成了吗？

这取决于您如何实现“边界中每个节点上的 IDS”。

如果你先在frontier的第一个节点做一个完整的IDS，然后在frontier的第二个节点做一个完整的IDS，等等，是不完整的。考虑在边界的第一个节点下有一个无限大小的搜索空间的情况，其中不包含解决方案。如果您首先尝试在该节点上运行“完整的”IDS，它将永远不会终止。

但是，如果您以不同的方式将 IDS 进程分散到边界中的节点上，它就可以完成。例如，如果您首先对边界中的所有节点进行深度为 1 的 DFS，然后对边界中的所有节点进行深度为 2 的 DFS，依此类推，算法将完成。

最优？

这里的完整性同样重要。如果您在移动到第二个节点之前完成了边界中第一个节点的完整 IDS，您可能已经在边界中的第一个节点下方找到了一个次优解决方案，因此该算法将是次优的。

如果您在边界中的任何节点移动到深度限制为 2 的 DFS 过程之前完成边界中所有节点的深度限制为 1 的 DFS 过程，并在移动到深度之前完成所有这些过程限制为 3 等，算法将是最优的。