Heuristic Search in AI

The term ‘Heuristic’ is used for algorithms that find solutions among all possible ones. 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 search 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 that determines how good or bad a node can be. If ev(n) is the best solution state and ev(n, p) is the best path then a heuristic is any information that 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 a nutshell, the heuristics needed to solve problems are expressed as a heuristic function that maps the problem states into numbers. These numbers are then appropriately used to guide the search.