我引用人工智能：一种现代方法：
深度优先搜索的属性很大程度上取决于使用的是图搜索还是树搜索版本。避免重复状态和冗余路径的图搜索版本在有限状态空间中是完整的，因为它最终会扩展每个节点。另一方面，树搜索版本并不完整 [...]。深度优先树搜索可以在不增加内存成本的情况下进行修改，以便根据从根到当前节点的路径上的状态检查新状态；这避免了有限状态空间中的无限循环，但不能避免冗余路径的扩散。
我不明白图形搜索如何完整而树搜索不是，因为树是一个特定的图形。
此外，我不清楚“无限循环”和“冗余路径”之间的区别......
有人可以向我解释一下吗？
附言。对于那些有这本书的人，它是第 86 页（第 3 版）。
深度优先树搜索可能会陷入无限循环，这就是它不“完整”的原因。图搜索跟踪它已经搜索过的节点，因此它可以避免无限循环。
“冗余路径”是从同一起始节点通向同一结束节点的不同路径。图搜索仍然会探索所有这些冗余路径，但是一旦它到达它之前访问过的节点，它就不会继续前进，而是会备份并寻找更多它还没有尝试过的路径。
这与“无限循环”不同，“无限循环”是从节点返回自身的路径。
作为对您的评论的回应，请查看您刚刚发布的报价：
Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node.
因此，虽然深度优先树搜索确实跟踪从根到当前节点的路径，但为了避免无限循环，它需要在每次访问新节点时对该路径进行线性搜索。如果您编写了一个没有进行检查的深度优先树搜索的实现，它可能会进入无限循环。
你是对的，书中所说的“冗余路径的扩散”与完整性无关。它只是指出了图形搜索和树搜索之间的区别。因为树搜索只跟踪当前路径，所以它可以在同一搜索中多次在同一路径上运行（即使执行我刚才提到的检查）。
假设您的根节点有 2 个分支。这些分支中的每一个都通向同一个节点，该节点有一条很长的路径从它引出。树搜索将遵循该长路径两次，一次针对通向它的 2 个分支中的每一个。这就是作者要指出的。
DFS 不完整（在树搜索中）。但是，如果您跟踪访问过的节点，它就会变成完整的（在图形搜索中）。
如果一个算法是完整的，这意味着如果至少存在一个解决方案，那么该算法保证在有限的时间内找到一个解决方案。
我们需要区分树搜索和图搜索。如人工智能：现代方法中的第 3.3 节或第 77 页所示，唯一的区别是图形搜索有一个集合来存储探索的节点。
最后，我们可以找出答案。