Heuristic Functions in A*
What You'll Learn
You'll understand how the heuristic function h(n) guides A* search by estimating the remaining cost from any node to the goal.
The Core Idea
In A* search, we don't just want to find any path—we want the shortest one, and we want to find it efficiently. The heuristic function h(n) is your "educated guess" about how far a node n is from the goal.
Think of it like using a GPS: when you're driving to a destination, you can see your current location and estimate "I'm probably about 20 minutes away" even before calculating the exact route. That estimate helps you decide which direction looks most promising.
How It Works
The heuristic function takes a node as input and returns a non-negative number:
- h(n) = 0 when n is the goal node
- h(n) > 0 estimates the cost to reach the goal from n
A* combines this with the actual cost from the start (g(n)) to evaluate nodes using: f(n) = g(n) + h(n)
This means: "total estimated cost = cost so far + estimated remaining cost"
Why It Matters
A good heuristic makes A* much faster than Dijkstra's algorithm. Without a heuristic (or with h(n) = 0), A* becomes Dijkstra's—it explores equally in all directions. With a helpful heuristic, A* focuses its search toward the goal, like a bloodhound following a scent rather than searching randomly.
The heuristic must be admissible (never overestimate) to guarantee finding the optimal path—but that's a topic for later.
Key Takeaway: The heuristic function h(n) estimates the cost from a node to the goal, guiding A* to explore promising paths first and making the search dramatically more efficient than uninformed approaches.