HEURISTIC SEARCH : Heuristic Function

Heuristic function has tendency to guide the search to reach goal. It checks all possible path and then find the shortest path to reach goal. The heuristic function is depicted by h(n).

Search node =( current node, parent node, heuristic value).

 Let us understand through an example:

A person in city A wants to visit City D. Cities are denoted as nodes.

                        

There are several ways to reach city D. The possible ways are:

1. He can visit city A -->city B --> city D

2. Or city A --> city C --> city D

Now by calculating heuristic value we will decide which path will be best. Here value from A  to B =4, B to D =2, A to C=1 and C to D =6.

A-->B-->D= 6

 A-->C-->D= 7

The person will prefer the path A-->B-->D.

                                         

Distance can be measured using Euclidean distance and Manhattan distance.

 Euclidean distance:

Euclidean metric is the "ordinary" straight-line distance between two points in Euclidean space. With this distance, Euclidean space becomes a metric space.

h(n)= sqrt(( x(goal) - x(n))^2 +(y(goal) - y(n))^2)

Manhattan distance: 

The sum of the horizontal and vertical distances between points on a grid.

h(n)= |x(goal) - x(n)| + | y(goal) - y(n)|.