Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

Exercise 11.1
What determines whether the branching factor of a bottom-
up tree for a system will be lower or higher than the
branching factor of a top-down tree?
114
  
Figure 11.1
Top-down search.

---

11.2 BREADTH VERSUS DEPTH
Having decided between a top-down search and a bottom-up search,
we then have to further decide on a procedure for searching the tree.
Keep in mind that any formal system of su
fficient interest for artifi-
cial intelligence researchers to be investigating will be considerably
more complex than the toy examples we are looking at here.
Consequently, choosing an appropriate search procedure can have a
significant impact on the computational resources required to carry
out the search. In fact, as we shall see, it can mean the di
fference
between a successful search and a search which never halts.
A breadth first search involves exhaustively searching all the nodes
at a given level before descending to the next level. Figure 11.3 shows
the order in which we would search the nodes of a tree if we were con-
ducting a breadth first, left first search.
A clear advantage of breadth first search is that it is exhaustive. If
there are solution states to be found anywhere on the tree, the search
will find them. A downside of breadth first search, however, is that it
can be much more computationally expensive than necessary. This is
particularly the case if the solution state is a long way down one of
the branches.

115
Figure 11.2
Bottom-up search.

---

If we expect there to be numerous solution states a long way down
the branches, it is more e
fficient to conduct a depth first search. A
depth first search involves searching all the way down the length of a
branch until we either find a solution state or hit a terminal state. If
we reach a terminal node, we backtrack only until we can descend an
unsearched branch.
Figure 11.4 shows the order in which we would search the same tree
from Figure 11.3 if we were conducting a depth first, left first search.
While depth first search can be notably more e
fficient in situations
where there are numerous solution states deep down the branches of
116
  