In the previous lesson we formalised NovaMarket's delivery map as the graph CITY_GRAPH and checked that brute force chokes as soon as the deliveries grow: it evaluates n! routes and the vast majority are physically impossible. In this lesson we are going to solve the problem intelligently. We will start with the simplest and most important case: taking the van from Warehouse_Getafe to a destination district by the best path, building the solution step by step, only along real roads, and without enumerating anything unnecessary. We will introduce the vocabulary of search (state space, node, frontier, explored set), the criteria by which a search algorithm is judged, and then implement five classic algorithms on the same graph: three uninformed ones (breadth-first, depth-first and uniform-cost, which only know the graph) and two informed ones (greedy and A*, which also use an estimate of what remains to the goal). You will see through traces and tables why breadth-first search does not always give the shortest path in kilometres, why depth-first can return bad paths, and how a heuristic as simple as straight-line distance lets A* find the optimum while exploring less. These algorithms are the heart of any route planner, and we will reuse them in the exercise project of module 9 (09-01).

1. Search vocabulary: state space, node, frontier, explored set, path and cost
2. Search tree versus graph: the problem of repeated states
3. How a search algorithm is evaluated: completeness, optimality, complexity
4. The general scheme and the working graph
5. Breadth-first search (BFS) with deque, with a step-by-step trace
6. Depth-first search (DFS): the same idea with a stack
7. Uniform-cost search (Dijkstra) with heapq
8. Informed search: heuristics, admissibility and consistency
9. Greedy best-first search
10. A*: the best of both worlds, with a trace
11. Comparison table and when to use each one

Recall the problem formulation of 02-01 and 03-01: initial state, actions, transition model, goal test and cost. On top of that formulation, search algorithms handle a few concepts that are worth pinning down precisely, because they appear in the code of every one of them:

Every search works by repeating the same loop: take a node out of the frontier, check whether it is a goal, and if not, expand it, adding its successors to the frontier. The only difference between the algorithms in this lesson is which node is taken out of the frontier at each step. That choice is the "search strategy", and it determines whether a solution is found, whether it is the best one and how much it costs to find it.

It is important not to confuse two things: the state-space graph (the map: 8 nodes, 12 edges, fixed) and the search tree the algorithm builds as it explores (root = initial state; children = successors; every branch is a path). The same state can appear in several places of the tree: from Getafe you can reach Villaverde directly or via Leganes, and both would be different tree nodes with the same state.

If we do not control those repeated states, the tree grows without bound (Getafe → Leganes → Getafe → Leganes…) even though the graph is tiny. The standard solution is graph search: remember the states already explored (and those already in the frontier) and never generate them again. That is what the parents set/dictionary does in our implementations: besides remembering where we came from (to reconstruct the path at the end), it acts as "already seen". The memoryless variant is called tree search and only makes sense in spaces without cycles, such as the game trees of 03-03.

Four criteria, which we will use in the final table:

• Completeness: does it guarantee finding a solution if one exists?
• Optimality: does it guarantee that the solution found is the one with the lowest cost?
• Time complexity: how many nodes does it generate or expand? It is expressed in terms of the branching factor b (average number of successors per node; about 3 in our graph) and the depth d of the solution (number of steps). A tree with branching b and depth d has of the order of bᵈ nodes, so almost every complexity has the form O(bᵈ): exponential, as 03-01 anticipated.
• Space complexity: how many nodes does it hold in memory at once? This is where breadth-first and depth-first differ most.

We will always work with the CITY_GRAPH from 03-01, reproduced here as a reminder, plus two helper functions shared by every algorithm: reconstruct_path, which follows the chain of parents from the goal back to the start, and path_cost, which adds up the kilometres of a path.

The parents dictionary is the key piece of every implementation: parents[X] = Y means "X was reached from Y". The initial node has parent None, and that is what stops the loop in reconstruct_path. The problem we will solve in every section is getting from Warehouse_Getafe to Retiro, the district furthest from the warehouse, for which several reasonable paths exist.

Strategy: expand the shallowest nodes first. The frontier is a FIFO queue (deque): nodes come out in the same order they went in, so first all the nodes one step from the start are expanded, then those two steps away, and so on. It explores the map "in concentric waves" from the warehouse.

