Back to Study Material Artificial Intelligence

Heuristic function

A heuristic function, denoted h(n), estimates the cost of the cheapest path from a given node n to the goal state. It encodes domain knowledge in a compact...

Heuristic function

Guiding Search with Domain Knowledge

A heuristic function, denoted h(n), estimates the cost of the cheapest path from a given node n to the goal state. It encodes domain knowledge in a compact numeric form, allowing a search algorithm to prioritise states that appear more promising and avoid wasting time exploring states that are unlikely to lead to an efficient solution. The quality of the heuristic has a profound effect on search performance: a perfect heuristic would lead directly to the optimal solution without any wasted exploration, while a zero heuristic provides no guidance at all and reduces informed search to uninformed search.

For the eight-puzzle, two common heuristics are the misplaced tiles heuristic, which counts how many tiles are not in their goal position, and the Manhattan distance heuristic, which sums the horizontal and vertical distances each tile must travel to reach its goal position. The Manhattan distance is a stronger heuristic because it provides more accurate estimates and thus results in fewer node expansions.

Admissibility is the key theoretical property of heuristics used with A-star. A heuristic is admissible if it never overestimates the true cost to reach the goal. An admissible heuristic can be thought of as an optimistic estimate. When A-star uses an admissible heuristic, it is guaranteed to find the optimal solution. Consistency, also called monotonicity, is a stronger condition: h(n) is consistent if the estimated cost from n to the goal is never more than the step cost of moving to a neighbour plus the estimated cost from that neighbour to the goal.

Heuristic Dominance

Heuristic h2 dominates h1 if h2(n) is greater than or equal to h1(n) for all nodes n. A dominant admissible heuristic always results in fewer node expansions and should be preferred. The Manhattan distance dominates misplaced tiles for the eight-puzzle, which is why it is the standard choice.

Exam Tip

Exam questions often ask you to prove or disprove that a given heuristic is admissible. The standard technique is to argue that the heuristic represents a relaxed version of the original problem. For example, the Manhattan distance heuristic assumes tiles can slide through each other, which can only make the path shorter or equal, never longer. Constructing this relaxed-problem argument demonstrates solid theoretical understanding.