To return to our Underground map example, we noticed that the search strategy often involved investigating routes that seemed unlikely to end up as useful, such as going south from Victoria. In the tree description, these extra possibilities made the tree more `bushy' than it really needs to be. If we could guess in advance that certain options were not worth following up, then we could reduce the amount of computer time spent finding the route. To do this, we need to invoke the idea of heuristic search, as in the game playing program.
One such heuristic might involve knowing the layout of stations on the map. We might decide to forget about any route where the line sets off in the `wrong' direction: say south when the destination is known to be north of the start point, and so on. This is like telling our horde of volunteers that they can get off and give up if they find themselves travelling away from the destination. Characteristically for a heuristic method, it will sometimes go wrong. For instance, to get from St James's Park to Warren Street, which is to the east in the map, it is best to set off west to Victoria. Examples on the Circle line can also be found. However, most of the time the heuristic rule will work properly, and when it does not, the solution arrived at will still probably be adequate. In general, using heuristics does not change the basic structure of the search. Rather, heuristic rules are incorporated into a strategy such as branch and bound in order to give greater efficiency.
For some problems, then, it might be worth limiting the amount of state space to search by adopting heuristics. The more complex the problem, the more likely this is to become necessary. For the Underground map the computer can do a complete search in a reasonable time and heuristics are not essential. For chess games there is no chance at all of playing without heuristics. For many problems in artificial intelligence the challenge lies in discovering the heuristic rules that make a search strategy possible.