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

Hard to Find, Easy to Check

P, NP & Verification 30 minFinding the cheapest tour needs every permutation; checking one finished tour needs none of that
You're building a piece ofMeridian — the bid desk
This piece — bid_desk_tsp(): Finds the cheapest route through every stop on a tender by brute force, and shows why checking a submitted route is nothing like as expensive.
Scenario A tender lands on Meridian's bid desk with a dozen stops that have to be served on one route. Finding the cheapest route means trying orderings; checking whether a route a bidder has already proposed is any good means nothing of the sort.
Your task
Build bid_desk_tsp(cities, edges). cities is a list of stop names; edges is a list of [a, b, cost] covering every pair (a complete, symmetric network). Fix cities[0] as the start and try every ordering of the rest with itertools.permutations, keeping the cheapest full loop back to the start. Return {"route": ..., "cost": ..., "permutations_tried": ...}. A single city needs no permutations: return {"route": cities, "cost": 0, "permutations_tried": 1}. Example: bid_desk_tsp(["a", "b", "c"], [["a","b",1],["b","c",1],["a","c",5]]) -> cost 7, 2 permutations tried.

Hard to Find, Easy to Check

In short: every algorithm this course has taught so far runs in time that is a polynomial in its input size — that's the class P. Finding the cheapest tour through a handful of stops isn't known to have any such algorithm: the best general method is still brute force over every ordering, and the number of orderings explodes factorially. But checking a tour someone else hands you — does it visit every stop once, does it cost what they claim — takes barely any work at all. That gap, between finding a solution and checking one, is what the class NP names, and it's not a philosophical point: you can measure it on your own laptop.

Two groups of bars at n=4, n=8 and n=12: permutations_tried in red climbs to 39,916,800 at n=12, while verify_checks in green barely rises off the baseline to 13

Count what brute force actually tries

Meridian's bid desk gets a tender with a handful of stops and needs the cheapest loop that visits every one of them and returns to the start. There's no shortcut known: try every ordering, score each one, keep the best.

step through it
1import itertools
2 
3def bid_desk_tsp(cities, edges):
4 dist = {}
5 for a, b, cost in edges:
6 dist[(a, b)] = cost
7 dist[(b, a)] = cost
8 start, rest = cities[0], cities[1:]
9 best_cost, tried = None, 0
10 for perm in itertools.permutations(rest):
11 route = [start] + list(perm)
12 cost = sum(dist[(route[i], route[i + 1])] for i in range(len(route) - 1))
13 cost += dist[(route[-1], start)]
14 tried += 1
15 if best_cost is None or cost < best_cost:
16 best_cost = cost
17 return best_cost, tried
18 
19cities = ["central", "harbor", "mill", "north"]
20edges = [["central", "harbor", 4], ["central", "mill", 7], ["central", "north", 9],
21 ["harbor", "mill", 2], ["harbor", "north", 6], ["mill", "north", 3]]
22print(bid_desk_tsp(cities, edges))

Four stops means 3! = 6 orderings — nothing. The start city never moves, so what grows is (n - 1)!, the orderings of everyone else. This is never about how fast your machine is: doubling the clock speed buys you maybe one more stop before the wait becomes a problem again, because the count itself is growing factorially, not the time per step.

What does this print?
import math

def permutations_to_try(n):
    return math.factorial(n - 1) if n >= 1 else 1

print([permutations_to_try(n) for n in (4, 8, 12)])

Checking a tour is a different kind of work entirely

Say a bidder hands Meridian a proposed route and claims it costs ₹18,000. Checking that claim doesn't need any ordering to be tried — just a single walk through the route they already gave you:

python

verify_tour is a sort and a comparison: O(n log n). route_cost is one pass: O(n). Neither one searches anything — there is nothing to search, because the route to check is already in your hand. That asymmetry, not wall clock seconds (your laptop's clock speed changes; the number of checks for a given n does not), is what separates P (verify_tour, route_cost — solvable and checkable fast) from the harder class a brute-force tour search sits in.

broken — fix it

This prints (True, 3), missing the length check. Make it print (True, 4).

Quick practice

What does this print?
import math
print(math.factorial(5), math.factorial(5 - 1))
What does this print?
def verify_checks(n):
    return n + 1

print(verify_checks(12), verify_checks(1000))

🎯 Your turn

Build bid_desk_tsp(cities, edges). cities is a list of stop names; edges is [a, b, cost] covering every pair. Fix cities[0] as the start, try every ordering of the rest, and return the cheapest loop as {"route": ..., "cost": ..., "permutations_tried": ...}. A single city needs no permutations at all: {"route": cities, "cost": 0, "permutations_tried": 1}.

  • bid_desk_tsp(["a", "b", "c"], [["a","b",1],["b","c",1],["a","c",5]]) → cost 7, 2 permutations tried.

Hint: itertools.permutations(cities[1:]) gives every ordering of everyone except the start; score each one and keep the cheapest.

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-upHow many tours are there to try?

Write permutations_to_try(n), returning how many orderings brute-force TSP has to try for n cities once the start city is fixed: (n - 1)!, or 1 when n <= 1. permutations_to_try(4) -> 6.

intractabilitycomplexity
DrillScore one finished route

Write route_cost(route, edges), returning the total cost of travelling the route in order and back to the start. edges is [a, b, cost] triples covering every pair. route_cost(["a","b","c"], [["a","b",1],["b","c",1],["a","c",5]]) -> 7.

intractability
BuildIs this a valid tour at all?

Write verify_tour(cities, route), returning True if route visits every city in cities exactly once (any order), and False otherwise. verify_tour(["a","b","c"], ["b","a","c"]) -> True. verify_tour(["a","b","c"], ["a","a","c"]) -> False.

intractabilitycomplexity
BossCount what verifying actually costs

Write verify_with_checks(cities, route), returning [is_valid, checks] where checks counts one check for the length comparison plus one more for every city in route as it's confirmed present and removed from the pool of names still owed. Stop and return False as soon as a check fails. verify_with_checks(["a","b","c"], ["b","a","c"]) -> [True, 4].

intractability
CapstoneThe gap, in two numbers

Write tsp_vs_verify(n), returning {"permutations_tried": ..., "verify_checks": ...} for n cities: the (n - 1)! brute force would try, next to the n + 1 checks verifying one finished tour would take. tsp_vs_verify(4) -> {"permutations_tried": 6, "verify_checks": 5}.

intractabilitycomplexity
bid_desk_tsp.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
bid_desk_tsp(cities, edges) → dictThe cheapest full loop through every city, how much it costs, and how many permutations brute force had to try.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.