HEURISTIC FUNCTIONS AND SEARCH EFFICIENCY
A Heuristic function is a function that evaluates the measure of desirability for a given problem description. This measure is usually a number, which is used by search algorithms at each branching step in deciding which path to follow. A heuristic function h(n) gives the estimated cost of the cheapest path from a particular at node ‘n’ to the goal node. For doing so, it takes several decisions like, which aspects of the problem to be considered, how to evaluate those aspects, what weights to be assigned to
each aspect, etc. All these decisions are taken such that the estimated value of h(n) in least.
Examples
- In travelling salesman problem, a heuristic function considers distance between two nodes as a measure and returns the sum of distances to be covered to reach the goal node.
- In a chess game, a heuristic function takes material (i.e., king, queen, horse, etc.) into account, assigns a numerical value to each piece and it returns the material advantage of our side aver the opponent.
- In shortest path problem, a heuristic function will give the cost of the cheapest path from the current node to goal node.
The information about the problem which can sometimes help us to guide the search more efficiently are,
- The nature of the states.
- The cost of transforming from one state to another.
- The promise of taking a certain path.
- The characteristics of the goal.
This information is often expressed in the form of heuristic evaluation function f(n, g) which is function of the node n and/or the goals g. Hence, heuristic functions have additional knowledge of the problem which is imparted to the search algorithm. The idea behind a heuristic search is that we explore the node that is most likely to be nearest to the goal state. To do this we use a heuristic function which tells us how close we are to a goal state. There is no guarantee that the heuristic function will return a value that ensures that a particular node is closer to a goal state than any other node. If we could do that search would not be necessary. We would simply be moving through the various states in order to reach the goal state.
A heuristic function has following features which are not available in uninformed search,
- It takes a state as an argument and returns a number that is the estimate of the merit of the state.
- It must provide a reasonable estimate of the merit of the goal.
- It must be inexpensive to compute.
- It over estimates the cost of the path to the goal from a node.
An important point to be noted is that, low values of a heuristic function is not advantageous in all situations, sometimes a higher value may be the best solution. For example in “chess game”, it is always desirable to have h(n) as higher as it can (i.e., our score should be higher than opponent's score). This means h(n) may find either minimum or maximum value feed upon the problem situation. The primary purpose of heuristic function is to assist the search algorithm so that they choose al best or most profitable path among the available paths.
Effect of Heuristic Accuracy on Performance: Effective branching facto b* used to characterize the quality of a heuristic,
N+ 1 = 1+ b* + (b*)² +... + (b*)d
Here,
b* is the effective branching factor
d is solution depth
N is total number of nodes
Thus, the formula implies that if the total number of nodes generated by A* is N and d is solution depth then b* is the branching factor in order to contain N + 1 nodes
The efficiency of a search process can be increased by using a well designed heuristic function. However, in some cases, the cost of evaluating a heuristic function may be greater than the search process itself. In such cases we cannot implement heuristic function.