The trace (frontier and explored set after expanding each node) is this:

Read it carefully: in step 6, when Vallecas is expanded, Retiro is generated for the first time and parents["Retiro"] = "Vallecas" is recorded. When Arganzuela is expanded in step 7, Retiro is already in parents and is not updated, even though the path via Arganzuela is shorter in kilometres. BFS finds the path with the fewest legs (3), not the fewest kilometres: 18.5 km, when the optimum is 17.0 km via Villaverde–Usera–Arganzuela (4 legs). That is the fundamental limitation of BFS: it is optimal only if every action costs the same. It is complete (if a solution exists, it finds it), and its time and space cost is O(bᵈ): it holds the whole current "wave" in the frontier, which on large maps takes a lot of memory.

Strategy: always expand the deepest node, that is, follow one path to the end before trying alternatives. The code is literally that of BFS with the queue swapped for a stack (append/pop on a list): just as we announced in 03-01, the data structure defines the algorithm.

DFS has explored fewer nodes (6 versus 8), but returns a clearly worse path: 25 km, 5 legs. It "dived" into Leganes, carried on to Carabanchel and Usera, and from there kept taking the first unvisited exit until it stumbled upon Retiro. Characteristics:

• It is not optimal: it returns the first path it finds, not the best one.
• It may not be complete: in infinite spaces, or with cycles and no repeated-state control, it can follow an endless path and never come back. With our parents as a visited check and a finite graph, it does terminate.
• Its great advantage is memory: it only stores the current path and the pending siblings, O(b·m) where m is the maximum depth, versus BFS's O(bᵈ). That is why it is used in problems with huge numbers of states where any solution will do (and in the minimax recursion of 03-03, which is a depth-first search).

A common variant, depth-limited search (cutting off at a maximum depth), and its iterative version (deepen to 1, 2, 3… until a solution is found), combines the low memory of DFS with the completeness of BFS; we mention it for completeness but will not implement it.

Strategy: always expand the frontier node with the lowest accumulated cost g. The frontier is a priority queue, which we implement with heapq, a binary heap in which heappop always returns the smallest tuple. It is Dijkstra's algorithm seen as a search, and unlike BFS it does take the kilometres into account.

Notice three details that explain why it works:

• In step 5, when Usera is expanded, it turns out that Arganzuela is 13.0 km away (via Usera) instead of 14.0 (via Carabanchel). Arganzuela's parent is reassigned and a new entry is pushed onto the heap. The old one (14.0) becomes stale; when it comes out, the if node in explored: continue discards it. This is simpler than deleting it from the heap and is the usual technique ("lazy deletion").
• In step 6 Retiro is generated with 18.5 km (via Vallecas), but it is not declared a solution on generation: we wait for it to come out of the heap. In step 7 Retiro shows up with 17.0 km and, being lower, comes out first. Had we tested the goal on generation, we would have returned 18.5 km. This difference from BFS (which can legitimately test on generation) is subtle but decisive.
• The result is optimal: 17.0 km. Uniform-cost search is complete and optimal as long as costs are positive, at the price of exploring in every direction with no idea of where the goal is (here it expanded all 8 nodes, including Leganes, which lies in the opposite direction).

The three previous algorithms are uninformed: they know only what the graph says. A human driver, by contrast, knows that Retiro "is up north" and would never think of heading out towards Leganes. That intuition is formalised as a heuristic function h(n): a cheap estimate of the remaining cost from node n to the goal. The most natural heuristic on maps is straight-line distance: there is never a road shorter than the straight line, and it is computed instantly from coordinates.

We fix the coordinates (in kilometres, on a fictional plane with the warehouse at the origin) of the nodes of CITY_GRAPH, and the Euclidean heuristic:

Two properties of a heuristic determine whether A* will be optimal:

