Worked examples — A - algorithm — heuristic, admissibility, consistency — important for GNC

Before anything: recall the three quantities from the parent — $g(n)$ = cost paid to reach $n$, $h(n)$ = guess of cost still owed to the goal, and $f(n)=g(n)+h(n)$ = guess of the whole trip. A* always pops the frontier node with the smallest $f$. Every example below is just those three letters in a new outfit.

---

The scenario matrix

Read this table as a checklist of every distinct behaviour A* can exhibit; the "Example" column is the promise that we demonstrate each one, not just assert it. Column meaning: Case class = the condition on the heuristic or graph; What makes it special = the single behaviour you must be able to predict; Example = where it is worked in full.

#	Case class	Behaviour you must predict	Example
C1	Admissible + consistent heuristic	optimal path, no re-expansion	Ex 1
C2	Tie in $f$ (goalward vs sideways)	tie-break rule fires; speedup over Dijkstra	Ex 2
C3	$h=0$ (degenerate)	A* collapses to Dijkstra's Algorithm	Ex 3
C4	Inadmissible (overestimating) $h$	optimality breaks	Ex 4
C5	Admissible but NOT consistent	a closed node is re-expanded	Ex 5
C6	Greedy trap ($f=h$ only)	small $h$ lures into a costly detour	Ex 6
C7a	Dead end (no successors, $h^{\ast }=\infty$)	node examined once, harmlessly abandoned	Ex 7a
C7b	Negative edge present	A* / Dijkstra can return a wrong cost	Ex 7b
C8	Real GNC drone, Euclidean $h$	continuous space, consistent, focused cone	Ex 8
C9	Weighted A* ($f=g+wh$)	bounded suboptimality $\le w{C}^{\ast }$	Ex 9

---

Example 1 — Grid, Manhattan heuristic (Cell C1)

Forecast: Guess the optimal cost and whether A* ever expands the cell $(-1,0)$ (behind the start).

Step 1. Compute $h$ at the start: $h(0,0)=|0-2|+|0-1|=3$. So $f(S)=g+h=0+3=3$. Why this step? $f$ at the start is our first, purely-heuristic estimate of the whole trip. In the figure, inspect the yellow number under $S$ — that is this $f=3$.

Step 2. Expand $S$. Neighbours and their $f$:

• $(1,0)$: $g=1$, $h=|1-2|+|0-1|=2$, $f=3$.
• $(0,1)$: $g=1$, $h=|0-2|+|1-1|=2$, $f=3$.
• $(-1,0)$: $g=1$, $h=|-1-2|+|0-1|=4$, $f=5$. Why this step? A* keeps the smallest $f$. In the figure, note the two blue cells (goalward, $f=3$) versus the pink cell $(-1,0)$ labelled $f=5$ — pink is never touched.

Step 3. Continue popping $f=3$ nodes toward $T$. The path $S\to (1,0)\to (2,0)\to (2,1)$ has cost $3$ (the yellow arrows in the figure), and along it $f$ stays $=3$ the whole way (consistency keeps $f$ flat here). Why this step? Manhattan is consistent on a unit grid: between neighbours the edge cost $c(u,v)=1$ and $|h(u)-h(v)|\le 1=c(u,v)$, so $f$ never dips → no re-expansion.

Verify: True optimum = $|2-0|+|1-0|=3$ moves. A* returned $3$. ✔ Backward cell $f=5>3$, never expanded. ✔

---

Example 2 — The tie, and why it means speed (Cell C2)

Forecast: How many cells does plain Dijkstra expand before reaching $T$ vs A*?

Step 1. Under Dijkstra ($f=g$), the frontier grows as a diamond of radius $g$. To reach a node at distance $3$, Dijkstra expands all cells with $g\le 3$: that's $1+4+8+12=25$ cells (the diamond $|x|+|y|\le 3$). Why this step? Dijkstra is blind — it treats every direction equally, so it fills a full diamond. In figure s01, imagine that whole diamond filled; A* instead touches only the handful of cells drawn.

