我引用自 人工智能：现代方法：

深度优先搜索的特性在很大程度上取决于使用的是图搜索版本还是树搜索版本。图搜索版本避免了重复状态和冗余路径，在有限状态空间中是完整的，因为它最终会扩展每个节点。另一方面，树搜索版本则不是完整的[…]。深度优先树搜索可以在不增加额外内存成本的情况下进行修改，以检查新状态与从根节点到当前节点的路径上的状态是否一致；这可以避免在有限状态空间中的无限循环，但不能避免冗余路径的增生。

我不明白为什么图搜索是完整的而树搜索不是，因为树本身就是一种特殊的图。

此外，我不太清楚“无限循环”和“冗余路径”之间的区别…

有人能解释一下吗？

附注：对于拥有这本书的人来说，这是第86页（第三版）。

回答：

深度优先树搜索可能会陷入无限循环，这就是它不“完整”的原因。图搜索会记录已经搜索过的节点，因此可以避免陷入无限循环。

“冗余路径”是指从同一个起始节点到同一个结束节点的不同路径。图搜索仍然会探索所有这些冗余路径，但一旦到达之前访问过的节点，它就不会继续前进，而是会回溯并寻找尚未尝试的其他路径。

这与“无限循环”不同，后者是从一个节点回到自身的路径。

针对你的评论，请看你刚刚发布的引用：

深度优先树搜索可以在不增加额外内存成本的情况下进行修改，以检查新状态与从根节点到当前节点的路径上的状态是否一致。

因此，虽然深度优先树搜索确实会记录从根节点到当前节点的路径，以避免无限循环，但每次访问新节点时，它需要对该路径进行线性搜索。如果你编写了一个不进行此检查的深度优先树搜索实现，它可能会陷入无限循环。

你是对的，书中关于“冗余路径增生”的说法与完整性无关。它只是指出了图搜索和树搜索之间的一个区别。因为树搜索只记录当前路径，它可以在同一次搜索中多次经过同一条路径（即使进行了我刚才提到的检查）。

假设你的根节点有两个分支。每个分支都通向同一个节点，该节点有一条长路径从它延伸出去。树搜索将沿着那条长路径走两次，一次对应于通向它的两个分支中的每一个。这就是作者想要指出的。