• Admissible: it never overestimates the real remaining cost, h(n) ≤ minimum real cost from n to the goal. Straight-line distance is admissible by construction: the road is always at least as long as the straight line. You can check it edge by edge in our graph (for example, Usera–Arganzuela: 3.5 km of road versus 3.16 km in a straight line).
• Consistent (or monotone): for every leg n → n' of cost c, h(n) ≤ c + h(n') holds. Intuitively, "the estimate cannot drop by more than the leg costs"; it is equivalent to the triangle inequality, which Euclidean distance always satisfies. Every consistent heuristic is admissible; in practice, almost every natural heuristic is. With a consistent heuristic, the first time A* pops a node from the frontier it already does so with its optimal cost, and that is why we can close nodes (explored) without ever reopening them.

A heuristic that overestimates can lead A* to discard the optimal path because it looks expensive (you will see it in exercise 2). A heuristic that underestimates too much (in the extreme, h = 0) is still admissible but does not help: A* with h = 0 is exactly uniform-cost search.

Strategy: always expand the node that looks closest to the goal, that is, the one with the lowest h(n), completely ignoring what has already been driven (g). It is the direct translation of "always head towards Retiro".

It is extremely fast (only 4 nodes explored: it never looks towards Leganes or Carabanchel), but it is not optimal: from Villaverde, Vallecas (h = 5.00) looks closer to Retiro than Usera (h = 5.39), so it goes via Vallecas, without realising that the Villaverde–Vallecas leg costs 7.5 km and the whole detour comes to 18.5 km. It has fallen into the trap of looking only at the estimated future and not the real past. Moreover, without repeated-state control, greedy search can get into loops (it is not complete in general). Its real usefulness is as a component of other methods and as an "emergency" algorithm when response time is everything.

Strategy: expand the node with the lowest f(n) = g(n) + h(n): real cost driven plus estimated remaining cost. It combines the guarantee of uniform-cost (which looks at g) with the direction of greedy (which looks at h). The code is that of uniform-cost with the priority changed:

A* returns the optimum (17.0 km), like uniform-cost, but steered by the heuristic: it heads straight for Villaverde (f = 14.06 < 15.90 for Leganes), continues via Usera and Arganzuela, and only when those options have a higher f than Leganes does it go back to check it. Vallecas, the greedy trap, has f = 17.50 and never gets expanded. On such a small graph the saving is modest (7 nodes versus 8), but on a real map with thousands of junctions the difference between uniform-cost and A* is orders of magnitude: A* explores an "ellipse" around the straight line between origin and destination, whereas uniform-cost explores a full circle around the origin.

Properties: A* is complete and optimal if h is admissible (in tree search) or consistent (in graph search, like ours). Its complexity is still exponential in the worst case, but it drops drastically the better the heuristic; and its weak point is memory, because it stores the whole frontier just like BFS.

Results on CITY_GRAPH for three different destinations (kilometres of the returned path / nodes explored):

And the theoretical summary (b = branching factor, d = solution depth, m = maximum depth):

Marta's rule of thumb for the NovaMarket planner: A* with straight-line distance to compute the best path between two points; uniform-cost (Dijkstra) when the distances from one point to all the others are needed (which is exactly what we will need in 03-04 to build the distance matrix between stops); BFS only for "how many hops" questions; DFS and greedy as auxiliary pieces.

• Testing the goal on generation instead of on popping in uniform-cost and A*: it returns the first path that touches the goal, not the best one (here it would have given 18.5 km instead of 17.0). In BFS it is correct to test on generation, because every path of the same depth costs the same.
• Using list.pop(0) for the BFS queue: it is O(n) per extraction; deque.popleft() is O(1).
• Forgetting repeated-state control: without parents (or a visited set), DFS and greedy can cycle indefinitely between two connected districts.
• Not allowing the parent to be reassigned in uniform-cost/A*: if you treat parents as in BFS (assigned only the first time), you lose the Carabanchel→Usera improvement for Arganzuela and stop being optimal. The correct condition is new_g < best_g[neighbour].
• Pushing tuples that cannot be compared onto the heap: if two entries tie on f and on g, Python compares the third element; with strings it works, with objects that have no defined ordering it raises an error. Add a counter as a tie-break if your nodes are not comparable.
• Heuristic in different units from the cost: if the cost is in minutes and h in kilometres, A* loses its guarantees. Convert h to the same unit (for example, km / maximum speed → minutes), which also keeps it admissible.
• Confusing "explores fewer nodes" with "better": DFS and greedy explore less and return worse paths. Choose according to what you need to guarantee (optimality, memory, response time), not by the node counter.