Step 2. Under A*, every backward cell has $f=g+h>3$ because moving away raises $h$ by as much as $g$ rises. The cells that keep $f=3$ are exactly the nodes inside the axis-aligned rectangle spanned by $S=(0,0)$ and $T=(2,1)$: that is $(2+1)\times (1+1)=6$ cells (grid points), namely all $(x,y)$ with $0\le x\le 2,0\le y\le 1$. Why this step? Be careful: we are counting nodes with $f=3$, not the number of distinct shortest paths. The number of monotone shortest paths from $S$ to $T$ is the smaller number $\left(\genfrac{}{}{0ex}{}{3}{1}\right)=3$ (choose which of the 3 steps goes upward). A* may touch all 6 rectangle nodes but there are only 3 optimal routes through them.

Step 3. Speedup ratio in nodes expanded $=25/6\approx 4.17$. Why this step? This ratio is the payoff of the heuristic — the tie-at-$f$ cells are exactly the useful ones. When two of them tie (e.g. $(1,0)$ vs $(0,1)$ both at $f=3$), our global tie-break rule (larger $g$ first, then insertion order) decides the pop order deterministically; either way the answer cost is unchanged.

Verify: Diamond count ${\sum }_{r=0}^3(\text{cells at radius }r)=1+4+8+12=25$. Rectangle nodes $=(2+1)(1+1)=6$. Monotone paths $=\left(\genfrac{}{}{0ex}{}{3}{1}\right)=3$. Ratio $25/6$. ✔

---

Example 3 — Degenerate $h=0$: A* becomes Dijkstra (Cell C3)

Forecast: Which node does A* expand second — $A$ or $B$? And is the answer optimal?

Step 1. With $h\equiv 0$, $f(n)=g(n)$. Expand $S$: put $A$ ($f=2$) and $B$ ($f=5$) on the frontier. Why this step? $h=0$ is trivially admissible ($0\le h^{\ast }$) and consistent, so optimality still holds — we're just unguided.

Step 2. Pop smallest $f$: that's $A$ ($f=2$). Relax $A\to T$: $g(T)=2+6=8$, $f=8$. Why this step? This is precisely Dijkstra's "pop the cheapest-so-far" rule. $h$ contributes nothing.

Step 3. Frontier now $\{B:5,T:8\}$. Pop $B$ ($f=5$). Relax $B\to T$: $g(T)=5+2=7<8$, update $T$ to $f=7$. Why this step? We found a cheaper route to $T$ through $B$; A* (=Dijkstra here) keeps the better $g$.

Step 4. Pop $T$ at $f=7$. Done.

Verify: Path costs: $S\to A\to T=8$, $S\to B\to T=7$. Optimum $=\min (8,7)=7$. A* returned $7$. ✔ And it ran exactly Dijkstra — not broken, just blind.

---

Example 4 — Inadmissible $h$ breaks optimality (Cell C4)

Forecast: Will A* find cost $2$ (true optimum) or the worse $2.5$?

Step 1. Expand $S$. Successors: $A$ with $g=1,h=5,f=6$; and $G$ directly with $g=2.5,h=0,f=2.5$. Why this step? The inflated $h(A)=5$ makes the good route look like a 6-cost trip — a lie the search believes.

Step 2. Pop smallest $f$: the direct $G$ at $f=2.5$ beats $A$'s $f=6$. Since $G$ is a goal, A* halts and returns $2.5$. Why this step? A* trusts $f$. Because $h$ overestimated ($5>h^{\ast }(A)=1$), it discarded the truly cheaper path.

Step 3. Note the violated condition: admissibility needs $h(A)\le h^{\ast }(A)=1$, but $5\nleqq 1$. Why this step? This is the exact line crossed. The parent's Derivation 1 needed $h(n)\le h^{\ast }(n)$; break it and the optimality proof collapses.

Verify: True optimum $=\min (1+1,2.5)=2$. A* returned $2.5\ne 2$ — optimality lost, as predicted. ✔

---

Example 5 — Admissible but NOT consistent → re-expansion (Cell C5)

Forecast: Does A* close $Y$ once at $g=2$, then have to re-open it at a cheaper $g=1$? What's the final cost?

Step 1. Compute the true remaining costs $h^{\ast }$ (the perfect distances to $G$): $h^{\ast }(Y)=2$ (edge $Y\to G$), $h^{\ast }(X)=\min (X\to Y\to G)=1+2=3$, $h^{\ast }(S)=\min (2+2,0+3)=3$. Why this step? We need $h^{\ast }$ to test admissibility ($h\le h^{\ast }$) — you cannot judge a guess without the truth it estimates.

