Question about breadth-first completeness vs depth-first incompleteness

Question

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.

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?

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!

Answer 1

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.

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.

Answer 2

DFS can not stuck in cycles (if we have a list of opened and closed states). The algorithm is not complete since it does not find a solution in an infinite space, even though the solution is in depth d which is much lower than infinity.

Imagine a strangely defined state space where each node has same number of successors as following number in Fibonacci sequence. So, it's recursively defined and therefore infinite. We're looking for node 2 (marked green in the graph). If DFS starts with the right branch of tree, it will take infinite number of steps to verify that our node is not there. Therefore it's not complete (it won't finish in reasonable time). BFS would find the solution in 3rd iteration.

Rubik's cube state space is finite, it is huge, but finite (human stuck in cycles but DFS won't repeat the same move twice). DFS would find very inefficient way how to solve it, sometimes this kind of solution is infeasible. Usually we consider maximum depth infinite, but our resources (memory) are always finite.