Discrete Mathsfor Engineers

2. Heuristic Functions

The heuristic function is the component that transforms A* from uninformed shortest-path search into informed search.

It provides directional knowledge about the goal, helping the algorithm prioritize more promising states.

2.1 Definition of a Heuristic

A heuristic is a function h(n) that estimates the cost of the cheapest path from node n to a goal node.

It is an estimate, not an exact value.

Its purpose is to guide the search toward the goal without fully exploring the remaining graph.

2.2 Role in A*

A* evaluates states using:

Here, g(n) measures the exact cost accumulated so far, while h(n) estimates the remaining cost.

The heuristic therefore influences which node will be explored next.

2.3 Intuition

Without a heuristic, the algorithm has no directional preference toward the goal.

With a heuristic, the search gains a notion of how far a state appears to be from success.

Better heuristics usually reduce the number of explored nodes.

2.4 Typical Examples

In pathfinding on grids, common heuristics include:

• Manhattan distance
• Euclidean distance
• Chebyshev distance

These functions do not compute the exact remaining path cost, but give a useful approximation based on geometry.

2.5 Admissibility

A heuristic is admissible if it never overestimates the true remaining cost.

where h*(n) denotes the actual optimal cost from n to the goal.

Admissibility is a key condition for the optimality of A*.

2.6 Consistency

A heuristic is consistent if, for every edge (n, n'), it satisfies:

This is a triangle-inequality-type condition.

Consistency implies that the estimated total cost does not decrease unexpectedly along a path.

2.7 Weak vs Strong Heuristics

Not all admissible heuristics are equally informative.

A heuristic is considered stronger when it stays closer to the true remaining cost while remaining admissible.

• weak heuristic → more nodes explored
• strong heuristic → fewer nodes explored

2.8 Extreme Cases

Some special cases help clarify the role of heuristics:

• h(n) = 0 for all n → A* reduces to Dijkstra’s algorithm
• g(n) ignored → the search behaves like Greedy Best-First Search

A* balances these extremes by combining exact cost and estimated future cost.