Step 2. Check admissibility node-by-node: $h(S)=0\le 3$ ✔, $h(X)=3\le 3$ ✔, $h(Y)=1\le 2$ ✔, $h(G)=0\le 0$ ✔. So $h$ is admissible. Why this step? One node over $h^{\ast }$ would sink admissibility; all four clear it, so optimality is still guaranteed.

Step 3. Check consistency on edge $X\to Y$ (cost $c(X,Y)=1$): the rule demands $h(X)\le c(X,Y)+h(Y)=1+1=2$. But $h(X)=3>2$ — violated. So $h$ is admissible yet inconsistent. Why this step? Consistency is the stronger triangle-inequality condition; failing it on even one edge means A* may pop a node before its cheapest $g$ is settled.

Step 4. Run A*. Expand $S$ ($g=0$): successors $X$ with $g=0,f=0+3=3$; and $Y$ with $g=2,f=2+1=3$. This is an $f=3$ tie; by our global tie-break rule (larger $g$ first) we pop $Y$ ($g=2$) before $X$ ($g=0$). We close $Y$ with $g(Y)=2$ and relax $Y\to G$: $g(G)=4,f=4$. Why this step? $Y$ is now closed believing its cheapest cost is $2$ — but we have not yet explored the route through $X$. (The tie-break rule choosing $Y$ first is exactly what sets up the re-expansion; had we popped $X$ first, $Y$ would never have closed prematurely — but a real solver cannot know that in advance.)

Step 5. Pop $X$ ($f=3$). Relax $X\to Y$: new $g(Y)=g(X)+c(X,Y)=0+1=1$, which is cheaper than the closed value $2$. This forces the closed node $Y$ to re-open, and we re-relax $Y\to G$: $g(G)=1+2=3<4$. Why this step? This is the re-expansion the parent warned about — inconsistency let $Y$ close too early, so a later cheaper path drags it back onto the frontier.

Step 6. Pop $G$ at $g=3$. Done.

Verify: Optimal path $S\to X\to Y\to G=0+1+2=3$. A* (after re-opening $Y$) returned $3$ — optimality preserved (admissible), but it cost one re-expansion (inconsistent). ✔

---

Example 6 — Greedy best-first trap (Cell C6)

Forecast: Greedy loves the small $h(A)=1$. Does that path turn out cheap or a trap?

Step 1. Greedy uses $f=h$ only. From $S$: $A$ has $h=1$, $B$ has $h=9$. Greedy pops $A$, then races to $G$: total path cost $=1+100=101$. Why this step? Greedy ignores the road already travelled ($g$), so it's seduced by the low-$h$ node without noticing the giant edge behind it.

Step 2. A* uses $f=g+h$. From $S$: $A$ has $f=1+1=2$, $B$ has $f=10+9=19$. Pop $A$; relax $A\to G$: $g(G)=101,f=101$. Frontier: $\{B:19,G:101\}$. Pop $B$ ($f=19$); relax $B\to G$: $g(G)=20<101$, update. Pop $G$ at $20$. Why this step? The $g$ term makes A* notice the expensive edge — $f(G\text{ via }A)=101$ loses to the $B$ route.

Verify: Greedy cost $=101$. A* / true optimum $=\min (101,20)=20$. A* returned $20$; greedy returned $101$. ✔ Greedy trap confirmed.

---

Example 7a — Dead end / blocked frontier (Cell C7a)

Forecast: If $D$ looks promising, will A* get stuck?

Step 1. Pin down $h^{\ast }(D)$. From the dead end $D$ there is no path to the goal at all, so by our convention $h^{\ast }(D)=\infty$. Why this step? Admissibility is $h(D)\le h^{\ast }(D)$. Since $h^{\ast }(D)=\infty$, any finite $h(D)$ is admissible — even an over-eager $h(D)=1$ that makes $D$ look close. There is no finite truth for it to overshoot.

Step 2. Take $h(D)=1$ (deliberately tempting), and $h(A)=1$. Expand $S$: $D$ gets $g=1,h=1,f=2$; $A$ gets $g=1,h=1,f=2$. Two nodes tie at $f=2$; our global tie-break rule breaks by larger $g$ (equal here, both $1$) then insertion order — say $D$ entered first, so $D$ is popped first. Why this step? We deliberately let the tie hand $D$ to the solver first, to prove even the worst-case order is harmless.

