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

Approximation & Heuristics

Approximation & Heuristics 32 minDouble the MST and shortcut repeats: a tour that's never more than twice the best possible, with a proof instead of a hope
You're building a piece ofMeridian — the bid desk
This piece — approximate_bid_route(): Builds a tour from the relay backbone's minimum spanning tree that is never more than twice the length of the best possible route.
Scenario Meridian's bid desk can't afford to brute-force the optimal route through every tender -- but it can afford to build the relay backbone's minimum spanning tree and walk it, and prove in advance that the result is never worse than double the best possible answer.
Your task
Build approximate_bid_route(cities, edges). edges is a complete, symmetric network [a, b, cost] obeying the triangle inequality (real point-to-point distances). Grow a minimum spanning tree with Prim's algorithm, walk it in preorder from cities[0] (visiting a node, then each child's whole subtree before moving to the next child), and use that order as the tour -- this shortcuts every repeat visit the doubled-MST walk would otherwise make. Return {"route": ..., "tour_cost": ..., "mst_weight": ..., "ratio": tour_cost / mst_weight rounded to 4 places}. Example: approximate_bid_route(["a","b","c"], [["a","b",2],["b","c",2],["a","c",3]]) -> tour_cost 7, mst_weight 4, ratio 1.75.

Approximation & Heuristics

In short: brute-force TSP doesn't scale, and no algorithm known today solves it exactly in polynomial time. But Meridian still has to ship a route. The fix is a proven approximation: grow a minimum spanning tree (section 17's relay backbone), walk it so that every edge is visited twice — once in, once out — then shortcut past any city you've already seen. The result is never more than twice the length of the best possible tour, and that's not a hope, it's provable, because the MST weight is itself a lower bound on any tour at all. A different heuristic, nearest-neighbour, has no such proof behind it — it's here for contrast, not as a replacement.

Three panels: an MST star, the same tree with every edge walked out-and-back shown as dashed loops, and the final shortcut tour drawn as a solid triangle, captioned "every edge walked twice costs 2x the MST weight, and skipping repeats never makes a metric tour longer"

Why the MST is a lower bound at all

Remove any one edge from the optimal tour and what's left is a path touching every city — which is itself a spanning tree, just not necessarily the cheapest one. So:

optimal tour cost ≥ (optimal tour minus one edge) ≥ MST weight

That one inequality is the entire foundation. Nothing about approximating TSP works without first having something to measure against, and the MST is cheap to compute exactly (section 17) even though the tour itself isn't.

watch it move · graph

The relay backbone's MST, weight 10. Walking every edge out and back would cost 20 — but the shortcut tour never needs to.

The MST here keeps central-north (3), central-harbor (4) and harbor-mill (3): weight 10. This is the lower bound every tour on these four depots has to beat. 4 nodes, 6 edges, undirected.

1 / 2

The shortcut, and why it's always safe

A preorder DFS of the MST visits every node exactly once and never needs to retrace a step it didn't already take to get there — it just skips the "come back here" trips the doubled walk would otherwise make:

python

The shortcut only works because of the triangle inequality: going directly from A to C is never longer than going A → B → C. Every real distance obeys this. Drop that assumption (make up an edge weight that breaks it) and the shortcut can get worse than the doubled walk, which is why this guarantee is stated for "metric TSP," not TSP in general.

What does this print?
def tour_cost(route, edges):
    dist = {}
    for a, b, cost in edges:
        dist[(a, b)] = cost
        dist[(b, a)] = cost
    return sum(dist[(route[i], route[(i + 1) % len(route)])] for i in range(len(route)))

edges = [["a", "b", 2], ["b", "c", 2], ["a", "c", 3]]
mst_weight = 4   # a-b and b-c, skipping the dearer a-c
print(tour_cost(["a", "b", "c"], edges) / mst_weight)

A heuristic with no proof behind it

Nearest-neighbour — always go to the closest unvisited city — is simpler to write and often does fine in practice, but it has no guaranteed ratio. An adversary can place the cities so that nearest-neighbour's early greedy choices strand it far from where it needs to end up:

broken — fix it

This currently returns ['a', 'a', 'b', 'c']. Remove the start city from `unvisited` before the loop begins.

Quick practice

What does this print?
mst_weight = 10
results = [(tc, round(tc / mst_weight, 2), tc / mst_weight <= 2.0) for tc in (14, 20, 21)]
print(results)
What does this print?
def ratio_ok(tour_cost, mst_weight):
    return tour_cost / mst_weight <= 2.0

print(ratio_ok(10, 5), ratio_ok(9, 5))

🎯 Your turn

Build approximate_bid_route(cities, edges). Grow a minimum spanning tree with Prim's algorithm, walk it in preorder from cities[0], and use that order as the tour. Return {"route": ..., "tour_cost": ..., "mst_weight": ..., "ratio": ...} with ratio rounded to 4 places.

  • approximate_bid_route(["a","b","c"], [["a","b",2],["b","c",2],["a","c",3]]) → tour_cost 7, mst_weight 4, ratio 1.75.

Hint: reuse Prim's from section 17 to grow the tree, then a recursive preorder walk (visit a node, then each unvisited neighbour's whole subtree) turns it into a tour with no edge ever doubled back on.

Press ▶ Run, try the Live App chips, then ✓ Check.

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-upJust the weight

Write mst_weight(cities, edges), returning the total weight of a minimum spanning tree built with Prim's algorithm. mst_weight(["a","b","c"], [["a","b",2],["b","c",2],["a","c",3]]) -> 4.

minimum-spanning-trees
DrillWalk a tree, one subtree at a time

Write preorder_walk(tree, start), where tree is an adjacency dict (each node maps to a list of its neighbours in the tree). Visit start, then recurse into each neighbour's whole unvisited subtree in sorted order before moving to the next. preorder_walk({"a":["b","c"],"b":["a"],"c":["a"]}, "a") -> ["a","b","c"].

intractability
BuildScore a finished tour

Write tour_length(route, edges), returning the total cost of travelling route in order and back to the start. tour_length(["a","b","c"], [["a","b",2],["b","c",2],["a","c",3]]) -> 7.

intractability
BossA different heuristic entirely

Write nearest_neighbour_route(cities, edges): starting at cities[0], repeatedly go to the closest city not yet visited, until every city has been visited. Return {"route": ..., "tour_cost": ...}. nearest_neighbour_route(["a","b","c"], [["a","b",2],["b","c",2],["a","c",3]]) -> route ["a","b","c"], cost 7.

intractability
CapstoneDoes the 2x bound actually hold?

Write measure_approx_ratio(seed, trials): using random.Random(seed), generate trials instances (4 to 8 cities, integer coordinates 0..20, Manhattan distance between every pair as edges). For each, compute the MST-shortcut tour's ratio to the MST weight. Return {"trials": ..., "max_ratio": ... (rounded to 4 places), "guarantee_held": max_ratio <= 2.0}.

intractabilityminimum-spanning-trees
approximate_bid_route.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
approximate_bid_route(cities, edges) → dictA tour built from the MST's preorder walk, its cost, the MST weight it's measured against, and the ratio between them.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.