Heuristic Search in AI

The term ‘Heuristic’ is used for algorithms which find solutions among all possible one. The Heuristic is a rule of thumb or judgment technique that leads to a solution but it provides no guarantee of success. Heuristic plays an important role in the searching process because they help to reduce the number of alternatives from an exponential number to a polynomial number.

So, we get a solution in a reasonable amount of time. The additional information about the properties of the specific domain which is built into the state and operator definitions is called Heuristic Information. A search using this Heuristic Information is called Heuristic Search or Informed Search.

A heuristic function determines a number which determines how good or bad a node can be. If ev(n) is a best solution state and ev(n, p) is the best path then a heuristic is any information which shows how good or bad that path is likely to be so, we can expand that good node and it can generate only its children. There is no blind expansion. So, pruning of the search tree occurs.

In the nutshell, the heuristics needed to solve problems are expressed as a heuristic function which maps the problem states into numbers. These numbers are then appropriately used to guide search.