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

Exercise 11.2
If we were to simply apply a breadth first, left first search to
the tree depicted in Figure 11.5 (without applying a heuristic
function), how many nodes would we have to traverse before
reaching the same solution state? What if we used a depth
first, left first search? What if we used depth first, right first?
As Exercise 11.2 demonstrates, this heuristic search is notably more
e
fficient – in terms of the number of nodes searched – than either of
our blind search procedures. It is also the case, though, that it is more
computationally expensive per node since as well as determining
118
  

---

whether each searched node represents a solution state, we are also
applying a heuristic function.
For any generation tree of even moderate complexity though, the
computational cost per node of applying the heuristic function will
be far outweighed by the overall computational savings conferred by
the heuristic guide, since we typically massively decrease the number
of nodes we need to examine.
Unfortunately, however, heuristics are just that – heuristics. They
are not decision procedures. In other words, while heuristic values
provide us with some sort of indication of the closeness to solution
of a given node, the assigned value may not be a good representation
of the actual closeness to solution of the node. Better heuristics
provide more accurate indications, but it is always the case that
heuristic values can lead us astray.
One way in which hill climbing search can lead us astray is if a par-
ticular search path involves initially moving away from a solution state
(according to the criteria measured by our heuristic) but then swings
back and leads to a solution more quickly than other search paths.
To make this clear, consider the following spatial analogy. Suppose I
am in the rainforest at an elevation of roughly 100 metres and I want to
get down to the beach which I know to be roughly to my east. There are
two paths I can see, one of which seems to head north-east and the other
of which leads south-east. I can’t see much of either path through the
trees but what I can see is that the north-east path seems to lead gently

119