Methods Of Informed Search

Informed Search: We have seen that uninformed search methods that systematically explore the state space and find the goal. They are inefficient in most cases. Informed search methods use problem specific knowledge, and may be more efficient. At the heart of such algorithms there is the concept of a heuristic function.

Heuristics: Heuristic means “rule of thumb”. To quote Judea Pearl, “Heuristics are criteria, methods or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal”. In heuristic search or informed search, heuristics are used to identify the most promising search path.

Example of Heuristic Function: A heuristic function at a node n is an estimate of the optimum cost from the current node to a goal. It is denoted by h(n).
h(n) = estimated cost of the cheapest path from node n to a goal node
Example 1: We want a path from Kolkata to Guwahati
Heuristic for Guwahati may be straight-line distance between Kolkata and Guwahati
h(Kolkata) = euclideanDistance(Kolkata, Guwahati)
Example 2: 8-puzzle: Misplaced Tiles Heuristics is the number of tiles out of place.

The first picture shows the current state n, and the second picture the goal state. h(n) = 5 because the tiles 2, 8, 1, 6 and 7 are out of place.
Manhattan Distance Heuristic: Another heuristic for 8-puzzle is the Manhattan distance heuristic. This heuristic sums the distance that the tiles are out of place. The distance of a tile is measured by the sum of the differences in the x-positions and the y-positions. For the above example, using the Manhattan distance heuristic,
h(n) = 1 1 0 0 0 1 1 2 = 6
We will now study a heuristic search algorithm best-first search.