Best-first search and f(n) = g(n) + h(n)

Best-first search

Best-first search uses the same open / closed bookkeeping as BFS and DFS, but it orders the open list differently. BFS orders open as a FIFO queue (by level); DFS as a LIFO stack (by recency). Best-first orders open as a priority queue — by a *heuristic estimate of closeness to the goal*. Each iteration pops the most promising state, regardless of which level it sits on, giving an opportunistic search that jumps to wherever the heuristic points.

Crucially — unlike hill-climbing — best-first keeps every generated state on open. If the heuristic leads it down a dead end, the next-best state is still waiting on the queue, so it can recover.

The evaluation function

The state's priority is its evaluation function

$$f(n) = g(n) + h(n)$$

with two parts that pull in different directions:

- $g(n)$ — the actual cost so far: the path length (or summed edge cost) from the start to $n$. It biases the search toward shallower states and stops it from diving forever down one deep branch. - $h(n)$ — the heuristic estimate of the remaining cost from $n$ to the goal. It pulls the search toward states that *look* close to the goal.

Drop $g$ and you are back to greedy hill-climbing-like behaviour (no depth penalty). Drop $h$ (set $h=0$) and you have uniform-cost / breadth-first search (blind to where the goal is). The balance of the two is the whole game — and it sets up A\* in the next lesson.

Worked example: greedy best-first (order by h alone)

Take a small graph A→{B,C}, B→D, C→F, D→F, with heuristic values $h(A)=5,\ h(B)=4,\ h(C)=2,\ h(D)=3,\ h(F)=0$. Ordering the open list by $h$ only:

1. Expand A ($h=5$); push B ($h=4$) and C ($h=2$).
2. C looks closer than B, so expand C next; push F ($h=0$).
3. F has the best $h$, expand F — goal.

Expansion order A C F, path A → C → F. The heuristic steered the search straight down the C branch and never expanded B or D. Swap the priority key from $h(n)$ to $g(n)+h(n)$ and this same machinery becomes A\*.