Heuristics in Artificial Intelligence

What does heuristic mean?

Well, heuristic refers to "to discover".

Heuristic is a technique that improves the efficiency of search process possibly by sacrificing the completeness. This technique gives us optimized solution.

We can hope to get good solutions to hard problems such as Travelling Salesman Problem which takes less than the exponential time. Some heuristics helps to guide a search process without sacrificing any claims to completeness.

Some may occasionally cause an excellent path to be overlooked to improve the quality of paths that are explored. 

There are 2 types of  heuristics :

1. General purpose heuristics.

• General purpose heuristics do not require the need for any specific knowledge.
• For example, Nearest neighbor heuristics, travelling salesman problem.

     2. Special purpose heuristics.

• Unlike General purpose heuristic, special purpose heuristics require domain specific knowledge.
• For example, an interesting function of two arguments f(x,y).

Domain specific knowledge can be incorporated into rule based search procedure. 

Two things are required for rules based search.

• Rules itself,
• Heuristic function, that evaluates the individual problem state and determine how desirable they are.

The purpose of heuristic function is to guide the search process in the most profitable path among all that are available. It is a function that maps from problem state description to measure of desirability usually represented as numbers.

For example,

For initial state, 

        heuristic, h1 = 8 

For goal state,

        heuristic, h2 = 2+1+1+1+1+0+0+2 = 8 

Therefore, the optimized solution will be, h1+ h2 = 8 + 8 = 16