Held and Karp index a table by a subset of the cities and the city currently ended at, which turns a factorial search into an exponential one. On four cities that is 256 units of work against 6, so the table loses by a factor of more than forty on the instance in front of you. It does not overtake trying every tour until ten cities, and both numbers are printed as exact integers because the whole point is how they pull apart.
Core ideas
The hard idea is the state: a subset is an index, and accepting that is what turns an ordering problem into a table problem.
The table has one entry per pair: a set of cities already visited, and which of them the route currently ends at. The entry is the length of the shortest route from the start that visits exactly that set and finishes there. Nothing about a table requires its index to be a number, and once the index may be a set the problem has n2ⁿ states rather than (n−1)! orderings.
Two routes visiting the same cities and ending at the same city are interchangeable for everything that follows, so only the shorter needs keeping. That is optimal substructure stated for this problem, and it is what collapses the factorial: the (k−1)! orders of a k-subset ending at a given city become one entry.
n²2ⁿ against (n−1)! is 256 against 6 at four cities, 2 304 against 120 at six, and 41 472 against 40 320 at nine, where the table is still behind. It first wins at ten, 102 400 against 362 880. The better asymptotic method is the worse method on every instance this lab will run.
The material
The problem, the recurrence over subsets, what the tour that comes back actually is, and the two exact counts that pull apart.
Given n cities and a distance from each to each, find a cyclic route that starts at city 1, visits every city exactly once, and returns to city 1, of least total length. The distances need not be symmetric and nothing here assumes the triangle inequality — the lab ships a matrix violating both.
For a subset S of the cities containing city 1 and a city j in S other than 1, let D(S, j) be the length of the shortest path that starts at city 1, visits exactly the cities of S, and ends at j. Then D({1, j}, j) = d(1, j), and for larger S, D(S, j) is the minimum over cities i in S other than 1 and j of D(S − {j}, i) + d(i, j). The tour's length is the minimum over j of D(all, j) + d(j, 1).
A shortest path from city 1 covering S and ending at j arrives at j from some city i in S. Deleting the final leg leaves a path from 1 covering S − {j} and ending at i, and that path must be a shortest such path: a shorter one could be extended by the same final leg to beat the original. So the length is D(S − {j}, i) + d(i, j) for that i, and minimising over i gives the recurrence.
The substitution is legal because the final leg's cost depends only on i and j and not on how S − {j} was traversed, which is exactly the property that makes the order inside a subset irrelevant. Closing the cycle at the end adds the return leg, and taking the minimum over the last city gives the tour.
□
The fill order follows from the recurrence as usual: D(S, j) reads entries for S − {j}, which is a strictly smaller set, so filling by increasing subset size — or, equivalently here, by increasing numeric value of the subset's bit pattern — has every read written. On the lab's four-city instance the fill makes 12 reads.
The tour is returned as an open list of n cities beginning at city 1. The leg home is counted in the reported length and is not in the list. On the lab's default matrix the tour is 1, 3, 4, 2 and the length is 21; adding up the three legs written down gives 20, and the missing 1 is the return from city 2 to city 1. Re-measuring the list as written is the way to convince yourself there is an off-by-one in the table, and there is not.
So the check closes the cycle. The panel confirms that the list is a permutation of the cities starting at city 1 and re-adds the n legs — the n − 1 written plus the return — from the distance matrix. Both of those are separate from the table, and both are printed.
The matrix is asymmetric: the distance from city 1 to city 2 is 2 and from 2 to 1 is 1. The six tours are 1-2-3-4-1 at 22, 1-2-4-3-1 at 33, 1-3-2-4-1 at 26, 1-3-4-2-1 at 21, 1-4-2-3-1 at 34 and 1-4-3-2-1 at 30. Held-Karp returns 21 and the tour 1, 3, 4, 2, and the enumeration agrees on both.
Held-Karp fills one entry per (subset, end city) pair, which is n2ⁿ entries, and each entry minimises over up to n predecessors, so the work is n²2ⁿ. Trying every ordering is (n−1)! tours. At four cities those are 256 and 6. At five, 800 and 24. At six, 2 304 and 120. At nine, 41 472 and 40 320 — still behind. At ten, 102 400 and 362 880, and from there the gap widens for ever.
This is the Subject's warning in its sharpest available form, and it is worth being precise about what each number is. The two figures on the panel are exact integers evaluated from n, not measurements of a running time and not estimates: n²2ⁿ and (n−1)! are the two bounds, printed at the n on screen. They are the proved statements, and they are what says the table wins eventually. What the lab measures is separate: 12 reads for the fill and 6 tours for the enumeration on this instance, and by that measurement too the table is the slower method here.
So a reader who chose Held-Karp for a four-city problem chose the asymptotically better algorithm and did more work, and would keep doing more work up to nine cities. Nothing is wrong with the analysis. What is wrong is treating an asymptotic comparison as advice about an instance, and this page is on the course because that mistake is invisible when both methods finish instantly.
Intractability and Approximation takes this further: O(n²2ⁿ) is still exponential and this problem is NP-hard, so the table is a better exponential rather than a way out of one. The six honest responses to a problem with no fast algorithm are that course's subject, and an exact algorithm that is merely less bad is the first of them.
Interactive
Held-Karp against every ordering, with both costs as exact integers
Method
The technique is mechanical. The decision about whether it helps at your size is not.
For a tour: which cities are used and where you are. Not the order they were used in, because nothing in the future depends on it. That observation is the whole algorithm, and it is the same optimal-substructure argument as every other page here.
A subset is a legitimate index. Entries for a set read entries for strictly smaller sets, so increasing size is a valid order and can be checked the same way every other order on this course is checked.
The list that comes back is open: n cities, starting at the start, with the leg home counted in the length and absent from the list. Re-measuring the list as written gives a tour one leg short, which looks exactly like an off-by-one in the table.
n²2ⁿ and (n−1)! are two integers you can evaluate in a second. Below ten cities the factorial one is smaller, and the simpler algorithm is also the faster one. Above it, the table pulls away without bound.
Six tours at four cities, 120 at six, 5 040 at eight. Use the enumeration to establish the table, note the size at which you had to stop, and do not extend the claim past it without an argument.
The distance matrix is asymmetric: row i column j is the distance from city i to city j, and it need not equal row j column i. The diagonal is zero.
The asymmetry is doing real work in this instance. The tour 1-3-4-2-1 uses the leg from city 2 back to city 1, which costs 1, where the leg from 1 to 2 costs 2. Its reverse, 1-2-4-3-1, costs 33. On a symmetric matrix a tour and its reverse cost the same and half the enumeration is redundant; here it is not, and nothing in the recurrence assumed it was.
The list 1, 3, 4, 2 has four entries for four cities and the length is twenty-one. Those two facts are consistent only once you know the convention: the leg home is counted and not listed. A reader who adds up the list as written gets 20, concludes the table is off by one, and goes looking for a bug in the recurrence. There is no bug; there is a convention, and the check on the panel closes the cycle for exactly this reason.
For a faded rehearsal, switch to the matrix that violates the triangle inequality before running it. The supplied first move: going straight from city 1 to city 4 costs fifty, and going round by 2 and 3 costs three, so no shortcut argument applies and the exact answer is the only answer available. Predict the optimal tour's length, then check — and note that the work figures are unchanged, because they depend on the number of cities and not on what is in the matrix.
You should be able to state what a partial tour has to remember, write the recurrence over subsets, close the cycle before measuring a returned tour, and evaluate both work expressions at a given number of cities rather than quoting their order of growth.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.