The f(n) Evaluation Function
What you'll learn: How A* combines actual cost and heuristic estimates into a single evaluation score to prioritize which nodes to explore.
The Core Idea
In A* search, every node gets a score that helps decide which one to explore next. This score is called f(n), and it's beautifully simple:
f(n) = g(n) + h(n)
Where:
- g(n) = the actual cost to reach node
nfrom the start (what you've already spent) - h(n) = the heuristic estimate of cost from
nto the goal (what you expect to spend) - f(n) = the total estimated cost of the cheapest path through
n
Why This Matters
Think of planning a road trip. You've already driven 100 miles (that's your g(n)), and your GPS estimates another 50 miles to your destination (that's your h(n)). Your total expected trip length is 150 miles (that's your f(n)).
A* always picks the node with the lowest f(n) value to explore next. It's asking: "Which path looks most promising when I consider both what I've spent so far and what I think it'll cost to finish?"
This combination is what makes A* so effective—it balances being realistic about costs already incurred (like Dijkstra's algorithm) while being optimistic about future costs (guided by the heuristic you learned in the previous lesson).
Example
If you're at node B where g(B) = 10 (actual cost from start) and h(B) = 5 (estimated remaining cost), then f(B) = 15. If another node C has f(C) = 18, you'd explore B first.
Key Takeaway: The f(n) evaluation function combines actual cost g(n) and heuristic h(n) to estimate the total path cost through each node, guiding A* toward the goal efficiently.