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^*$."* 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^*$

Best-first search keeps OPEN as a priority queue and always expands the node with the smallest evaluation $f(n)$. $A^*$ 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^*$ 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^*(n)$ for all $n$ (the heuristic never overestimates the true remaining cost $h^*$), then $A^*$ returns an optimal (least-cost) path. Note that $h = 0$ everywhere is admissible, and $A^*$ 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.