Module 8 ended with a promise: to consolidate, hands on, what modules 3 to 8 gave you in theory, code and judgement. We start where the technical part of the course started, with the algorithms of module 3: uninformed search (BFS, DFS), uniform-cost search, A* with a heuristic, minimax with alpha-beta pruning, and optimisation with local search, simulated annealing and genetic algorithms. Every exercise uses NovaMarket's delivery map (CITY_GRAPH and COORDINATES from 03-02) and the assignment of orders between Getafe and Zaragoza from 03-04, so the figures you already know (17.0 km to Retiro, 39.0 km for the travelling salesman, €257 for the assignment) will serve as your yardstick. Everything is pure Python with the standard library.
How to work through the lesson: read the statement and the hints, try to solve it in your editor (half an hour per exercise is reasonable; the final challenge, an hour), and only then compare with the solution and read the feedback. If you get stuck, go back to the reference lesson given in each reminder; copying the code from 03-02 or 03-04 and adapting it is exactly what a professional would do. Difficulty grows from exercise 1 to exercise 6.
Contents
- Shared setup: graph, coordinates and utilities
- Exercise 1: BFS and DFS, reachable districts and a closed road
- Exercise 2: Dijkstra from the warehouse, paths and the best delivery point
- Exercise 3: A* with a new district, admissibility and expanded nodes
- Exercise 4: minimax and alpha-beta in the two-week price war
- Exercise 5: travelling salesman with time windows, hill climbing versus annealing
- Exercise 6 (challenge): assignment with capacity and route cost using a genetic algorithm
- Common Mistakes and Tips
- Conclusion
- Shared setup: graph, coordinates and utilities
Save this as nm_graph.py (or paste it at the top of each script): it is the map from 03-02 with its two utilities. Everything else is built on top of it.
from collections import deque
import heapq, math, random, itertools
CITY_GRAPH = {
"Warehouse_Getafe": [("Leganes", 4.5), ("Villaverde", 5.0)],
"Leganes": [("Warehouse_Getafe", 4.5), ("Carabanchel", 4.5), ("Villaverde", 6.5)],
"Villaverde": [("Warehouse_Getafe", 5.0), ("Leganes", 6.5), ("Usera", 4.5), ("Vallecas", 7.5)],
"Carabanchel": [("Leganes", 4.5), ("Usera", 4.5), ("Arganzuela", 5.0)],
"Usera": [("Villaverde", 4.5), ("Carabanchel", 4.5), ("Arganzuela", 3.5), ("Vallecas", 5.5)],
"Vallecas": [("Villaverde", 7.5), ("Usera", 5.5), ("Retiro", 6.0)],
"Arganzuela": [("Carabanchel", 5.0), ("Usera", 3.5), ("Retiro", 4.0)],
"Retiro": [("Arganzuela", 4.0), ("Vallecas", 6.0)],
}
COORDINATES = {"Warehouse_Getafe": (0, 0), "Leganes": (-3, 3), "Villaverde": (3, 3), "Carabanchel": (-2, 7),
"Usera": (2, 7), "Vallecas": (7, 8), "Arganzuela": (1, 10), "Retiro": (4, 12)}
def reconstruct_path(parents, goal):
path = [goal]
while parents[path[-1]] is not None:
path.append(parents[path[-1]])
return path[::-1]
def path_cost(graph, path):
return sum(dict(graph[a])[b] for a, b in zip(path, path[1:]))
- Exercise 1: BFS and DFS, reachable districts and a closed road
Reminder (03-02, sections 5 and 6). BFS uses a FIFO queue and finds the path with the fewest hops (not the fewest kilometres); DFS uses a stack and returns the first path it finds, with little memory and no guarantee of quality. Both use the parents dictionary as their visited record.
Statement. Diego wants to know, for this morning's delivery run from Warehouse_Getafe:
- Which districts are reachable and how many hops away each one is (a function
reachable_bfs(graph, start)that returns{district: number of hops}). - The path with the fewest hops to Vallecas with BFS, and the one DFS returns; compare hops and kilometres.
- Roadworks on the M-40 close the Villaverde–Vallecas road. Write
without_edge(graph, a, b), which returns a copy of the graph without that road in both directions (without modifying the original), and repeat questions 1 and 2. How many roads have to be closed for Vallecas to stop being reachable?
Hints: for question 1 the BFS loop is enough, recording hops[neighbour] = hops[node] + 1; to copy the graph use a dictionary comprehension that filters out the edge {n, v} == {a, b}.
Solution
def reachable_bfs(graph, start):
frontier, hops = deque([start]), {start: 0}
while frontier:
node = frontier.popleft()
for neighbour, _ in graph[node]:
if neighbour not in hops: # first time seen: minimum depth
hops[neighbour] = hops[node] + 1
frontier.append(neighbour)
return hops
def bfs(graph, start, goal):
frontier, parents, explored = deque([start]), {start: None}, []
while frontier:
node = frontier.popleft(); explored.append(node)
if node == goal:
return reconstruct_path(parents, goal), explored
for neighbour, _ in graph[node]:
if neighbour not in parents:
parents[neighbour] = node; frontier.append(neighbour)
return None, explored
def dfs(graph, start, goal):
stack, parents, explored = [start], {start: None}, []
while stack:
node = stack.pop(); explored.append(node)
if node == goal:
return reconstruct_path(parents, goal), explored
for neighbour, _ in reversed(graph[node]): # reversed: expand in list order
if neighbour not in parents:
parents[neighbour] = node; stack.append(neighbour)
return None, explored
def without_edge(graph, a, b):
"""Copy of the graph without the road a-b (in both directions); the original is untouched."""
return {n: [(v, d) for v, d in adj if {n, v} != {a, b}] for n, adj in graph.items()}
print(reachable_bfs(CITY_GRAPH, "Warehouse_Getafe"))
for name, f in (("BFS", bfs), ("DFS", dfs)):
p, ex = f(CITY_GRAPH, "Warehouse_Getafe", "Vallecas")
print(f"{name}: {' -> '.join(p)} | hops {len(p)-1} | km {path_cost(CITY_GRAPH, p)} | explored {len(ex)}")
G2 = without_edge(CITY_GRAPH, "Villaverde", "Vallecas")
print(reachable_bfs(G2, "Warehouse_Getafe"))
p, ex = bfs(G2, "Warehouse_Getafe", "Vallecas")
print(f"BFS without the road: {' -> '.join(p)} | hops {len(p)-1} | km {path_cost(G2, p)}")
G4 = without_edge(without_edge(G2, "Usera", "Vallecas"), "Retiro", "Vallecas")
print(bfs(G4, "Warehouse_Getafe", "Vallecas")[0], reachable_bfs(G4, "Warehouse_Getafe")){'Warehouse_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Vallecas': 2, 'Arganzuela': 3, 'Retiro': 3}
BFS: Warehouse_Getafe -> Villaverde -> Vallecas | hops 2 | km 12.5 | explored 6
DFS: Warehouse_Getafe -> Leganes -> Carabanchel -> Usera -> Vallecas | hops 4 | km 19.0 | explored 5
{'Warehouse_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Arganzuela': 3, 'Vallecas': 3, 'Retiro': 4}
BFS without the road: Warehouse_Getafe -> Villaverde -> Usera -> Vallecas | hops 3 | km 15.0
None {'Warehouse_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Arganzuela': 3, 'Retiro': 4}Reading: all 7 districts are reachable (the graph is connected) and BFS gives the minimum depth of each one in a single pass. Vallecas is reached in 2 hops (12.5 km, which here happens to be the optimum in km as well); DFS explores one node fewer but returns 4 hops and 19 km. With the Villaverde–Vallecas road closed, Vallecas moves to 3 hops via Usera (15.0 km) and Retiro to 4; and you have to close all three of Vallecas's roads (Villaverde, Usera and Retiro) to isolate it: bfs returns None and reachable_bfs no longer lists it.
Feedback
- Typical mistake: modifying
CITY_GRAPHin place withremoveand "dragging" the closure into the following exercises; the copy via comprehension avoids that hidden state. - Another one: removing the edge in one direction only; the graph is undirected and you have to filter both lists (that is why we compare the sets
{n, v}). - Variants: write a recursive
dfsand check that it returns the same path; compute the minimum number of closures needed to isolate each district (the node's degree is an upper bound); add a depth limit tobfsand observe when it stops finding Retiro.
- Exercise 2: Dijkstra from the warehouse, paths and the best delivery point
Reminder (03-02 section 7 and 03-04 section 3). Uniform-cost search (Dijkstra) always expands the node with the lowest accumulated cost g using a heap (heapq), can reassign the parent of a node if a better path shows up, and discards stale entries from the heap. Run without a goal, it gives the minimum distance to every node.
Statement. Write full_dijkstra(graph, origin), which returns (dist, parents, closing_order) for all nodes, and use it for: (a) a table with the minimum distance from Warehouse_Getafe to each district and the reconstructed path; (b) the edges of the graph that no shortest path from the warehouse uses; (c) the complete distance matrix (running it from every node) and a check that it is symmetric; (d) Marta wonders where an urban delivery point should be if it could be chosen freely among the 8 nodes: the one that minimises the sum of minimum distances to all the others. Which is it, and how much does it save compared with the Getafe warehouse?
Solution
def full_dijkstra(graph, origin):
dist, parents, frontier, closed = {origin: 0.0}, {origin: None}, [(0.0, origin)], []
while frontier:
g, node = heapq.heappop(frontier)
if node in closed: # stale entry
continue
closed.append(node)
for neighbour, d in graph[node]:
if neighbour not in dist or g + d < dist[neighbour]:
dist[neighbour], parents[neighbour] = g + d, node
heapq.heappush(frontier, (g + d, neighbour))
return dist, parents, closed
dist, parents, order = full_dijkstra(CITY_GRAPH, "Warehouse_Getafe")
for n in order:
print(f"| {n} | {dist[n]:.1f} | {' -> '.join(reconstruct_path(parents, n))} |")
used = {frozenset((parents[n], n)) for n in parents if parents[n]}
all_edges = {frozenset((a, b)) for a in CITY_GRAPH for b, _ in CITY_GRAPH[a]}
print("Unused edges:", sorted(tuple(sorted(e)) for e in all_edges - used))
MATRIX = {n: full_dijkstra(CITY_GRAPH, n)[0] for n in CITY_GRAPH}
print("Symmetric:", all(MATRIX[a][b] == MATRIX[b][a] for a in MATRIX for b in MATRIX))
for n in MATRIX:
print(f"{n:17s} sum {sum(MATRIX[n].values()):5.1f} farthest: {max(MATRIX[n], key=MATRIX[n].get)}")| District (closing order) | km | Shortest path |
|---|---|---|
| Warehouse_Getafe | 0.0 | — |
| Leganes | 4.5 | Getafe → Leganes |
| Villaverde | 5.0 | Getafe → Villaverde |
| Carabanchel | 9.0 | Getafe → Leganes → Carabanchel |
| Usera | 9.5 | Getafe → Villaverde → Usera |
| Vallecas | 12.5 | Getafe → Villaverde → Vallecas |
| Arganzuela | 13.0 | Getafe → Villaverde → Usera → Arganzuela |
| Retiro | 17.0 | Getafe → Villaverde → Usera → Arganzuela → Retiro |
Unused edges: [('Arganzuela', 'Carabanchel'), ('Carabanchel', 'Usera'), ('Leganes', 'Villaverde'), ('Retiro', 'Vallecas'), ('Usera', 'Vallecas')]
Symmetric: True
Warehouse_Getafe sum 70.5 farthest: Retiro
Leganes sum 61.5 farthest: Vallecas
Villaverde sum 52.5 farthest: Retiro
Carabanchel sum 51.0 farthest: Vallecas
Usera sum 44.0 farthest: Warehouse_Getafe
Vallecas sum 64.5 farthest: Leganes
Arganzuela sum 52.0 farthest: Warehouse_Getafe
Retiro sum 69.0 farthest: Warehouse_GetafeThe shortest paths from the warehouse form a tree (7 edges for 7 districts; the other 5 edges of the graph go unused). Nodes are closed in increasing order of distance, the property that guarantees optimality with positive costs. The matrix is the one from 03-04 and it is symmetric because the graph is undirected. And the best delivery point would be Usera (a sum of 44.0 km versus 70.5 for the warehouse): it is less than 10 km from any district; in practice this is the logic behind urban last-mile micro-hubs.
Feedback
- Typical mistake: testing the goal or "closing" a node when it is generated rather than when it is popped from the heap; in 03-02 we saw that this returns 18.5 km to Retiro instead of 17.0. Here, in addition,
parentsmust be overwritable: if you protect it withif neighbour not in parentsas in BFS, Arganzuela keeps the path via Carabanchel (14.0) instead of the one via Usera (13.0). - Compare with exercise 1: BFS and Dijkstra agree on hops except for Retiro (3 hops via Vallecas, 18.5 km, versus 4 hops and 17.0 km).
- Variant: convert km into minutes with different speeds per road (for example, 3 min/km on Usera–Arganzuela because of traffic) and check whether the tree changes; the algorithm does not change, only the weights.
- Exercise 3: A* with a new district, admissibility and expanded nodes
Reminder (03-02, sections 8 and 10). A* expands the node with the lowest f = g + h. With an admissible h (never overestimates) that is also consistent (h(n) ≤ c(n, n') + h(n'), the triangle inequality) it is optimal and expands fewer nodes than uniform-cost search; h = 0 turns it exactly into uniform-cost search.
Statement. NovaMarket opens deliveries in Moratalaz, at coordinates (8, 11), connected by two new roads: Vallecas–Moratalaz 3.5 km and Retiro–Moratalaz 4.5 km.
- Write
add_district(graph, coords, name, xy, edges), which returns extended copies of the graph and the coordinates. - Check that the Euclidean heuristic is still consistent: for every edge a–b, the straight-line distance must not exceed the road's km. Check admissibility towards Moratalaz too:
h(n, Moratalaz) ≤ true minimum distancefor every n (usefull_dijkstrafrom Moratalaz). - Solve Getafe → Moratalaz with uniform-cost search and with A*, and compare km and expanded nodes.
- Diego proposes recording the Vallecas–Moratalaz road as 3.0 km ("there's a shortcut"). What happens to the heuristic? And what if, instead, you multiply
hby 2 to "speed up" A*? Find an origin-destination pair where A* stops being optimal.
Solution
def add_district(graph, coords, name, xy, edges):
g = {n: lst[:] for n, lst in graph.items()}; c = dict(coords)
g[name], c[name] = [], xy
for neighbour, km in edges:
g[name].append((neighbour, km)); g[neighbour].append((name, km))
return g, c
def heuristic(coords, n, goal, w=1.0):
(x1, y1), (x2, y2) = coords[n], coords[goal]
return w * math.hypot(x2 - x1, y2 - y1)
def inconsistent_edges(graph, coords):
return [(a, b, km, round(heuristic(coords, a, b), 2)) for a in graph for b, km in graph[a]
if heuristic(coords, a, b) > km + 1e-9]
def non_admissible(graph, coords, goal):
real = full_dijkstra(graph, goal)[0]
return [(n, round(heuristic(coords, n, goal), 2), real[n]) for n in graph
if heuristic(coords, n, goal) > real[n] + 1e-9]
def a_star(graph, coords, start, goal, w=1.0):
h = lambda n: heuristic(coords, n, goal, w) # w=0 -> uniform-cost search
frontier, parents, best_g, closed = [(h(start), 0.0, start)], {start: None}, {start: 0.0}, []
while frontier:
f, g, node = heapq.heappop(frontier)
if node in closed: continue
closed.append(node)
if node == goal:
return reconstruct_path(parents, goal), g, closed
for neighbour, d in graph[node]:
if neighbour not in best_g or g + d < best_g[neighbour]:
best_g[neighbour], parents[neighbour] = g + d, node
heapq.heappush(frontier, (g + d + h(neighbour), g + d, neighbour))
return None, math.inf, closed
G_M, C_M = add_district(CITY_GRAPH, COORDINATES, "Moratalaz", (8, 11), [("Vallecas", 3.5), ("Retiro", 4.5)])
print("Inconsistent:", inconsistent_edges(G_M, C_M), "| non-admissible:", non_admissible(G_M, C_M, "Moratalaz"))
for name, w in (("Uniform cost", 0.0), ("A*", 1.0)):
p, g, ex = a_star(G_M, C_M, "Warehouse_Getafe", "Moratalaz", w)
print(f"{name}: {' -> '.join(p)} | {g} km | expanded {len(ex)}: {ex}")
G_3, C_3 = add_district(CITY_GRAPH, COORDINATES, "Moratalaz", (8, 11), [("Vallecas", 3.0), ("Retiro", 4.5)])
print("With 3.0 km:", inconsistent_edges(G_3, C_3), non_admissible(G_3, C_3, "Moratalaz"))
for a in G_M: # inflated heuristic (w=2): does it lose the optimum?
for b in G_M:
if a != b and a_star(G_M, C_M, a, b, 2.0)[1] > a_star(G_M, C_M, a, b, 0.0)[1]:
print("w=2 NOT optimal:", a, "->", b, a_star(G_M, C_M, a, b, 2.0)[1], "versus", a_star(G_M, C_M, a, b, 0.0)[1])Inconsistent: [] | non-admissible: []
Uniform cost: Warehouse_Getafe -> Villaverde -> Vallecas -> Moratalaz | 16.0 km | expanded 8: ['Warehouse_Getafe', 'Leganes', 'Villaverde', 'Carabanchel', 'Usera', 'Vallecas', 'Arganzuela', 'Moratalaz']
A*: Warehouse_Getafe -> Villaverde -> Vallecas -> Moratalaz | 16.0 km | expanded 4: ['Warehouse_Getafe', 'Villaverde', 'Vallecas', 'Moratalaz']
With 3.0 km: [('Vallecas', 'Moratalaz', 3.0, 3.16), ('Moratalaz', 'Vallecas', 3.0, 3.16)] [('Vallecas', 3.16, 3.0)]
w=2 NOT optimal: Vallecas -> Leganes 14.5 versus 14.0
w=2 NOT optimal: Moratalaz -> Leganes 18.0 versus 17.5| Node | h(n, Moratalaz) | True distance | h ≤ true? |
|---|---|---|---|
| Warehouse_Getafe | 13.60 | 16.0 | yes |
| Villaverde | 9.43 | 11.0 | yes |
| Usera | 7.21 | 9.0 | yes |
| Vallecas | 3.16 | 3.5 | yes |
| Retiro | 4.12 | 4.5 | yes |
A* reaches Moratalaz in 16.0 km expanding 4 nodes (it heads straight through Villaverde and Vallecas) against the 8 of uniform-cost search, which opens Leganes, Carabanchel, Usera and Arganzuela unnecessarily; summed over the 72 origin-destination pairs of the extended graph, A* expands 223 nodes and uniform-cost search 396. With the 3.0 km "shortcut" the road is shorter than the straight line (3.16 km): the heuristic stops being consistent and stops being admissible at Vallecas; on this graph A* still gets it right (losing the guarantee does not force a failure), but it is no longer guaranteed. With h × 2 it does fail: from Vallecas to Leganes it returns 14.5 km instead of 14.0, because the inflated heuristic makes it discard the optimal path for looking expensive.
Feedback
- Typical mistake: storing
(h, node)or(g, node)in the heap instead of(f, g, node); and forgetting that the admissibility check needs the true distances (Dijkstra from the goal), not the straight lines. - The edge-by-edge check (consistency) is the useful one in production: it is local, cheap and does not depend on the goal. If a road entry violates the straight line, it is almost always a data error (like Diego's "shortcut"), not a magic road.
- Variants: use the Manhattan distance
|dx| + |dy|as the heuristic and check whether it is admissible on this map (in general it is not for diagonal roads); measure expansions withw = 1.2("weighted" A*, which trades the guarantee for speed and is used in video games).
- Exercise 4: minimax and alpha-beta in the two-week price war
Reminder (03-03, sections 4, 6 and 8). Minimax walks the game tree depth-first and returns the value MAX can guarantee against a perfect MIN. Alpha-beta pruning gives the same result without visiting branches that cannot change the decision; its saving depends on the order of the children. generic_minimax(tree, utilities, node, is_max) works on a tree of dictionaries.
Statement. Marta extends the television price war from 03-03 to two weeks: NovaMarket chooses (hold, cut 5 %, cut 10 %); the competitor responds (holds, matches/cuts 5 %, cuts even further); and in the second week NovaMarket can hold its price or adjust (cut another 5 %). The leaves are the accumulated margin over the two weeks (thousands of euros):
| NovaMarket | Competitor | hold / adjust |
|---|---|---|
| hold | holds | 24 / 21 |
| hold | cuts 5 % | 10 / 11 |
| hold | cuts 10 % | 5 / 9 |
| cut 5 % | holds | 27 / 22 |
| cut 5 % | matches | 15 / 13 |
| cut 5 % | cuts 10 % | 8 / 11 |
| cut 10 % | holds | 25 / 18 |
| cut 10 % | matches | 11 / 9 |
| cut 10 % | cuts 15 % | 7 / 6 |
Build the tree as dictionaries, compute the minimax value of each initial option and the recommendation; write generic_alphabeta with a visited-node counter and compare: minimax, alpha-beta with the table order, alpha-beta trying first the option that won in 03-03 (cut_5), and alpha-beta with the perfect order (children sorted by their value). Does the recommendation change with respect to the one-week game (3/5/4)?
Solution
TREE = {"start": ["hold", "cut_5", "cut_10"],
"hold": ["h/comp_holds", "h/comp_cuts5", "h/comp_cuts10"],
"cut_5": ["c5/comp_holds", "c5/comp_matches", "c5/comp_cuts10"],
"cut_10": ["c10/comp_holds", "c10/comp_matches", "c10/comp_cuts15"]}
MARGIN = {"h/comp_holds": (24, 21), "h/comp_cuts5": (10, 11), "h/comp_cuts10": (5, 9),
"c5/comp_holds": (27, 22), "c5/comp_matches": (15, 13), "c5/comp_cuts10": (8, 11),
"c10/comp_holds": (25, 18), "c10/comp_matches": (11, 9), "c10/comp_cuts15": (7, 6)}
UTIL = {}
for resp, (h, a) in MARGIN.items(): # third level: hold / adjust
TREE[resp] = [resp + "/hold", resp + "/adjust"]
UTIL[resp + "/hold"], UTIL[resp + "/adjust"] = h, a
def generic_minimax(tree, util, node, is_max, count):
count[0] += 1
if node in util: return util[node]
values = [generic_minimax(tree, util, child, not is_max, count) for child in tree[node]]
return max(values) if is_max else min(values)
def generic_alphabeta(tree, util, node, is_max, count, alpha=-math.inf, beta=math.inf):
count[0] += 1
if node in util: return util[node]
best = -math.inf if is_max else math.inf
for child in tree[node]:
v = generic_alphabeta(tree, util, child, not is_max, count, alpha, beta)
if is_max: best, alpha = max(best, v), max(alpha, v)
else: best, beta = min(best, v), min(beta, v)
if alpha >= beta: break # PRUNE
return best
def order_children(tree, util, node, is_max):
"""Perfect order: children from best to worst for the player to move (uses minimax itself, for the experiment only)."""
if node in util: return util[node]
vals = {child: order_children(tree, util, child, not is_max) for child in tree[node]}
tree[node] = sorted(tree[node], key=vals.get, reverse=is_max)
return max(vals.values()) if is_max else min(vals.values())
for op in TREE["start"]:
print(f"{op:9s} -> guarantees {generic_minimax(TREE, UTIL, op, False, [0])}")
c = [0]; print("minimax:", generic_minimax(TREE, UTIL, "start", True, c), "nodes", c[0])
c = [0]; print("alpha-beta table order:", generic_alphabeta(TREE, UTIL, "start", True, c), "nodes", c[0])
import copy
T2 = copy.deepcopy(TREE); T2["start"] = ["cut_5", "hold", "cut_10"]
c = [0]; print("alpha-beta cut_5 first:", generic_alphabeta(T2, UTIL, "start", True, c), "nodes", c[0])
T3 = copy.deepcopy(TREE); order_children(T3, UTIL, "start", True)
c = [0]; print("alpha-beta perfect order:", generic_alphabeta(T3, UTIL, "start", True, c), "nodes", c[0])hold -> guarantees 9 cut_5 -> guarantees 11 cut_10 -> guarantees 7 minimax: 11 nodes 31 alpha-beta table order: 11 nodes 28 alpha-beta cut_5 first: 11 nodes 25 alpha-beta perfect order: 11 nodes 17
The recommendation is still cut by 5 % (it guarantees €11,000 over two weeks), but the order of the other two changes: hold (9) overtakes cut 10 % (7), which in the one-week game was the second option; with a longer horizon, the aggressive cut leaves no room for manoeuvre in the second week. As for pruning: the tree has 31 nodes; alpha-beta with the table order prunes 3 (in cut_10, once comp_matches is worth 11 ≤ α = 11 there is no need to look at comp_cuts15); trying the best known move first raises the saving to 6 nodes, and the perfect order almost halves it (17). It is the rule from 03-03: pruning is worth as much as the ordering is.
Feedback
- Typical mistake: using
>instead of>=in the pruning condition (prunes less than it should) or updating α at MIN nodes and β at MAX nodes (prunes too much and returns wrong values). Always check that alpha-beta returns the same value as minimax. order_childrencheats (it uses the result to sort); in a real engine the ordering is based on cheap heuristics or on earlier, shallower searches (iterative deepening).- Variants: add a fourth option "raise 5 %" at the root with leaves you make up and observe how much alpha-beta prunes depending on where you place it; turn the leaves into expected values by giving the competitor probabilities (0.5 / 0.3 / 0.2) instead of assuming it is perfect (expectimax) and compare the recommendation.
- Exercise 5: travelling salesman with time windows, hill climbing versus annealing
Reminder (03-04, sections 3-7). The travelling salesman is represented as a permutation of the deliveries; the objective function adds up the closed route using the matrix of minimum distances (MATRIX from exercise 2). Swap-based hill climbing gets stuck in local optima and is rescued with restarts; simulated annealing accepts worsening moves with probability e^(−Δ/T) and cools down gradually. With 7 deliveries, brute force (5,040 permutations) gives the exact optimum for validation.
Statement. The van leaves Getafe at 8:00 and averages 30 km/h (2 min/km). Two customers have priority delivery: Vallecas before 8:30 (minute 30) and Carabanchel before 8:50 (minute 50). Define the cost of a route as minutes of the closed route + 3 × total minutes of delay at the priority stops (arriving late costs three times as much as driving). (a) Compute the optimal route by brute force and compare it with the 39.0 km route from 03-04: how late is that route and what does it cost? (b) Solve with simple hill climbing, with 1/5/10/20 restarts and with simulated annealing; for each method, repeat with 20 seeds and record in how many it reaches the optimum and how many evaluations it uses. (c) If annealing falls behind hill climbing with restarts, try cooling more slowly.
Solution
MIN_PER_KM, WINDOWS, DELAY_WEIGHT = 2.0, {"Vallecas": 30, "Carabanchel": 50}, 3.0
DELIVERIES = [n for n in CITY_GRAPH if n != "Warehouse_Getafe"]
def evaluate_route(route, dist=MATRIX, origin="Warehouse_Getafe", detail=False):
clock = delay = 0.0; arrivals = {}; previous = origin
for stop in route:
clock += dist[previous][stop] * MIN_PER_KM; arrivals[stop] = clock
if stop in WINDOWS: delay += max(0.0, clock - WINDOWS[stop])
previous = stop
clock += dist[previous][origin] * MIN_PER_KM
cost = clock + DELAY_WEIGHT * delay
return (cost, clock, delay, arrivals) if detail else cost
def brute_force(deliveries):
return min(((evaluate_route(list(o)), list(o)) for o in itertools.permutations(deliveries)), key=lambda t: t[0])
def hill_climbing(route):
current, c_current, evals = route[:], evaluate_route(route), 1
while True:
best, c_best = None, c_current
for i in range(len(current)):
for j in range(i + 1, len(current)):
v = current[:]; v[i], v[j] = v[j], v[i]; c = evaluate_route(v); evals += 1
if c < c_best: best, c_best = v, c
if best is None: return current, c_current, evals
current, c_current = best, c_best
def hill_climbing_restarts(deliveries, n, seed=0):
rng, best, best_c, total = random.Random(seed), None, math.inf, 0
for _ in range(n):
init = deliveries[:]; rng.shuffle(init); r, c, ev = hill_climbing(init); total += ev
if c < best_c: best, best_c = r, c
return best, best_c, total
def simulated_annealing(route, T0=20.0, cooling=0.995, T_min=0.05, seed=0):
rng = random.Random(seed); current, c_current = route[:], evaluate_route(route)
best, best_c, T, evals = current[:], c_current, T0, 1
while T > T_min:
i, j = sorted(rng.sample(range(len(current)), 2))
neighbour = current[:]; neighbour[i:j + 1] = reversed(neighbour[i:j + 1]) # 2-opt
c_n = evaluate_route(neighbour); evals += 1; delta = c_n - c_current
if delta < 0 or rng.random() < math.exp(-delta / T):
current, c_current = neighbour, c_n
if c_current < best_c: best, best_c = current[:], c_current
T *= cooling
return best, best_c, evals
opt_c, opt = brute_force(DELIVERIES)
print("Optimum:", opt_c, opt, evaluate_route(opt, detail=True)[1:])
print("Route 39.0 km:", evaluate_route(["Leganes", "Carabanchel", "Arganzuela", "Retiro", "Vallecas", "Usera", "Villaverde"], detail=True))
rng = random.Random(7); init = DELIVERIES[:]; rng.shuffle(init)
print("Initial:", evaluate_route(init), "| simple hill climbing:", hill_climbing(init)[1:])
for n in (1, 5, 10, 20):
res = [hill_climbing_restarts(DELIVERIES, n, s) for s in range(20)]
print(f"hill climbing {n:2d} restarts: {sum(r[1] == opt_c for r in res)}/20 optima, ~{sum(r[2] for r in res)//20} evaluations")
for T0, cool in ((20, 0.995), (20, 0.998), (20, 0.999)):
res = [simulated_annealing(init, T0, cool, seed=s) for s in range(20)]
print(f"annealing T0={T0} cooling={cool}: {sum(r[1] == opt_c for r in res)}/20 optima, ~{sum(r[2] for r in res)//20} evaluations")Optimum: 99.0 ['Villaverde', 'Vallecas', 'Usera', 'Carabanchel', 'Arganzuela', 'Retiro', 'Leganes'] (99.0, 0.0, {'Villaverde': 10.0, 'Vallecas': 25.0, 'Usera': 36.0, 'Carabanchel': 45.0, 'Arganzuela': 55.0, 'Retiro': 63.0, 'Leganes': 90.0})
Route 39.0 km: (132.0, 78.0, 18.0, {'Leganes': 9.0, 'Carabanchel': 18.0, 'Arganzuela': 28.0, 'Retiro': 36.0, 'Vallecas': 48.0, ...})
Initial: 392.0 | simple hill climbing: (109.0, 106)
hill climbing 1 restarts: 3/20 optima, ~90 evaluations
hill climbing 5 restarts: 15/20 optima, ~449 evaluations
hill climbing 10 restarts: 20/20 optima, ~888 evaluations
hill climbing 20 restarts: 20/20 optima, ~1818 evaluations
annealing T0=20 cooling=0.995: 8/20 optima, ~1197 evaluations
annealing T0=20 cooling=0.998: 14/20 optima, ~2994 evaluations
annealing T0=20 cooling=0.999: 19/20 optima, ~5990 evaluationsThe windows change the route completely: the optimal one (99 min = 49.5 km) heads out to Villaverde and Vallecas (minute 25), continues via Usera to Carabanchel (45), and only then goes up to Arganzuela and Retiro to come back via Leganes; it meets both windows with zero delay and there are two tied routes (Arganzuela/Retiro in either order). The shortest route in km (78 min) reaches Vallecas at minute 48, 18 late: 78 + 3 × 18 = 132. Simple hill climbing from a random route (392) gets stuck at 109 (Vallecas–Carabanchel–Retiro…, a local optimum that already meets the windows but takes a detour); with 10 restarts it always gets there with fewer than 900 evaluations (against 5,040 for brute force). Annealing with the parameters from 03-04 only succeeds 8 times out of 20: the penalty creates a "rougher" landscape (one swap can add 3 × 20 minutes at a stroke) and you need to cool more slowly: with 0.999 it succeeds 19 out of 20, at the price of 6,000 evaluations. On this small problem, hill climbing with restarts is the most efficient method.
Feedback
- Typical mistake: counting the delay only at the last priority stop or not accumulating it; and computing the open route (forgetting the return to the warehouse), which changes the optimum.
- Another one: comparing methods with one seed. With a single run, annealing at 0.995 may succeed (seed 0 does) and look just as good; the 20-seed table is the only honest comparison, the same discipline as cross-validation in 04-05.
- Variants: also penalise arriving too early (the customer is not in); add a third window and observe when a route with no delay stops existing; use the 15-address instance from 03-04 (
generate_addresses(15)) with windows for two of them, where brute force is no longer viable and all that is left is to compare methods against each other.
- Exercise 6 (challenge): assignment with capacity and route cost using a genetic algorithm
Reminder (03-04, sections 8 and 9). In the order assignment, each solution is a list of labels (one warehouse per order), the capacity constraint becomes a penalty (€20 per excess box) and local search moves one order between warehouses at a time. A genetic algorithm keeps a population, selects by tournament, crosses over and mutates, and keeps the best through elitism. Validating on a small instance against brute force is mandatory.
Statement. Systems has added a transport cost per zone to the model: each (warehouse, zone) pair with at least one assigned order opens a route with a fixed cost, according to the table; per-box costs and capacities (Getafe 32, Zaragoza 30) are those from 03-04 (generate_orders(20, seed=11), 60 boxes). Represent each solution as a list of 20 bits (0 = Getafe, 1 = Zaragoza).
| Fixed route cost (€) | centre | south | northeast | east |
|---|---|---|---|---|
| Getafe | 20 | 20 | 60 | 55 |
| Zaragoza | 55 | 70 | 20 | 30 |
- Write
total_cost(genes, orders), which returns(penalised cost, shipping, routes, excess). - Validate the approach on a small instance: with orders P007-P014 (8 orders, 26 boxes) and capacities 14/14, enumerate the 2⁸ = 256 assignments and compare with the naive solution ("every order to its cheapest warehouse").
- Implement
genetic_algorithm(orders, size, generations, elitism, p_mut, k, seed)with one-point crossover and bit-by-bit mutation; check over 20 seeds how many times it reaches the optimum for the 8 orders. - Solve it for the 20 orders with the genetic algorithm (10 seeds), with hill climbing (20 restarts) and, since the 2²⁰ ≈ 1 million assignments can be enumerated in a few seconds, check the exact optimum. Interpret the solution in terms of open routes.
Solution
def generate_orders(n, seed=11): # the one from 03-04
rng = random.Random(seed)
rate = {"centre": (4, 7), "south": (3, 9), "northeast": (9, 4), "east": (8, 5)} # €/box (Getafe, Zaragoza)
orders = []
for i in range(1, n + 1):
zone = rng.choice(list(rate)); boxes = rng.choice([1, 1, 2, 3, 5])
orders.append({"id": f"P{i:03d}", "zone": zone, "boxes": boxes,
"getafe_cost": rate[zone][0] * boxes, "zaragoza_cost": rate[zone][1] * boxes})
return orders
ORDERS = generate_orders(20)
WAREHOUSES, CAPACITY, PENALTY = ["Getafe", "Zaragoza"], {"Getafe": 32, "Zaragoza": 30}, 20
ROUTE_COST = {("Getafe", "centre"): 20, ("Getafe", "south"): 20, ("Getafe", "northeast"): 60, ("Getafe", "east"): 55,
("Zaragoza", "centre"): 55, ("Zaragoza", "south"): 70, ("Zaragoza", "northeast"): 20, ("Zaragoza", "east"): 30}
def total_cost(genes, orders, capacity=None):
capacity = capacity or CAPACITY
shipping, load, routes = 0, [0, 0], set()
for g, o in zip(genes, orders):
shipping += o["getafe_cost"] if g == 0 else o["zaragoza_cost"]
load[g] += o["boxes"]; routes.add((WAREHOUSES[g], o["zone"]))
excess = max(0, load[0] - capacity["Getafe"]) + max(0, load[1] - capacity["Zaragoza"])
fixed = sum(ROUTE_COST[r] for r in routes)
return shipping + fixed + PENALTY * excess, shipping, fixed, excess
def brute_force(orders, capacity=None):
return min(((total_cost(g, orders, capacity)[0], list(g)) for g in itertools.product([0, 1], repeat=len(orders))))
def routes_of(genes, orders):
r = {}
for g, o in zip(genes, orders): r.setdefault((WAREHOUSES[g], o["zone"]), []).append(o["id"])
return r
def genetic_algorithm(orders, size=40, generations=60, elitism=2, p_mut=0.05, k=3, seed=0, capacity=None):
rng, n = random.Random(seed), len(orders)
fit = lambda ind: total_cost(ind, orders, capacity)[0] # lower cost = fitter
population = [[rng.randint(0, 1) for _ in range(n)] for _ in range(size)]
history = []
for _ in range(generations):
population.sort(key=fit); history.append(fit(population[0]))
new_pop = [ind[:] for ind in population[:elitism]] # elitism
while len(new_pop) < size:
p1, p2 = (min(rng.sample(population, k), key=fit) for _ in range(2)) # tournament
cut = rng.randint(1, n - 1)
child = p1[:cut] + p2[cut:] # one-point crossover
new_pop.append([1 - g if rng.random() < p_mut else g for g in child]) # bit-by-bit mutation
population = new_pop
best = min(population, key=fit)
return best, fit(best), history
def hill_climb(genes, orders):
current, f = genes[:], total_cost(genes, orders)[0]
while True:
neighbours = [current[:i] + [1 - current[i]] + current[i + 1:] for i in range(len(current))]
best = min(neighbours, key=lambda v: total_cost(v, orders)[0])
if total_cost(best, orders)[0] >= f: return current, f
current, f = best, total_cost(best, orders)[0]
# 2) small-scale validation
sub, cap8 = ORDERS[6:14], {"Getafe": 14, "Zaragoza": 14}
c8, opt8 = brute_force(sub, cap8)
naive8 = [0 if o["getafe_cost"] <= o["zaragoza_cost"] else 1 for o in sub]
print("8 orders | brute force:", c8, opt8, total_cost(opt8, sub, cap8), routes_of(opt8, sub))
print("8 orders | naive:", total_cost(naive8, sub, cap8))
print("GA on 8:", sum(genetic_algorithm(sub, 20, 30, seed=s, capacity=cap8)[1] == c8 for s in range(20)), "/20 seeds")
# 4) the 20 orders
g, c, h = genetic_algorithm(ORDERS, seed=0)
print("GA 20 seed 0:", c, total_cost(g, ORDERS), "| best in generation", h.index(min(h)))
print("history:", [(i, h[i]) for i in (0, 5, 10, 15, 20, 59)])
print("GA 10 seeds:", [genetic_algorithm(ORDERS, seed=s)[1] for s in range(10)])
print("GA pop. 80, 100 gen, mut 0.08:", [genetic_algorithm(ORDERS, 80, 100, p_mut=0.08, seed=s)[1] for s in range(10)])
rng = random.Random(0)
print("Hill climbing 20 restarts:", sorted(hill_climb([rng.randint(0, 1) for _ in range(20)], ORDERS)[1] for _ in range(20)))
c20, opt20 = brute_force(ORDERS)
print("Brute force 2^20:", c20, total_cost(opt20, ORDERS)); print(routes_of(opt20, ORDERS))8 orders | brute force: 251 [0, 1, 1, 0, 1, 0, 0, 0] (251, 126, 125, 0) {('Getafe', 'south'): ['P007', 'P010', 'P014'], ('Zaragoza', 'centre'): ['P008', 'P011'], ('Zaragoza', 'east'): ['P009'], ('Getafe', 'centre'): ['P012', 'P013']}
8 orders | naive: (346, 96, 70, 9)
GA on 8: 16 /20 seeds
GA 20 seed 0: 402 (402, 257, 145, 0) | best in generation 15
history: [(0, 517), (5, 496), (10, 435), (15, 402), (20, 402), (59, 402)]
GA 10 seeds: [402, 435, 402, 402, 402, 402, 402, 402, 402, 402]
GA pop. 80, 100 gen, mut 0.08: [402, 402, 402, 402, 402, 402, 402, 402, 402, 402]
Hill climbing 20 restarts: [402, 402, 402, 402, 402, 402, 402, 435, 435, 435, 435, 435, 493, 496, 506, 581, 590, 602, 608, 608]
Brute force 2^20: 402 (402, 257, 145, 0)
{('Zaragoza', 'east'): ['P001', 'P002', 'P004', 'P006', 'P009', 'P019'], ('Getafe', 'south'): ['P003', 'P005', 'P007', 'P010', 'P014', 'P017', 'P018'], ('Getafe', 'centre'): ['P008', 'P011', 'P012', 'P013'], ('Zaragoza', 'centre'): ['P015', 'P020'], ('Zaragoza', 'northeast'): ['P016']}On the small instance, the naive solution is infeasible (9 excess boxes, €346) and the optimum (€251) opens four routes, including an expensive Zaragoza–centre one (€55), because moving P008 and P011 (10 boxes from the centre) is the only way to respect 14 boxes at Getafe; the genetic algorithm with population 20 finds it in 16 out of 20 seeds (with 256 solutions, the initial population already covers 8 % of the space, so here it is a big hammer for a small nail: it serves to validate the implementation, not to show off). For the 20 orders, the exact optimum is €402 = €257 of shipping (the same feasible assignment as in 03-04) + €145 for the five routes; the fixed cost does not change the assignment because the tight capacity already forces Zaragoza–centre to open, but it does change the landscape: hill climbing only reaches the optimum in 7 of 20 restarts (closing or opening a route requires moving several orders at once, and the one-bit neighbourhood cannot see that), whereas the genetic algorithm reaches it in 9 of 10 seeds with the basic configuration and in 10 of 10 with more population and mutation, using some 2,400-8,000 evaluations against the million of brute force.
Feedback
- Typical mistake: mutating with probability
p_mutper individual (one bit) instead of per bit; both work, but they change the meaning of the parameter. Another one: forgetting elitism and watching the best cost go up from one generation to the next. - If the per-box penalty were lower than the cost of a route (for example, with capacities 36/36 the optimum prefers to pay for 2 excess boxes, €40, rather than open Zaragoza–centre for €55), the algorithm does what the objective function says, not what Diego wants: when the capacity is hard, raise the penalty until no infeasible solution pays off.
- Variants: replace one-point crossover with uniform crossover (each bit from parent 1 or 2 at random); add a third warehouse (representation with 0/1/2); measure, for 30 and 40 orders, the time of the genetic algorithm against brute force (2³⁰ is already intractable).
Common Mistakes and Tips
- Copying the code from 03-02/03-04 without rereading the details (goal test when popping from the heap, overwritable
parentsin Dijkstra,>=in the pruning): the subtle mistakes of module 3 resurface here. Keep the traces from those lessons at hand to compare. - Validating with a single run. For everything stochastic (restarts, annealing, genetic) compare over many seeds and against brute force on a reduced version; without that you do not know whether your implementation is correct or lucky.
- Mixing units in the objective function (km, minutes, euros): pick one unit, convert everything to it (here minutes in exercise 5, euros in exercise 6) and document the conversion factors (
MIN_PER_KM,DELAY_WEIGHT). - Badly calibrated penalties: too low and the algorithm "buys" the violation; too high and they flatten the real differences. Always check that the best solution found has excess 0 (or that the violation is deliberate).
- Not checking the heuristic: the edge-by-edge consistency test is cheap and should run every time the map data changes.
- Tip: save each exercise as a script with a
main()function and a check (assert cost == 402); these are the tests from 07-04 applied to algorithms.
Conclusion
You have gone back over module 3 without the lesson holding your hand: BFS and DFS with a closed road (Vallecas at 3 hops via Usera; three closures to isolate it), Dijkstra with the reconstruction of the 7 shortest paths and the discovery that Usera would be the best delivery point (a sum of 44 km versus 70.5), A* to Moratalaz with 4 expanded nodes versus 8, the check that a 3.0 km "shortcut" breaks admissibility and that an inflated heuristic loses the optimum (14.5 versus 14.0), two-week minimax (cutting 5 % still guarantees more, 31 nodes that pruning leaves at 28, 25 or 17 depending on the order), the travelling salesman with time windows (99 minutes versus the 132 of the shortest route in km, with hill climbing with restarts beating annealing unless it cools slowly) and the genetic algorithm for the assignment with route cost (€402, validated against 256 and against the million assignments). The common thread: represent well, define the objective function with its units and penalties, and validate against a known optimum or over many seeds.
The next exercises change tool but not discipline: in 09-02, Machine Learning Practices, you will work with the NovaMarket generators from module 4 (cleaning a dirty batch, a returns pipeline with a new feature, demand forecasting with TimeSeriesSplit, customer segmentation and threshold tuning with a fairness check), always with a baseline and an honest comparison.
Fundamentals of Artificial Intelligence (AI)
Module 1: Introduction to Artificial Intelligence
Module 2: Basic Principles of AI
- Fundamental Concepts: Agents, Environments and Rationality
- Types of Artificial Intelligence
- Data as the Raw Material of AI
- Ethics and Considerations in AI
Module 3: Algorithms in AI
- Introduction to Algorithms
- Search Algorithms
- Adversarial Search: Games and Minimax
- Optimization Algorithms
Module 4: Machine Learning
- Basic Concepts of Machine Learning
- Types of Machine Learning
- Data Preparation and Feature Engineering
- Machine Learning Algorithms
- Model Evaluation and Validation
- Overfitting, Regularization and Hyperparameter Tuning
Module 5: Neural Networks and Deep Learning
- Introduction to Neural Networks
- Neural Network Architecture
- How a Network Learns: Gradient Descent and Backpropagation
- Deep Learning and Its Applications
- Transformers, Large Language Models and Generative AI
Module 6: Logic and Expert Systems
- Logic in AI
- Expert Systems
- Reasoning under Uncertainty: Probability and Bayesian Networks
- Applications of Expert Systems
Module 7: Tools and Programming Languages in AI
- Programming Languages for AI
- Scientific Python: NumPy, pandas and Matplotlib
- Popular Tools and Libraries
- Development Environments
Module 8: Projects and Case Studies
Module 9: Exercises and Practice
- Algorithm Exercises
- Machine Learning Practice
- Neural Network Projects
- Capstone Project: from Idea to Prototype