深度优先搜索的完备性 [英] 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:

深度优先树搜索可以在不增加内存开销的情况下进行修改，以便它根据从根到当前节点的路径上的状态检查新状态.

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

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屋！