Exercises 1 - Search

Expansion order: $I, C, D, A$. Path returned: $I \rightarrow C \rightarrow A \rightarrow G$, cost $17$.

Expanding $I$ generates $C$ and $D$. Expanding $C$ generates $A$, $B$, and $E$. Expanding $D$ generates nothing new that matters. Expanding $A$ generates $G$, and the search terminates there.

Note that $B$ was generated, back when $C$ was expanded, but never expanded itself, and $G$ is never expanded at all. Being on the frontier is not the same as having been expanded, and only the expanded states go in your answer.

BFS orders by number of transitions, not by cost, so it returns the first goal it can reach in three transitions. Whether $17$ is the cheapest way to reach a goal is a separate question, and one BFS never asks. Problem 1.3 asks it.

Expansion order: $I, D, E, C, B$. Path returned: $I \rightarrow D \rightarrow E \rightarrow C \rightarrow B \rightarrow G$, cost $22$.

The stack drives down the alphabetically last branch each time. Expanding $I$ generates $C$ and $D$, and $D$ comes off first. Expanding $D$ generates $E$; expanding $E$ generates $B$ and $C$, so $C$ comes off first. Expanding $C$ generates $A$ and $B$, so $B$ comes off. Expanding $B$ generates $G$, and the search terminates.

Five transitions and cost $22$, worse on both counts than what BFS found. DFS optimizes nothing at all: it returns whichever goal its stack stumbles into first, and here the stack walked most of the graph to find the long way around.

Path returned: $I \rightarrow C \rightarrow B \rightarrow G$, cost $7$.

Watch expansions 3 and 4. $B$ and $D$ are both sitting on the frontier at $g = 5$, so the tie-break decides, and $B$ goes first because it is earlier in the alphabet. This is the only place on the page where that rule actually changes anything.

Note also that $D$ and $E$ get expanded even though neither is on the returned path. Best-first search has no way to know that, and problem 2.4 is about buying that knowledge with a heuristic.

Best-first search is optimal: $I \rightarrow C \rightarrow B \rightarrow G$ costs $7$, against $17$ for the BFS path. BFS optimizes the number of transitions rather than cost. Both paths here happen to use three transitions, but BFS commits to the first one it finds and never reconsiders, while best-first search keeps going until it is certain nothing cheaper remains. The two agree only when every transition costs the same.

Path returned: $I \rightarrow C \rightarrow B \rightarrow G$, cost $7$.

Look at the very first choice. Ranked by $h$ alone, $D$ at $h = 5$ beats $C$ at $h = 6$. Ranked by $f$, $C$ sits at $1 + 6 = 7$ and $D$ at $5 + 5 = 10$, so A* takes $C$ instead. Adding the one term $g$ reverses the decision. Problem 2.2 is about what that term is buying.

No. Ranking by $h$ alone throws away everything already spent to get where you are, so the search commits to whatever merely looks closest to the goal.

The first expansion shows it. From $I$ the frontier holds $C$ at $h = 6$ and $D$ at $h = 5$, so ranking by $h$ takes $D$, even though reaching $D$ costs $5$ where reaching $C$ costs $1$. A* ranks the same two by $f$: $C$ at $1 + 6 = 7$ against $D$ at $5 + 5 = 10$, and takes $C$.

That is what $g$ is for. It holds the search accountable for what a path has already cost, so a state that is cheap to reach but looks a little further from the goal can still win. Without it there is nothing to stop the search walking confidently in an expensive direction.

$D$ and $E$. Best-first search expanded both because it ranks by $g$ alone, and at $g = 5$ and $g = 6$ they came up before the goal did at $g = 7$.

A* never touches them. Adding $h$ puts $D$ at $f = 5 + 5 = 10$ and $E$ at $f = 6 + 3 = 9$, both well above the $f = 7$ shared by every state on the optimal path. The heuristic is what tells A* that those two lead away from the goal, which is information best-first search simply does not have.