Step 3. Pop $D$. It has zero out-edges → it generates no frontier nodes. $D$ is simply closed and abandoned. Why this step? A dead end can be examined but never extended; the search naturally moves on to the next-cheapest frontier node.

Step 4. Pop $A$ ($f=2$). Relax $A\to G$: $g(G)=2,f=2$. Pop $G$. Done, cost $2$. Why this step? The dead end cost us one wasted pop but not the answer — A* is complete as long as the goal is reachable and edge costs are nonnegative.

Verify: Only reachable goal path $S\to A\to G=2$. A* returned $2$. ✔ Dead end $D$ contributed nothing but one pop, and $h(D)=1$ was admissible because $h^{\ast }(D)=\infty$. ✔

---

Example 7b — A negative edge breaks A* (Cell C7b)

Forecast: The route through the $-5$ edge is genuinely cheapest. Will A* find it, or lock in a worse cost?

Step 1. List the true path costs. $S\to A\to G=1+1=2$. $S\to G$ direct $=3$. $S\to A\to G^{\prime }\to G=1+(-5)+0=-4$. True optimum $=\min (2,3,-4)=-4$. Why this step? We compute the ground truth first, so we can catch A* red-handed if it disagrees.

Step 2. Run A* with $h\equiv 0$ (Dijkstra). Expand $S$: frontier $\{A:1,G:3\}$. Pop $A$ ($f=1$), close it. Relax: $g(G)=\min (3,1+1)=2$; $g(G^{\prime })=1+(-5)=-4$. Why this step? Dijkstra/A* closes $A$ believing $g(A)=1$ is final. With nonnegative edges that belief is safe — here it is about to bite us.

Step 3. Frontier $\{G:2,G^{\prime }:-4\}$. Pop $G^{\prime }$ ($f=-4$), relax $G^{\prime }\to G$: $g(G)=\min (2,-4+0)=-4$. Update $G$. Pop $G$ at $-4$. Why this step? In this tiny graph the negative edge happens to still surface, giving $-4$. But the mechanism is fragile: had the negative edge dangled off a node that was closed before the cheaper route reached it, A* would never revisit it and would return the too-high $2$.

Step 4. State the failure mode cleanly. A*/Dijkstra's correctness rests on the non-decreasing $f$ property (parent's Derivation 2, Step B), which itself needs $c(u,v)\ge 0$. A negative edge can lower $g$ of an already-closed node, and the closed set will refuse to reopen it → wrong answer in general. Why this step? The point of C7b is the limiting/degenerate case the assumption forbids: with even one negative edge you must switch to Bellman–Ford, which relaxes every edge $|V|-1$ times and does tolerate negatives (no closed set).

Verify: True optimum $=\min (2,3,-4)=-4$. The safe algorithm for negatives is Bellman–Ford, not A*. ✔ (We report $-4$ here but flag that A* gives no guarantee once $c<0$.)

---

Example 8 — Real-world GNC drone, Euclidean heuristic (Cell C8)

Forecast: Is the answer $6$ (all straight) or $3\sqrt{2}\approx 4.24$ (all diagonal)? And is Euclidean $h$ safe on diagonal moves?

Step 1. The cheapest route from $(0,0)$ to $(3,3)$ is $3$ diagonal steps: cost $=3\sqrt{2}\approx 4.243$. In figure s02, this is the blue arrowed diagonal; compare it against the pink L-shaped path (all straight, cost $6$). Why this step? Each diagonal step advances both $x$ and $y$ by $1$ for cost $\sqrt{2}$, cheaper per unit progress than two straight steps ($=2$).

Step 2. Compute $h$ at start: $h(0,0)=\sqrt{3^2+3^2}=3\sqrt{2}\approx 4.243$ — drawn as the dashed straight line in s02. Why this step? The Euclidean straight line is the shortest possible distance in the plane, so it can never exceed the true grid path cost $h^{\ast }$ — hence $h\le h^{\ast }$: admissible.

Step 3. Now verify consistency on the two move types, since an 8-connected grid has both.

