4 - Heuristic Search

Summary

Having introduced the machinery needed for search in the last chapter, we look at approaches to informed search. The algorithms introduced in the last chapter were blind, or uninformed, taking no cognizance at all of the actual problem instance to be solved and behaving in the same bureaucratic manner wherever the goal might be. In this chapter we introduce the idea of heuristic search, which uses domain specific knowledge to guide exploration. This is done by devising a heuristic function that estimates the distance to the goal for each candidate in OPEN.

When heuristic functions are not very accurate, search complexity is still exponential, as revealed by experiments. We then investigate local search methods that do not maintain an OPEN list, and study gradient based methods to optimize the heuristic value.

Knowledge is necessary for intelligence. Without knowledge, problem solving with search is blind. We saw this in the last chapter. In general, knowledge is that sword in the armoury of a problem solver that can cut through the complexity. Knowledge accrues over time, either distilled from our own experiences or assimilated from interaction with others – parents, teachers, authors, coaches, and friends. Knowledge is the outcome of learning and exists in diverse forms, varying from tacit to explicit. When we learn to ride a bicycle, we know it but are unable to articulate our knowledge. We are concerned with explicit knowledge. Most textbook knowledge is explicit, for example, knowing how to implement a leftist heap data structure.

In a well known incident from ancient Greece, it is said that Archimedes, considered by many to be the greatest scientist of the third century BC, ran naked onto the streets of Syracuse. King Hieron II was suspicious that a goldsmith had cheated him by adulterating a bar of gold given to him for making a crown. He asked Archimedes to investigate without damaging the crown. Stepping into his bathtub Archimedes noticed the water spilling out, and realized in a flash that if the gold were to be adulterated with silver, then it would displace more water since silver was less dense. This was his epiphany moment when he discovered what we now know as the Archimedes principle. And he ran onto the streets shouting ‘Eureka, eureka!’ We now call such an enlightening moment a Eureka moment!