Search & heuristic drills

The search facts the exam tests

Q4 asks you to "explain, using an example, how the best-first heuristic principle is used in $A^{\ast }$." Behind that sit the uninformed searches you must also be able to hand-trace.

BFS vs DFS — the one-line distinction:

• BFS keeps OPEN as a FIFO queue (first in, first out). It explores level by level, so it finds the shortest path in number of moves. Cost: it holds a whole frontier in memory ($O(B^d)$).
• DFS keeps OPEN as a LIFO stack (or uses native recursion). It plunges down one branch first. It is memory-cheap but not shortest-path and can loop without a visited (CLOSED) set.

Both maintain a CLOSED list of already-expanded states so they never re-expand a node.

The best-first principle and $A^{\ast }$

Best-first search keeps OPEN as a priority queue and always expands the node with the smallest evaluation $f(n)$. $A^{\ast }$ chooses

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

where $g(n)$ is the actual cost from the start to $n$, and $h(n)$ is a heuristic estimate of the remaining cost from $n$ to the goal. $A^{\ast }$ thus expands the node that looks cheapest overall, balancing what it has spent ($g$) against what it expects to spend ($h$).

Admissibility is the guarantee: if $h(n)\le h^{\ast }(n)$ for all $n$ (the heuristic never overestimates the true remaining cost $h^{\ast }$), then $A^{\ast }$ returns an optimal (least-cost) path. Note that $h=0$ everywhere is admissible, and $A^{\ast }$ with $h=0$ degenerates to uniform-cost / BFS.

Worked example — Q4 on a small weighted graph

Edges (cost): $S\to A(1)$, $S\to B(4)$, $A\to B(2)$, $A\to G(5)$, $B\to G(1)$. Admissible heuristics $h$: $S=5,A=4,B=1,G=0$.

• Start: OPEN $=\{S(f=0+5=5)\}$. Expand $S$.
• Generate $A$: $g=1,f=1+4=5$. Generate $B$: $g=4,f=4+1=5$.
• Tie at $f=5$; expand $A$ (it was pushed first). From $A$: $B$ via $g=1+2=3,f=3+1=4$; $G$ via $g=6,f=6+0=6$.
• Lowest $f$ now is $B(f=4)$ on the cheaper $g=3$ path. Expand $B$: $G$ via $g=3+1=4,f=4$.
• Expand $G$ at $g=4$. Optimal path $S\to A\to B\to G$, cost 4, beating the naive $S\to A\to G$ (cost 6) and $S\to B\to G$ (cost 5). The heuristic steered expansion toward the goal without ever overestimating, so optimality held.