Heuristic evaluation function estimates the cost of an optimal path between a pair of states in a single-agent path-finding problem. For example, Euclidean or airline distance is an estimate of the highway distance between a pair of locations.
MANHATTAN DISTANCE
Manhattan distance is a common heuristic function for the sliding-tile puzzles. Manhattan distance is computed by counting the number of moves along the grid that each tile is displaced from its goal position, and summing these values over all faces. For a fixed goal state, a heuristic evaluation is a function of a node, say h(n), that estimates the distance from node, say n to the given state.
KEY PROPERTIES OF A HEURISTIC EVALUATION FUNCTION
The key properties of a heuristic evaluation function are that it estimates actual cost, and that it be inexpensive to compute. For example, the Euclidean distance between a pair of points can be computed in constant time. The Manhattan distance between a pair of states can be computed in time proportional to the number of tiles. In addition, most heuristic functions are derived from relaxations of the original problem, and hence are lower bounds on actual cost, a property referred to as admissibility. For example, airline distance is a lower bound on road distance between two points, since the shortest path between a pair of points is a straight line. Similarly, Manhattan distance is a lower bound on the actual number of moves necessary to solve an instance of a sliding tile puzzle, since every tile must move at least as many times as its distance in grid units from its goal position.
APPLICATIONS OF HEURISTIC EVALUATION FUNCTIONS
A number of algorithms make use of heuristic functions, including pure heuristic search, the A* algorithm, depth-first branch-and-bound, and the heuristic path algorithm. In addition, heuristic information can be employed in bidirectional search as well.