Every $h(n) \leq h^*(n)$, so $h$ is admissible. It is exact at $B$, $C$, and $E$ and an underestimate at $I$, $A$, and $D$.

Two of these are worth checking carefully. $h^*(A) = 9$ by the direct edge $A \rightarrow G$, which happens to beat going back through $C$ and $B$ at $7 + 4 + 2 = 13$. And $h^*(I) = 7$, which is exactly the cost best-first search returned in 1.3, as it must be: $h^*$ at the initial state is the optimal solution cost.

$h_2$ is not admissible: $h_2(D) = 8 > 6 = h^*(D)$, so it claims $D$ is further from the goal than it really is.

A* with $h_2$ would still return $I \rightarrow C \rightarrow B \rightarrow G$ at cost $7$. $D$ is not on the optimal path, and inflating it only makes A* avoid $D$ more eagerly than before.

That is the point worth taking away: inadmissibility means optimality is no longer guaranteed, not that it always breaks. You cannot test admissibility by running one example and liking the answer.

Take $\max(h_3, h_4)$ at each state. Every value is still at most $h^*$, since each one came from a heuristic that never overestimates, so the combination stays admissible, and it is at least as close to $h^*$ everywhere as either input. Closer to $h^*$ means fewer expansions (potentially)!

Solve $N + 1 = 1 + b^* + (b^*)^2 + (b^*)^3$, so $53 = 1 + b^* + (b^*)^2 + (b^*)^3$.

There is no closed form, so bracket it. $b^* = 3.3$ gives $51.1$, which undershoots; $b^* = 3.35$ gives $53.2$, which just overshoots. So $b^* \approx 3.35$.

A heuristic reporting $b^* = 1.2$ on the same problem would be dramatically better: its search tree is nearly a single path to the goal.

The two structures do different jobs, and the graveyard cannot cover for the priority queue.

The graveyard prevents repeated work. Without it a search can expand the same state again and again, but it says nothing about which state to expand next.

The priority queue is what decides which state to expand next, and ordering by $g$ is what makes the first goal expanded the cheapest one. Swap in a FIFO queue and you no longer have best-first search, you have breadth-first search, which orders by number of transitions instead. Whenever transitions cost different amounts, that returns a different path, and usually a worse one. Problems 1.1 and 1.3 are exactly this case: BFS returned a path costing $17$ where best-first search returned one costing $7$, and both searches kept a graveyard the whole time.

So the classmate has kept the mechanism that saves work and thrown away the mechanism that guarantees optimality on non-uniform cost problems.

That qualifier matters, because on a uniform cost problem the classmate would be right. When every transition costs the same, fewest transitions and cheapest are the same thing, so BFS is optimal and the priority queue buys nothing. The priority queue earns its keep exactly when costs differ.

1. Iterative deepening: it keeps only the current path in memory, like depth-first search, but because it tries every depth limit in increasing order it still returns the shallowest goal, which with uniform costs is the cheapest one. Plain depth-first search would fit the memory budget too, but it would return whichever goal it happened to reach first.
2. Best-first search with $f(n) = g(n)$: it is optimal for varying costs and needs no heuristic.
3. A*: the heuristic cuts expansions, and admissibility plus consistency keeps it optimal under graph search.
4. Depth-limited search with limit $5$: it gets depth-first memory without the risk of diving past the goal, and there is no reason to pay for the repeated shallower passes iterative deepening would make when you already know the depth.

Bookkeeping per state. Every frontier entry stores $g$, and $h$ has to be computed for it, where BFS stores nothing beyond the state and the path that reached it.

Cost per frontier operation. A priority queue costs $O(\log n)$ per insertion and removal, where a plain queue or stack is $O(1)$.

Neither of these changes how many states get expanded, which is the thing A* is actually trying to reduce. So a heuristic is only worth using when the expansions it saves outweigh the overhead it adds on every state that remains.