关于广度优先完整性与深度优先完整性的问题 [英] Question about breadth-first completeness vs depth-first incompleteness

问题描述

根据AIMA（人工智能：一种现代方法）中的Norvig，深度优先算法不完整（将不会总是产生解决方案），因为在某些情况下，子树的下降将是无限的。

According to Norvig in AIMA (Artificial Intelligence: A modern approach), the Depth-first algorithm is not complete (will not always produce a solution) because there are cases when the subtree being descended will be infinite.

另一方面，如果分支因数不是无限的，则说广度优先的方法是完整的。但是，这与子树在DFS中为无穷大的情况是否有些相同？

On the other hand, the Breadth-first approach is said to be complete if the branching factor is not infinite. But isn't that somewhat the same "thing" as in the case of the subtree being infinite in DFS?

如果树的深度有限，那么DFS是否可以说是完整的？ BFS的完整性如何取决于BFS的完整性取决于分支因子是有限的！

Can't the DFS be said to be complete if the tree's depth is finite? How is then that the BFS is complete and the DFS is not, since the completeness of the BFS relies on the branching factor being finite!

推荐答案

一棵树可以是无限的，而没有无限的分支因子。例如，考虑Rubik's Cube的状态树。给定立方体的配置，就可以进行有限数量的移动（我相信18个移动是因为移动包括拾取9个平面之一并沿两个可能的方向之一旋转）。但是，树是无限深的，因为它完全有可能例如只能在同一平面上来回交替旋转（永远不要前进）。为了防止DFS这样做，通常会缓存所有访问过的状态（有效修剪状态树）-您可能知道。但是，如果状态空间太大（或实际上是无限的），这将无济于事。

A tree can be infinite without having an infinite branching factor. As an example, consider the state tree for Rubik's Cube. Given a configuration of the cube, there is a finite number of moves (18, I believe, since a move consists of picking one of the 9 "planes" and rotating it in one of the two possible directions). However, the tree is infinitely deep, since it is perfectly possible to e.g. only rotate the same plane alternatingly back and forth (never making any progress). In order to prevent a DFS from doing this, one normally caches all the visited states (effectively pruning the state tree) - as you probably know. However, if the state space is too large (or actually infinite), this won't help.

我没有广泛研究AI，但是我认为认为BFS是完整的，而DFS则不是（完整性，毕竟只是一个定义在某处的术语）是指无限深的树比具有无限分支因数的树更频繁地发生（因为具有无限分支因数意味着您拥有无限数量的选择，我认为这并不常见-游戏和模拟通常是离散的）。即使对于有限的树，BFS通常也会表现更好，因为DFS很可能会从错误的路径开始，在达到目标之前先探索树的大部分。正如您所指出的那样，在有限树中，DFS 将最终找到是否存在解决方案。

I have not studied AI extensively, but I assume that the rationale for saying that BFS is complete while DFS is not (completeness is, after all, just a term that is defined somewhere) is that infinitely deep trees occur more frequently than trees with infinite branching factors (since having an infinite branching factor means that you have an infinite number of choices, which I believe is not common - games and simulations are usually discrete). Even for finite trees, BFS will normally perform better because DFS is very likely to start out on a wrong path, exploring a large portion of the tree before reaching the goal. Still, as you point out, in a finite tree, DFS will eventually find the solution if it exists.

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