深度优先搜索的性质严重依赖于使用图搜索或树搜索版本。避免重复状态和冗余路径的图搜索版本对于有限状态空间是完全的，因为它最终会展开每个节点。另一方面，树搜索版本则不完整[...]。可以在不增加额外内存成本的情况下修改深度优先树搜索，以便检查从根到当前节点的路径上新状态是否与已经存在的状态相同；这避免了有限状态空间中的无限循环，但不能避免冗余路径的激增。
我不明白为什么图搜索可以是完整的，而树搜索却不能，因为树是特殊的图。
此外，我不清楚“无限循环”和“冗余路径”的区别...
能否有人解释一下这个问题？
注：对于那些拥有该书的人来说，这是第86页（第3版）。
深度优先树搜索可能会陷入无限循环，因此它不是"完备的"。图搜索会跟踪它已经搜索过的节点，因此可以避免跟随无限循环。
"冗余路径"是从同一起点到同一终点的不同路径。图搜索仍会探索所有这些冗余路径，但一旦到达它以前访问过的节点，它将不再继续向下探索，而是回退并寻找尚未尝试的其他路径。
这与"无限循环"不同，后者是一条从一个节点返回到自身的路径。
针对您的评论，请看一下您刚才发布的引用：
深度优先树搜索可以被修改，而不需要额外的内存成本，使其检查从根到当前节点的路径上的新状态。
因此，虽然深度优先树搜索确实会记录从根到当前节点的路径以避免无限循环，但它需要每次访问新节点时对该路径进行线性搜索。如果您编写了一个没有进行此检查的深度优先树搜索实现，则可能会陷入无限循环。
您是正确的，书中所说的"冗余路径的增殖"与完备性无关。它只是指出了图搜索和树搜索之间的差异。因为树搜索仅跟踪当前路径，所以即使进行了上述检查，它也可能在同一搜索中多次遍历相同的路径。
假设您的根节点有2个分支。每个分支都通向同一个单独的节点，该节点有一条长路径从中延伸出来。树搜索将沿着那条长路径走两次，一次是从每个通向它的2个分支开始。这就是作者指出的内容。
深度优先搜索（DFS）在树搜索中是不完备的。但是，如果您跟踪已访问的节点，它将成为图搜索中的完备算法。
如果一个算法是完备的，那么意味着如果至少存在一种解决方案，则该算法保证能在有限时间内找到解决方案。
我们需要区分树搜索和图搜索。如《人工智能：一种现代方法》第3.3节或第77页所示，唯一的区别在于图搜索具有用于存储已探索节点的集合。
最后，我们可以得出答案。
