Smarter Search: Heuristics & A*

The problem with blind search

BFS and DFS are blind — they explore in all directions equally, with no idea which way the goal is. On a big map that wastes huge effort. We can do better by guessing how close each state is to the goal.

A heuristic = an educated guess

A heuristic is a quick estimate of the distance from a state to the goal. For map routing, a great heuristic is the straight-line distance to the destination — easy to compute and never an overestimate.

# Heuristic: straight-line ("as the crow flies") distance to the goal
def heuristic(city, goal, coords):
    (x1, y1), (x2, y2) = coords[city], coords[goal]
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

coords = {'Home': (0, 0), 'Mid': (2, 1), 'Goal': (4, 0)}
print(round(heuristic('Mid', 'Goal', coords), 2))

A* search — the famous one

A\* (say “A-star”) is the most popular pathfinding algorithm — it powers maps and game characters. For each option it adds two numbers and always expands the smallest total:

• g = the real cost to get here so far.
• h = the heuristic guess of the cost still to go.
• f = g + h = estimated total cost of a route through this state.

By always expanding the lowest f, A\* heads toward the goal and keeps the path short — so it is both fast and optimal (when the heuristic never overestimates).

Here is the A\* loop in order:

1. Start at the beginning state with g = 0 (no cost yet) and compute f = g + h.
2. Pick the unexpanded state with the smallest f — the most promising option so far.
3. Goal check: if it is the goal, stop — you have the shortest path.
4. Expand it: for each neighbour, work out its g (cost so far) and h (heuristic guess), add them for f, and remember it.
5. Repeat from step 2, always choosing the lowest f, until the goal is reached.

A quick worked number: suppose getting from Home to “Mid” costs g = 3, and from the previous lesson the straight-line guess from Mid to the Goal was h = 2.24. Then f = 3 + 2.24 = 5.24 — that is the score A\* uses to compare a route through Mid against every other option.