Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Hard Problems & Adversarial Search  ›  Lesson

Capstone: Meridian's Bid Desk

55 minRun the heuristic router against a fixed seeded benchmark and report how it actually performs against the MST lower bound
You're building a piece ofMeridian — the bid desk
This piece — bid_desk_benchmark(): Runs the heuristic router against a fixed benchmark set and reports how close it stays to the MST lower bound.
Scenario Meridian's bid desk has to commit to a route-quoting method before the tender deadline, not after proving something new about TSP. Run the heuristic router against a fixed, reproducible benchmark set and report, honestly, how close it stays to the MST lower bound -- and how a method with no proof behind it can do worse.
Your task
Build bid_desk_benchmark(seed, trials). Using random.Random(seed), generate trials instances: 4 to 9 stops, integer coordinates 0..30, Manhattan distance between every pair as the edges. For each instance, compute the MST weight (the lower bound on any tour), the nearest-neighbour heuristic's tour cost, and the MST-shortcut approximation's tour cost. Return {"trials": ..., "nearest_neighbour_max_ratio": ..., "approximation_max_ratio": ..., "approximation_guarantee_held": approximation_max_ratio <= 2.0}, with ratios rounded to 4 places before taking the max. Example: bid_desk_benchmark(42, 30) -> trials 30, approximation_guarantee_held True.

Capstone: Meridian's Bid Desk

In short: this section built four separate pieces of hard-problem machinery — brute force vs. verification, a reduction between two NP-hard problems, a provably-bounded approximation, and a search over an opponent who's also optimising. The bid desk is where the approximation piece earns its keep for real: a fixed, seeded benchmark of tender instances, scored two ways — the no-guarantee nearest-neighbour heuristic, and the MST-shortcut approximation with its proven ratio of at most 2. Measured honestly, one of them can break its informal expectations. The other, provably, cannot.

Run the benchmark, read what actually happened

step through it
1import heapq
2import random
3 
4def manhattan_edges(points):
5 cities = list(points)
6 edges = []
7 for i in range(len(cities)):
8 for j in range(i + 1, len(cities)):
9 a, b = cities[i], cities[j]
10 (x1, y1), (x2, y2) = points[a], points[b]
11 edges.append([a, b, abs(x1 - x2) + abs(y1 - y2)])
12 return edges
13 
14def mst(cities, edges):
15 adj = {c: [] for c in cities}
16 for a, b, cost in edges:
17 adj[a].append((cost, b))
18 adj[b].append((cost, a))
19 start = cities[0]
20 visited = {start}
21 tree = {c: [] for c in cities}
22 weight = 0
23 heap = [(cost, b, start) for cost, b in adj[start]]
24 heapq.heapify(heap)
25 while heap and len(visited) < len(cities):
26 cost, node, parent = heapq.heappop(heap)
27 if node in visited:
28 continue
29 visited.add(node)
30 weight += cost
31 tree[parent].append(node)
32 tree[node].append(parent)
33 for c, nxt in adj[node]:
34 if nxt not in visited:
35 heapq.heappush(heap, (c, nxt, node))
36 return tree, weight
37 
38rng = random.Random(7)
39worst_ratio = 0.0
40for _ in range(15):
41 n = rng.randint(4, 9)
42 points = {f"c{i}": (rng.randint(0, 30), rng.randint(0, 30)) for i in range(n)}
43 cities = list(points)
44 edges = manhattan_edges(points)
45 tree, weight = mst(cities, edges)
46 if not weight:
47 continue
48 # preorder walk, shortcutting repeats
49 order, seen = [], set()
50 def dfs(node):
51 seen.add(node)
52 order.append(node)
53 for nxt in sorted(tree[node]):
54 if nxt not in seen:
55 dfs(nxt)
56 dfs(cities[0])
57 dist = {}
58 for a, b, cost in edges:
59 dist[(a, b)] = cost
60 dist[(b, a)] = cost
61 cost = sum(dist[(order[i], order[(i + 1) % len(order)])] for i in range(len(order)))
62 worst_ratio = max(worst_ratio, cost / weight)
63print(round(worst_ratio, 4))

