Course contentsShow
← Computer Science
Lesson 1002 of 2,87223. Shortest Path AlgorithmsFree lesson

The f(n) Evaluation Function

Learn how A* combines g(n) (actual cost) and h(n) (heuristic) into f(n) = g(n) + h(n) for node evaluation.

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 n from the start (what you've already spent)
  • h(n) = the heuristic estimate of cost from n to 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.