深度优先搜索的完整性

Question

我引用人工智能:现代方法:

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

我不明白图搜索是如何完成的,树搜索不是,树是一个特定的图.

此外,我没有明确区分"无限循环"和"冗余路径"......

愿有人向我解释一下吗？

PS.对于有这本书的人来说,这是第86页(第3版).

Answer 1

深度优先树搜索可能陷入无限循环,这就是它不"完整"的原因.图搜索会跟踪已搜索的节点,因此可以避免跟随无限循环.

"冗余路径"是从相同的起始节点到相同的末端节点的不同路径.图搜索仍将探索所有这些冗余路径,但是一旦它到达之前访问过的节点,它将不会再进一步​​,但会备份并查找尚未尝试过的更多路径.

这与"无限循环"不同,"无限循环"是从节点返回自身的路径.

在回复您的评论时,请查看您刚发布的报价:

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个分支.这些分支中的每一个都通向相同的单个节点,该节点具有从其引出的长路径.树搜索将沿着该长路径两次,对于通向它的两个分支中的每一个,一次.这就是作者所指出的.