For reasons I can't exactly recall, someone asked me the other day about the differences between breadth-first vs. depth-first search. I provided a decent answer, and since this is the ideal place for such dorky discussions, I have elected to throw it up here. Computer, throw up search discussion!
First and foremost, a breadth-first search isn't what you do when you're in a bakery and you're looking for some rye. (That was the dumbest thing I've ever typed.)
Imagine you're looking at a tree structure. A depth-first search would start at the root and descend down a single path of lineage until it reached a childless node at the bottom; then it'd start on the next line of lineage and work its way down again, and so forth until we're out of nodes. A breadth-first search, meanwhile, would start at the root (level r), descend a level (level r+1), examine all nodes at that level, and would then repeat that action at the next level (level r+2). You could find a similar description in a textbook, so maybe that's not so helpful. Perhaps yo-yo vs. typewriter analogy is more fitting? No, I think not. Let's try again.
Imagine you're looking at a chess board, and you're trying to determine the best opening move you could make. You could do this two different ways.
The first way would be to concentrate on a single pawn. You think to yourself, "I could move THIS pawn two spots forward." Then you think what your opponent may do in response. You think, "He could move THAT pawn one spot forward." Then you think to yourself, "With THIS pawn here and THAT pawn there, I could move my bishop diagonally 3 spots." You're looking at a single possible sequence in great depth. That's a depth-first search.
The second way would be to look at the board and examine every possible first move. You realize you could move any of your pawns, or you could move any of your knights. Then what happens? Well, your opponent could move one of his pawns or one of his knights. Then what happens? Well, you could move your pawns some more, make your rooks dance, unleash your queen, etc. Instead of looking at a single sequence, you're looking at each possible move, one level at a time. That's a breadth-first search.
If you had to implement something that could advise you on chess moves, what would you pick? Clearly, the number of potential moves explodes combinatorically as we get deeper into the game. Just as clearly, humans aren't immortal, so we'd need a definitive answer before the heat death of the universe. Since we don't have time to examine each chain of possibilities and breadth-first is the only way to examine each path equally, I'd use breadth-first search. Of course, this may explain why I'm such a crappy chess player.
Posted by Cody at January 11, 2007 08:19 PM