BFS is complete, DFS is not?

General Questions
#1

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?

#2

Did you mean, ‘DFS is incomplete even WITH cycle detection’?

#3

I’ve made the suggested change to your quote.

My guess is that there’s been a misunderstanding somewhere along the way. For many problems a form of BFS will find solution much faster than DFS, even though DFS can search any finite tree in finite time as long as it detects each loop (within a finite number of cycles).

#4

This section on theDepth Limited Searchaddresses completeness. I assume your Cycle Limiting has some kind of restrictions similar to Depth Limiting that makes the the overall process incomplete for all finite cases.

#5

I managed to see a 2nd Edition of that book, and it appears to be flat out misleading. At the end of the section on search there’s a chart comparing search strategies. Under “complete” BFS is marked “yes” with a footnote, indicating that’s only true if the branching factor is not infinite. DFS is simply marked “no”, with no footnote. (Depth-limited & Iterative deepening are also on the chart; “no” and “yes” with footnote respectively.)

Now, in the text it briefly does talk about depth-first search being incomplete, but only if the depth is allowed to be infinite. Thus the “comparison” chart is failing to fairly compare them.

In the context of the course or the book, they’re probably using it to cover the most common cases. It is probably more likely for the depth to be (effectively or actually) infinite while the branching factor is finite. Or it’s easier to limit branching than limit the depth. So as a practical matter the comparison works, but it’s unfortunate that it’s presented so poorly.

#6

Yes, sorry :smack:

Yeah, that makes sense. If you consider what it means to have an infinite branching factor, it means that any state can have an infinite amount of successor states. Now, this isn’t impossible, but in 99% of cases you’re going to relax the problem somewhat which, if done correctly, would ideally put a cap on the branching factor into finite territory. However, it’s not so easy to relax a problem to some sort of definite truncated state. For instance, if you’re making a pathfinding decision tree you can limit each successor node to be a discrete distance away from the pathfinding object (rather than every single continuous point it could move to in 1 “tick”), but you still have to deal with an effectively infinite (well… let’s not quibble) amount of space to potentially traverse. So I suppose it’s true in most useful contexts, but I think it was definitely presented poorly.

Thanks, everyone.