深度优先搜索的完整性 [英] Completeness of depth-first search

问题描述

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

深度优先搜索的属性在很大程度上取决于是否使用图搜索版本或树搜索版本.避免重复状态和冗余路径的图搜索版本在有限状态空间中是完整的，因为它将最终扩展每个节点.另一方面，树搜索版本不是完整的[...].深度优先树搜索可以在不增加内存开销的情况下进行修改，因此它会根据从根到当前节点的路径上的状态来检查新状态.这避免了有限状态空间中的无限循环，但并没有避免冗余路径的泛滥.

The properties of depth-first search depend strongly on whether the graph-search or tree-search version is used. The graph-search version, which avoids repeated states and redundant paths, is complete in finite state spaces because it will eventually expand every node. The tree-search version, on the other hand, is not complete [...]. 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; this avoids infinite loops in finite state spaces but does not avoid the proliferation of redundant paths.

我不理解图搜索如何完整而树搜索不完整，因为树是特定的图.

I don't understand how can graph-search be complete and tree-search be not, being a tree a particular graph.

此外，我没有清楚地了解无限循环"和冗余路径"之间的区别...

Besides, I don't clearly get the difference between "infinite loops" and "redundant paths"...

有人可以向我解释吗?

May someone explain this to me?

ps.对于那些拥有本书的人，请参阅第86页(第3版).

ps. For those who have the book it's page 86 (3rd edition).

推荐答案

深度优先树搜索可能陷入无限循环，这就是为什么它不完整"的原因.图搜索跟踪已搜索到的节点，因此可以避免出现无限循环.

Depth-first tree search can get stuck in an infinite loop, which is why it is not "complete". Graph search keeps track of the nodes it has already searched, so it can avoid following infinite loops.

冗余路径"是从同一开始节点通向同一结束节点的不同路径.图搜索仍然会探索所有这些冗余路径，但是一旦它到达以前访问过的节点，它就不会再走了，而是会备份并寻找更多尚未尝试过的路径.

"Redundant paths" are different paths which lead from the same start node to the same end node. Graph search will still explore all these redundant paths, but once it reaches a node which it has visited before, it will not go any further, but will back up and look for more paths which it hasn't tried yet.

这与无限循环"不同，后者是从节点引回到自身的路径.

This is different from an "infinite loop" which is a path which leads from a node back to itself.

为回应您的评论，请查看您刚发布的报价:

In response to your comment, look at the quote which you just posted:

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.

因此，尽管深度优先树搜索确实会跟踪从根到当前节点的路径，但为了避免无限循环，它每次访问新节点时都需要对该路径进行线性搜索.如果您编写的深度优先树搜索的实现没有执行该检查，则可能会陷入无限循环.

So while depth-first tree search does keep track of the path from the root to the current node, to avoid infinite loops, it needs to do a linear search over that path each time it visits a new node. If you wrote an implementation of depth-first tree search which didn't do that check, it could get into an infinite loop.

是的，这本书所说的冗余路径的泛滥"与完整性无关.它只是指出了图搜索和树搜索之间的区别.因为树搜索只是跟踪当前路径，所以它可以在同一搜索中多次在同一路径上运行(即使进行了我刚才提到的检查).

You are right, what the book said about the "proliferation of redundant paths" doesn't relate to completeness. It is just pointing out a difference between graph and tree search. Because tree search just keeps track of the current path, it can run over the same path more than once in the same search (even if doing the check I just mentioned).

说您的根节点有2个分支.这些分支中的每一个都通向相同的单个节点，从该节点引出的路径很长.树搜索将沿着这条长路径两次进行，对于导致它的2个分支中的每一个分支一次.这就是作者指出的.

Say your root node has 2 branches. Each of those branches leads to the same single node, which has a long path leading out from it. Tree search will follow that long path twice, once for each of the 2 branches which leads to it. That is what the author is pointing out.

这篇关于深度优先搜索的完整性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！