The two previous lessons searched for and sorted values in collections. This lesson closes the module with a search of a different nature: finding a sequence of decisions that leads from an initial situation to a goal — the route of a Rutalia van across a grid with blocked streets, the planning of a delivery run under constraints. The formal framework is called a state space, and it is the point where several ideas you already own converge: the implicit graphs of 03-01, the BFS/DFS of 03-02, the Dijkstra of 03-03 and the exploration trees of the backtracking in 02-03. Here we will give them a common roof and add the piece promised since module 3: A*, "Dijkstra with a compass", which uses a heuristic to expand far fewer nodes. We will compare Dijkstra against A* experimentally and settle the complete mental map of the course's exploration techniques.

1. What a state space is: state, operators, goal, cost
2. State spaces vs. explicit graphs: the implicit and the gigantic
3. BFS and DFS over implicit spaces: the grid from 01-03 revisited
4. Uniform-cost search: Dijkstra without a graph
5. A*: heuristics, admissibility and consistency
6. Full implementation: a delivery route on a grid with obstacles
7. Experimental comparison: nodes expanded with and without a compass
8. Non-admissible heuristics, weighted A* and IDA* (brief)
9. The mental map: path finding vs. exact optimization (02-03)

A state space is a way of framing a problem as exploration. It is defined by four pieces:

A solution is a path of operators from the initial state to a goal state; an optimal solution is the one of minimum cost. Note that the state can be much richer than a position: if the van must pick up and deliver, the state could be (position, packages_on_board); if there are time windows, (position, time). Choosing what information goes into the state is the most important design decision: everything that affects future moves must be inside; everything that doesn't, outside (or the space blows up needlessly).

A state space is a graph: states are vertices and operators are weighted edges. So what is new relative to module 3? The difference is one of representation and scale, and we already anticipated it in 03-01 when discussing implicit graphs:

