So far we have looked at two search algorithms that can in principle be used to systematically search the whole search space. Sometimes however it is not feasible to search the whole search space - it's just too big. Imagine searching every possible road and alley in a 400 mile circumference around Edinburgh when looking for a route to London. (OK, so this might be feasible on a fast computer, but some search spaces are REALLY big). In this case we need to use heuristic search.
The basic idea of heuristic search is that, rather than trying all possible search paths, you try and focus on paths that seem to be getting you nearer your goal state. Of course, you generally can't be sure that you are really near your goal state - it could be that you'll have to take some amazingly complicated and circuitous sequence of steps to get there. But we might be able to have a good guess. Heuristics are used to help us make that guess.
To use heuristic search you need an evaluation function that scores a node in the search tree according to how close to the target/goal state it seems to be. This will just be a guess, but it should still be useful. For example, for finding a route between two towns a possible evaluation function might be a ``as the crow flies'' distance between the town being considered and the target town. It may turn out that this does not accurately reflect the actual (by road) distance - maybe there aren't any good roads from this town to your target town. However, it provides a quick way of guessing that helps in the search.
There are a whole batch of different heuristic search algorithms,
of which we'll go through three: hill climbing, best first search and
A. We'll assume that we are searching trees
rather than graphs (ie, there aren't any loops etc). However, all the
algorithms can be simply extended for graph search by using a closed
list of nodes as described above (though this is unnecessary for hill climbing).
(Note that there are many
minor varians of these algorithms, which are described in many different ways.
Don't expect all the algorithms in different text books
to look identical).