Checkpoint 1
Which node should A* try next?
Choose before revealing the rule.
Search algorithms
A* search: shortest paths guided by a heuristic.
A* keeps the useful rigour of graph search, but adds a guess about the remaining distance to the target. When that guess is good, the search can become much more focused.
Think first
A* adds a guess about what remains.
g is the cost from the start to the current node.
h is the heuristic: an estimate of the remaining cost to the target.
A* chooses the open node with the smallest f = g + h.
Checkpoint 2
What makes a good heuristic?
Imagine using straight-line distance on a map. It usually underestimates the road distance, because roads cannot always go perfectly straight.
Choose the kind of estimate you think A* needs.
A* workspace
Start A to target G; mode straight
Why A* exists
Dijkstra asks “what is cheapest so far?” A* also asks “where is the target likely to be?”
If you only care about one destination, Dijkstra can spend time exploring in directions that are mathematically valid but practically unhelpful. A* uses a heuristic to focus the search towards the goal.
This is why A* is common in games, robotics, maps and grid-based pathfinding: it can be much faster when the heuristic gives useful guidance.
Dijkstra
f = g
Explores by known cost from the start.
A*
f = g + h
Balances cost so far with estimated cost remaining.
Heuristic
h
A useful guess, such as straight-line distance to the target.
Benefits
A* can inspect far fewer nodes than Dijkstra when the heuristic is informative. It is especially useful when the graph has a physical layout and the target is known.
Drawbacks
A* depends on the heuristic. If the estimate is poor, it may not be faster. If it overestimates too aggressively, it may not return the true shortest path.
The important warning
A* is guaranteed optimal only under suitable conditions, such as an admissible heuristic that never overestimates the remaining cost.
What should students investigate next?
Switch to h = 0 and notice how A* becomes Dijkstra-like.
Compare how many nodes are opened with each heuristic mode.
Look for a case where the overconfident heuristic feels faster but risky.
Ask what a useful heuristic would be for a maze, road map or game world.