At seed=7, fifteen trials, the MST approximation's worst ratio lands at 1.9535 — under the 2x ceiling, as the proof in lesson 3 said it must. Run bid_desk_benchmark(7, 15) in full and the nearest-neighbour column tells a different story: 2.0465, past 2x. Nothing about nearest-neighbour is broken — it's a perfectly reasonable heuristic most of the time — but nothing was ever proven about it either, and this benchmark is where that absence shows up as a real number, not a footnote.

Why the same instances treat the two heuristics differently

Nearest-neighbour makes a locally greedy choice at every step and never revisits it. On most seeded point sets that works out fine. But a handful of points can be arranged — not maliciously, just by chance, as a seeded random.Random instance sometimes will — so that an early "closest" choice strands the walk far from where it still needs to go, with no mechanism to notice or correct it. The MST-shortcut approximation has no such blind spot because its guarantee doesn't come from being locally sensible — it comes from the inequality shortcut tour ≤ 2 × MST weight, which holds structurally, for every instance, not just typical ones.

What does this print?
nn_ratio, approx_ratio = 2.0465, 1.9535
print(nn_ratio <= 2.0, approx_ratio <= 2.0)

Quick practice

What does this print?
def guarantee_held(ratios):
    return max(ratios) <= 2.0

print(guarantee_held([1.2, 1.5, 2.0]), guarantee_held([1.2, 1.5, 2.01]))
What does this print?
trials_run = 30
instances_skipped = 0  # none have MST weight 0 here
print(trials_run - instances_skipped)

🎯 Your turn

Build bid_desk_benchmark(seed, trials). Generate trials seeded instances with random.Random(seed) (4 to 9 stops, coordinates 0..30, Manhattan distance between every pair). For each, compare the nearest-neighbour heuristic and the MST-shortcut approximation against the MST weight. Return {"trials": ..., "nearest_neighbour_max_ratio": ..., "approximation_max_ratio": ..., "approximation_guarantee_held": ...}.

  • bid_desk_benchmark(42, 30) → approximation_guarantee_held True.
  • bid_desk_benchmark(7, 15) → nearest-neighbour's ratio breaks past 2.0; the approximation's doesn't.

Hint: reuse the MST, preorder-walk and nearest-neighbour pieces from lesson 3 — this lesson's job is running them at scale and reporting honestly, not inventing new algorithms.

Press ▶ Run, try the Live App chips, then ✓ Check. Green = this piece of Meridian is built. ✅

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upOne ratio

Write tour_ratio(tour_cost, lower_bound), returning tour_cost / lower_bound rounded to 4 places. tour_ratio(18, 14) -> 1.2857.

intractability
DrillPick the cheaper of two routes

Write best_of_two_routes(route_a, cost_a, route_b, cost_b), returning {"route": ..., "cost": ...} for whichever of the two is cheaper (ties go to route_a). best_of_two_routes(['a','b'], 10, ['a','c'], 8) -> {"route": ['a','c'], "cost": 8}.

intractability
BuildSummarise a list of ratios

Write summarize_ratios(ratios), returning {"min": ..., "max": ..., "avg": ...}, each rounded to 4 places. summarize_ratios([1.2, 1.8, 1.5]) -> {"min": 1.2, "max": 1.8, "avg": 1.5}.

intractability
BossJust the approximation, benchmarked

Write benchmark_approx_only(seed, trials): same seeded instance generation as the main task (4 to 9 stops, coordinates 0..30, Manhattan distance), but only measure the MST-shortcut approximation's ratio. Return {"trials": ..., "max_ratio": ...}.

intractabilityminimum-spanning-trees
CapstoneThe whole bid desk, in one call

Write bid_desk_full_report(seed, trials), returning everything bid_desk_benchmark returns, plus the seed itself under the key "seed". bid_desk_full_report(42, 30) -> the same dict as bid_desk_benchmark(42, 30), with "seed": 42 added.

intractabilityadversarial-search
bid_desk_benchmark.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
bid_desk_benchmark(seed, trials) → dictHow the nearest-neighbour heuristic and the proven MST approximation each performed against the MST lower bound, across a fixed seeded benchmark set.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.