6.5.3 With Breadth-First Search

Pursue all possible choices "in parallel".

Let's look at the same example with breadth-first search. The big difference between breadth-first and depth-first search is that in breadth-first search we pursue all possible choices "in parallel", instead of just exploring one. So, instead of commiting to one decision, we so to speak jump between all alternatives.

It is useful to imagine that we are working with a big bag containing all the possibilities we should look at --- so in what follows we have used set-theoretic braces to indicate this bag. When we start parsing, the bag contains just one item.

The crucial difference occurs at state 5. There we try both ways of building VPs at once. At the next step, the intransitive analysis is discarded, but the transitive analysis remains in the bag, and eventually succeeds.

The advantage of breadth-first search is that it prevents us from zeroing in on one choice that may turn out to be completely wrong; this often happens with depth-first search, which causes a lot of backtracking. Its disadvantage is that we need to keep track of all the choices --- and if the bag gets big (and it may get very big) we pay a computational price.

So which is better? There is no general answer. With some grammars breadth-first search, with others depth-first.

?- Question!

Can you explain whe these to serach strategies are called depth-first and breadth-first, respectively?