My AI book and AI class have made the following claim:
Breadth-first search is complete
Depth-first search is incomplete
My first thoughts were: well, if the branching factor is infinite, BFS is incomplete, if the depth is infinite DFS is incomplete.
No! Says my instructor, we’re referring to finite, discrete spaces with finite depth.
Okay, says I, then BFS is complete, sure, DFS is incomplete, I can see that. If there’s a cycle in the graph DFS will get stuck. So implement cycle detection and we’re fine.
No so fast! Says the book (Artificial Intelligence: A Modern Approach 3d Edition), DFS is incomplete even WITHOUT cycle detection.
So… okay? Can somebody explain this to me? It seems to me that Depth First Search is complete then, since it necessarily traverses every traversable vertex/node before it terminates, just like Breadth-first, except in a different order. I can’t find any case where this is not so. I’ve done everything short of a formal proof trying to figure this out. My only guess is that for some reason the book was secretly using only a finite branching factor with a potentially infinite and my instructor was mistaken on what kind of state space the book was talking about. Any ideas?