Question about breadth-first completeness vs depth-first incompleteness
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
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.