Without running code, build the A* trace table from Warehouse_Getafe to Carabanchel (use the coordinates table to compute h with math.hypot or by hand). How many nodes does it expand and which path does it return? Compare it with what uniform-cost would expand for the same destination. Then verify your table with a_star(..., trace=True).

Suppose someone enters Arganzuela's coordinates wrongly in COORDINATES and puts (10, 16) instead of (1, 10). Compute the new h(Arganzuela, Retiro), check whether it is still admissible (compare it with the real cost Arganzuela → Retiro, which is 4.0 km) and run a_star towards Retiro. Which path does it return and why? Restore the coordinates when you finish.

Write a loop that, for every node of the graph as destination, runs bfs and uniform_cost from Warehouse_Getafe and prints the number of legs and the kilometres of each path. On which destinations do they disagree, and why precisely on those?

Solution 1. h towards Carabanchel (−2, 7): Getafe 7.28; Leganes 4.12; Villaverde 6.40; Carabanchel 0.

A* expands only 3 nodes and returns Warehouse_Getafe -> Leganes -> Carabanchel (9.0 km). Uniform-cost reaches the same path, but expands 4 (Getafe, Leganes, Villaverde and Carabanchel), because Villaverde with g = 5.0 comes out of the heap before Carabanchel with g = 9.0: without a heuristic it has no way of knowing that Villaverde lies in the opposite direction.

Solution 2. With (10, 16), h(Arganzuela, Retiro) = √(6² + 4²) = 7.21 km, higher than the real cost of 4.0 km: the heuristic is no longer admissible. When A* runs towards Retiro, Arganzuela now has f = 13.0 + 7.21 = 20.21, higher than the f of Retiro via Vallecas (12.5 + 6.0 + 0 = 18.50), so A* pops Retiro via Vallecas before expanding Arganzuela and returns Warehouse_Getafe -> Villaverde -> Vallecas -> Retiro with 18.5 km: it has lost optimality (17.0 km) because of an overestimate. It is the practical demonstration of section 8: admissibility is not a technicality, but the condition that makes A* reliable.

Solution 3.

They disagree on Arganzuela (BFS: 3 legs via Leganes–Carabanchel, 14.0 km; UCS: 3 legs via Villaverde–Usera, 13.0 km) and on Retiro (BFS: 3 legs, 18.5 km; UCS: 4 legs, 17.0 km). For Arganzuela both use 3 legs, but BFS keeps the first one it discovers (by expansion order, the one via Carabanchel) without looking at kilometres; for Retiro, the path with the fewest legs is not the one with the fewest kilometres. For the other destinations the path with the fewest legs coincides with the one with the fewest kilometres, which is why both algorithms agree; but that is a coincidence of the map, not a guarantee.

We have turned problem formulation into algorithms that work. They all share the same skeleton (frontier, explored set, parents, pop-test-expand loop) and differ only in which node leaves the frontier first: the oldest (breadth-first, with deque), the most recent (depth-first, with a stack), the one with the lowest accumulated cost g (uniform-cost, with heapq), the one with the lowest estimate h (greedy) or the one with the lowest g + h (A*). We have seen through traces on CITY_GRAPH that BFS minimises legs and not kilometres, that DFS saves memory but returns bad paths, that uniform-cost is optimal but explores in every direction, that greedy is fast but falls into traps, and that A* with an admissible and consistent heuristic (the straight-line distance computed from COORDINATES) obtains the optimum while exploring less. We have also learnt to evaluate any search algorithm by its completeness, optimality and time and space complexity.

So far the van has been finding its way in a world that does not react: the map does not change because the van moves. In the next lesson, Adversarial Search: Games and Minimax, we will introduce a second agent with opposing goals, who answers each of our decisions with one of its own. We will see how that situation is represented as a game tree, how the minimax algorithm chooses the best move assuming the opponent also plays as well as possible, and how alpha-beta pruning lets it do so while exploring a fraction of the tree; we will try it out on noughts and crosses and take it to a NovaMarket situation with a competitor.