• Straight move, e.g. $u=(x,y)\to v=(x+1,y)$, cost $c=1$. Euclidean $h$ obeys the Triangle Inequality: $\Vert u-T\Vert \le \Vert u-v\Vert +\Vert v-T\Vert$, and $\Vert u-v\Vert =1=c$. So $h(u)\le c+h(v)$. ✔
• Diagonal move, $u\to v=(x+1,y+1)$, cost $c=\sqrt{2}$. Again by the triangle inequality $\Vert u-T\Vert \le \Vert u-v\Vert +\Vert v-T\Vert$ with $\Vert u-v\Vert =\sqrt{2}=c$. So $h(u)\le c+h(v)$. ✔ Why this step? The key insight: consistency needs $h(u)-h(v)\le c(u,v)$, and Euclidean distance changes by at most the Euclidean step length, which we deliberately set equal to the edge cost ($1$ for straight, $\sqrt{2}$ for diagonal). Matching the metric to the cost is what makes it consistent — no re-expansion.

Step 4. How A* explores: because here $h(0,0)=3\sqrt{2}$ equals $h^{\ast }(0,0)$ exactly, every off-diagonal cell has strictly larger $f$, so A* expands an extremely narrow cone hugging the blue diagonal — essentially just the true path plus its immediate neighbours. Why GNC cares: a tight admissible+consistent $h$ makes A* laser-focused, so an on-board planner with limited compute still returns the genuinely shortest flyable route in real time.

Verify: Optimum $=3\sqrt{2}\approx 4.2426$. $h(0,0)=3\sqrt{2}\le$ optimum (equal here) ✔. All-straight alternative $=6>4.243$ ✔. Consistency holds on both straight ($c=1$) and diagonal ($c=\sqrt{2}$) moves ✔.

---

Example 9 — Exam twist: Weighted A* (Cell C9)

Forecast: Does inflating $h$ by $w=2$ still find the optimum $20$, or trade it for speed?

Step 1. Inflate the heuristic in the priority key: $f(A)=g+wh=1+2\cdot 1=3$, and $f(B)=10+2\cdot 9=28$. Why this step? Multiplying $h$ by $w>1$ makes the search more greedy — it trusts the goal-guess twice as much, so it dives toward low-$h$ nodes sooner. The $g$ part is untouched.

Step 2. Pop the smaller key first: $A$ at $f=3$ beats $B$ at $f=28$. Expand $A$, relax $A\to G$: $g(G)=1+100=101$, key $f=101+2\cdot 0=101$. Why this step? Only now, after actually walking the edge, does the giant $100$ cost enter through $g$ — the inflated $h$ could not warn us because $h(A)$ was tiny.

Step 3. Frontier $\{B:28,G:101\}$. Pop $B$ ($f=28$), relax $B\to G$: $g(G)=10+10=20<101$, update $G$'s key to $20+0=20$. Why this step? $B$'s inflated key $28$ still beat the discovered $G$ at $101$, so A* re-examines $B$ and finds the genuinely cheaper $20$ route. Here the weighting did not cost us the optimum.

Step 4. Pop $G$ at key $20$. Weighted A* returns cost $20$. Why this step? We got the optimal answer even at $w=2$; weighting only risks suboptimality, it does not force it.

Step 5. State the guarantee. Weighted A* returns a path of cost $\le w\cdot C^{\ast }$, where $C^{\ast }$ is the true optimum. Here $C^{\ast }=20$ so the bound is $2\cdot 20=40$. Why this step? This is bounded suboptimality: you may lose optimality, but never by more than the factor $w$. Our $20$ sits well inside $40$.

Verify: True optimum $C^{\ast }=\min (1+100,10+10)=20$. Weighted-A* result $=20$. Bound $w\cdot C^{\ast }=2\cdot 20=40\ge 20$ ✔.

---

Recall Scenario matrix — self-test

Which cell forces a re-expansion? ::: C5 — admissible but not consistent. Which cell makes A* identical to Dijkstra? ::: C3 — $h=0$. Which cell breaks optimality outright? ::: C4 — inadmissible (overestimating) $h$. Which cell needs Bellman–Ford instead of A*? ::: C7b — a negative edge is present. What is $h^{\ast }$ for a dead-end node with no path to the goal? ::: $\infty$, so any finite $h$ there is admissible. In Weighted A* with $w$, the returned cost is bounded by? ::: $w\cdot C^{\ast }$ (bounded suboptimality). What is our global tie-break rule when $f$ is equal? ::: pop the larger-$g$ (smaller-$h$) node first, then by insertion order.