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\*.