• Explicit graph (Rutalia's 9-zone network): it fits entirely in memory as an adjacency list; we can iterate over it, precompute Floyd-Warshall 9×9, draw it.
• Implicit graph (a state space): only the function successors(state) exists. The full graph may have 10²⁰ states — we will never materialize it. The only thing we can do is generate it on the fly from the initial state, and the central question becomes: how many states do we need to touch before finding the goal?

That question — nodes generated and expanded, not total vertices — is this lesson's metric. With a branching factor b (successors per state) and a solution at depth d, a blind exploration touches on the order of b^d states. Everything that follows is the fight to reduce that number.

The algorithms from 03-02 work unchanged: they never required having the whole graph, only asking for neighbors. The minimum-cost grid from 01-03 — which in 03-01 we already recognized as a graph — is our toy state space: we solved it with dynamic programming because movement was only right and down; now the van moves in all four directions and there are obstacles, so sweep-based DP no longer applies and we must search.

Look at the signature: bfs_states does not receive a graph, it receives functions (is_goal, successors_fn). That is the lesson's shift in mindset — the algorithm is the same one from 03-02.

On when to use each blind exploration:

The visited set (parent plays that double role) deserves emphasis: in a state space, paths cross constantly (cell (3, 4) can be reached by thousands of routes). Without a visited set, the same state is re-explored over and over and the cost goes from b^d to far worse. The exception is when the space really is a tree — as in the backtracking of 02-03, where each node had a single path from the root; we will return to this distinction at the end.

If the operators have different costs (crossing a congested avenue costs 3 minutes; an empty street, 1), BFS stops being optimal: it minimizes steps, not cost. You already know the solution from 03-03: always expand the state of least accumulated cost using a heap. Applied to an implicit space, the algorithm is called uniform-cost search (UCS), but it is literally Dijkstra with successors generated on the fly — same invariant ("whatever leaves the heap is final"), same lazy deletion.

We do not implement it separately: in the A* code of the next section, UCS is the special case h = 0. That is exactly the relationship between the two.

Dijkstra/UCS explores in concentric circles of increasing cost around the start: it is exhaustive and blind, spending the same effort toward the goal as away from it. But in many state spaces we know something about where the goal is. That something is formalized as a heuristic:

h(n) = an estimate of the remaining cost from state n to the goal.

A* orders the heap not by the accumulated cost g(n), but by

f(n) = g(n) + h(n) — cost already paid + estimated cost remaining = estimate of the total cost going through n.

Intuition: between two states with the same accumulated cost, A* expands first the one that looks closer to the goal. It is Dijkstra with a compass: the exploration stops being a circle and becomes an ellipse stretched toward the goal.

The guarantees depend on the quality of h:

• Admissibility: h never overestimates the true remaining cost (h(n) ≤ h*(n) for all n). With an admissible h, A* finds the optimal solution. The intuition behind the proof: if A* were about to return a suboptimal path, the optimal path would have some state on the frontier with a smaller f (because its h does not overestimate), and that state would have been expanded first.
• Consistency (or monotonicity): h(n) ≤ cost(n → n') + h(n') for every edge — a triangle inequality. It implies admissibility and something more: f values never decrease along a path, so the first time a state leaves the heap, its g is final — exactly Dijkstra's invariant, preserved. With a consistent h the usual "closed" set suffices; with an admissible but inconsistent h, a closed state may have to be reopened.
• Extreme cases that place A* on the map: with h = 0 (trivially admissible and consistent), A* is UCS/Dijkstra; with h = h* (the perfect heuristic), A* goes straight to the goal without expanding anything superfluous. Every real heuristic lives between the two: the more "informed" (larger without going over), the fewer nodes it expands.

For grid movement with steps of cost ≥ 1, the canonical heuristic is the Manhattan distance: |r1 − r2| + |c1 − c2|. It is admissible (no real path can be shorter than ignoring all the obstacles) and consistent (moving one cell changes the estimate by at most ±1, and the step costs at least 1).

The Rutalia van leaves the depot D and must reach the customer C in a neighborhood under construction (# = blocked street). We implement full A*, with a counter of expanded nodes for the experimental comparison to come.

The fine points of the code, one by one:

• The goal test happens when EXTRACTING from the heap, not when generating the successor. Testing at generation time is a classic mistake: you could find the goal via an expensive path while a cheap one waits in the heap. At extraction, the consistency of h guarantees its g is already optimal (the same argument as Dijkstra's invariant in 03-03).
• best_g + lazy deletion: the identical pattern to our Dijkstra from module 3 — stale entries are allowed in the heap and discarded on the way out by comparing against the best known g.
• The heap tuple is (f, g, state): it orders by f; including g as the second criterion breaks ties in favor of more advanced states, a practical detail that tends to reduce expansions.
• UCS for free: passing h = lambda n, goal: 0 turns the function into implicit Dijkstra, touching nothing else. It is the best demonstration that A* generalizes Dijkstra.

Let's run the variants on the same map and count expansions:

Both return a path of the same length — both are optimal — but A* expands considerably fewer nodes. On a 10×10 map the difference is modest; the gap widens with the size of the space: on large grids with scattered obstacles, A* with Manhattan expands orders of magnitude fewer nodes than Dijkstra, because the latter fills in the whole circle of radius 18 while A* digs a corridor toward the goal. I suggest making the experiment a habit: whenever you implement A*, instrument the expansion counter and compare it against h = 0. It is the honest way to know how much your heuristic is worth (and to detect broken heuristics: if A* expands more than Dijkstra, something is wrong — h is probably not consistent or is badly scaled).

What if we give up optimality in exchange for speed? If h overestimates, A* may return suboptimal paths, but it usually expands far fewer nodes. The controlled version of this idea is weighted A*: use f(n) = g(n) + w·h(n) with w > 1. It can be proven that the returned path costs at most w times the optimum — an explicit, tunable trade-off. For the Rutalia van, a w = 1.2 ("I accept routes up to 20% longer") can cut planning time drastically on large maps; it is the same spirit as the metaheuristics of module 2 (02-04, 02-05): trading guarantee for time, but here with a provable quality bound.

The other practical limit of A* is memory: the heap and best_g grow with the nodes generated. IDA* (iterative deepening A*) applies the iterative-deepening idea: DFS with a threshold on f that increases on each pass. O(d) memory while keeping optimality, at the price of repeated work. It is the classic algorithm for puzzles with gigantic spaces (the 15-puzzle was solved optimally with IDA*); we leave it as a mention.

In 02-03, backtracking and branch and bound also explored state trees — in fact, best-first B&B used a heap of nodes with optimistic bounds, suspiciously similar to A*. It is worth closing the exploration arc of the course with the complete map, because confusing the two families is common:

The two families share DNA (generate successors, prioritize with an optimistic estimate, use a heap), which is why best-first B&B and A* are nearly the same algorithm with a different purpose. The criterion for choosing: if your problem is "find the path/sequence to a goal", think A*; if it is "find the best complete solution among all combinations", think B&B. Rutalia's TSP was the latter; steering the van through the neighborhood under construction is the former.

• Testing the goal at generation instead of extraction. The most frequent bug in A*/UCS: it returns suboptimal paths intermittently and is hard to reproduce. The goal test goes when the state leaves the heap.
• A heuristic that overestimates "just a little". Using the Euclidean distance ×1.5, or Manhattan when diagonal movement is allowed (there Manhattan overestimates and the admissible choice is the Chebyshev or octile distance). Goodbye optimality, and silently so: the returned path looks reasonable. Always justify why h cannot exceed the true cost.
• Forgetting the visited set/best_g in spaces with cycles. The symptom is a program that "hangs" or eats memory without end: it is re-expanding the same states via different paths.
• Putting less (or more) than necessary into the state. If the van cannot pass twice through the same cell because temporary roadworks depend on the hour, the state must include time; if it doesn't, A* will produce illegal routes. Conversely, adding irrelevant information (the fuel level when it constrains nothing) multiplies the space for no reason.
• A heuristic that is expensive to compute. If evaluating h costs more than it saves in expansions, A* loses to Dijkstra in total time even while expanding fewer nodes. Measure both things: expansions and seconds.
• Tip: good heuristics usually come from relaxing the problem (remove constraints and solve the relaxed version exactly): Manhattan is "the problem without obstacles". It is the same idea as the optimistic bounds of 02-03 — relaxation = optimistic estimate, and optimistic = admissible.

Exercise 1 — State design. The Rutalia van delivers on the grid, but now it must first pass through the pickup point R before going to the customer C. Define the state space formally (state, operators, initial, goal, cost) without writing code, and reason it out: why isn't the state (row, col) enough? How many states does the new space have relative to the original?

Exercise 2 — Admissible heuristics. For the problem of exercise 1 (pass through R and then reach C), three heuristics are proposed from a state at position p that has not yet picked up: (a) manhattan(p, C); (b) manhattan(p, R); (c) manhattan(p, R) + manhattan(R, C). State which are admissible and which dominates the others (more information without overestimating). Justify each one.

Exercise 3 — Weighted A* experiment. Modify a_star to accept a weight w (f = g + w·h) and run it on GRID with w ∈ {0, 1, 1.5, 3}. For each w record the path length and the nodes expanded, and explain the pattern you observe. Which w corresponds to Dijkstra? And to a pure greedy "best-first by heuristic"?

Solution 1: the state must be (row, col, picked_up) with picked_up ∈ {False, True}: position alone does not determine the legal moves toward the goal, because being at C is only a goal if R was already visited. Operators: the usual four moves; on entering cell R, the successor has picked_up=True. Initial: (D_r, D_c, False). Goal: (C_r, C_c, True). Cost: 1 per move. The space doubles (each cell exists in two "layers", before and after pickup): from 66 free cells to 132 states. This is the general pattern: every bit of memory relevant to the future multiplies the space — which is why designing the minimal sufficient state matters so much.

Solution 2:

• (a) manhattan(p, C): admissible — the real path must end at C, and no path to C is shorter than the direct Manhattan distance; but it is poorly informed: it ignores the mandatory detour through R.
• (b) manhattan(p, R): admissible — every valid path must first pass through R, and reaching R costs at least that; it also ignores part of the work (from R to C).
• (c) manhattan(p, R) + manhattan(R, C): admissible and dominant — the real path decomposes into "reach R" (≥ manhattan(p, R)) plus "R to C" (≥ manhattan(R, C)); the sum of two lower bounds on mandatory, disjoint segments is a lower bound on the total. Since (c) ≥ (a) and (c) ≥ (b) in every state without overestimating, it dominates: A* with (c) expands a subset of the nodes it would expand with the others. In the picked_up=True layer, the right heuristic is simply manhattan(p, C).

Solution 3:

Interpretation: w=0 cancels the heuristic — it is exactly Dijkstra. w=1 is optimal A*. As w grows, the h term dominates over g and the algorithm tends toward greedy best-first (f = h, the limit w→∞), which rushes toward whatever looks close without accounting for what has already been spent — extremely fast and guarantee-free, the same character as the greedy counterexamples of 02-02. Exact values depend on the map and on tie-breaking; the qualitative pattern (expansions ↓, quality ↓ beyond w > 1) is what should come out.

This lesson closes module 4 and, with it, a complete arc of the course. A state space is an implicit graph — state, operators, goal, cost — too large to materialize, and over it we have reused the whole module 3 arsenal in "on the fly" form: BFS when steps cost the same, UCS/Dijkstra when they don't, and A* when we can also estimate what remains, with admissibility as the contract of optimality and consistency as the safeguard of the heap invariant. The expanded-nodes experiment delivers the module's moral: information is performance — an honest heuristic (born from relaxing the problem, like the bounds of 02-03) turns the exploration from a blind circle into a directed corridor, and the weight w lets you buy speed by paying with guarantees, in a measurable way. We have also drawn the mental frontier between searching for the best path (this lesson) and searching for the best configuration (backtracking and B&B from module 2): same DNA, different question.

Now look at the whole: in module 2 we optimized with rules that we designed; in module 3 we modeled the city as a graph with weights that we measured; in this module we searched, sorted and planned with invariants and heuristics that we justified. All the problem knowledge has been supplied by hand. But Rutalia has something we have not yet exploited: millions of historical records — deliveries with their time, zone, weight, delay, incidents — containing patterns that nobody has written down as a rule. How long will this delivery really take? Which customers will generate an incident? Which zones behave alike? In module 5 we change paradigm: instead of writing the rules, we will let algorithms learn them from the data. We start in 05-01 with the fundamentals of machine learning.