What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “Held-Karp Dynamic Programming: Exact Solutions, State Counts and "Above the Bound"”?
Answer: Held-Karp dynamic programming remembers only "where I have been and where I stand", reducing the factorial of brute force to the order of \(n2 2n\). For the nine-stop loop of the illustrative Seoul day, the dynamic programme uses 9216 extensions and brute force 181440 loops, and both arrive at 23.2337 km. At twelve stops it has only 24576 states, at twenty 10485760, and at twenty-five it needs 3355.4 megabytes; for a day of up to fifteen stops the exact solution is at hand. The literature's "about a quarter above" measures the large-scale excess over the Held-Karp bound, and the program reproduces 0.2501 at sixty stops; at twelve stops bound and optimum nearly coincide and nearest neighbour is only 0.1027 above the optimum. With the exact shortest loop in hand, the next question follows: can that shortest loop be walked within the hours when the counters are open?
Scope of the numbers: Chapter 7 examines Shen Kuo's account of Ding Wei's "one move, three jobs" (an illustrative account saves 0.826) and Euler's seven bridges. Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 181440, 23.2337, 9216
| counters | 9 (Seoul, illustrative km) |
| Held-Karp | 2304 states, 9216 transitions |
| brute force | 181440 loops checked |
| Held-Karp best | 23.2337 km SGHABCDEFI |
| brute force best 23.2337 km SGHABCDEFI | |
| lengths agree: True; work ratio brute/HK | 19.7 |
| dp[full][j] + return leg, by last counter j: | |
| A 24.64, B 24.07, C 24.65, D 25.08, E 23.92 | |
| F 23.41, G 23.23, H 24.35, I 23.23 |
Key formula
Show the full program
# Chapter 4. p41: Held-Karp dynamic programming against brute force.
# Model: a Seoul day of nine counters A to I and hotel S, illustrative
# coordinates (km, not real addresses). Held-Karp (1962) and Bellman
# (1962): f(S, j) = min over i in S - {j} of f(S - {j}, i) + d(i, j),
# the shortest path from the hotel through set S ending at j. Brute
# force lists every loop with the first counter index below the last.
import itertools
import math
NAMES = ["S"] + list("ABCDEFGHI")
# 首尔示意街区(公里,示意,非真实地址)
PTS = [(0.0, 0.0), (-2.8, 1.9), (-1.2, 3.1), (0.9, 2.4), (2.6, 3.3),
(3.4, 0.8), (2.1, -1.6), (-0.3, -2.7), (-2.5, -1.4), (0.8, 0.3)]
D = [[math.hypot(a[0] - b[0], a[1] - b[1]) for b in PTS] for a in PTS]
N = len(PTS) - 1
full, inf = (1 << N) - 1, float("inf")
dp = [[inf] * N for _ in range(full + 1)]
par = [[-1] * N for _ in range(full + 1)]
states = transitions = 0
for j in range(N):
dp[1 << j][j] = D[0][j + 1]
for m in range(1, full + 1):
for j in range(N):
v = dp[m][j]
if v == inf or not (m >> j) & 1:
continue
states += 1
for k in range(N):
if (m >> k) & 1:
continue
transitions += 1
if v + D[j + 1][k + 1] < dp[m | 1 << k][k]:
dp[m | 1 << k][k] = v + D[j + 1][k + 1]
par[m | 1 << k][k] = j
best, j = min((dp[full][j] + D[j + 1][0], j) for j in range(N))
t, m = [], full
while j != -1:
t.append(j + 1)
m, j = m ^ (1 << j), par[m][j]
hk = [0] + t[::-1]
checked, bf_best, bf_tour = 0, inf, None
for perm in itertools.permutations(range(1, N + 1)):
if perm[0] > perm[-1]:
continue
checked += 1
loop = (0,) + perm
v = math.fsum(D[loop[i - 1]][loop[i]] for i in range(len(loop)))
if v < bf_best - 1e-12:
bf_best, bf_tour = v, loop
print("counters: %d (Seoul, illustrative km)" % N)
print("Held-Karp: %d states, %d transitions" % (states, transitions))
print("brute force: %d loops checked" % checked)
print("Held-Karp best %.4f km %s" % (best, "".join(NAMES[i] for i in hk)))
print("brute force best %.4f km %s" % (bf_best, "".join(
NAMES[i] for i in bf_tour)))
same = abs(best - bf_best) < 1e-9
print("lengths agree: %s; work ratio brute/HK = %.1f" % (
same, checked / transitions))
print("dp[full][j] + return leg, by last counter j:")
row = ["%s %.2f" % (NAMES[j + 1], dp[full][j] + D[j + 1][0])
for j in range(N)]
print(" " + ", ".join(row[:5]))
print(" " + ", ".join(row[5:]))Single source and citation
Fan, Y. (2026). Two-Opt Travelling-Salesman Search and Vehicle Routing with Time Windows: Shortest Shopping Loops in Tokyo, Osaka and Seoul under Counter Opening Hours (Version 1.0.0), Chapter 4: Held-Karp Dynamic Programming: Exact Solutions, State Counts and "Above the Bound". 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-298 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026298,
author = {Fan, Yafu},
title = {Two-Opt Travelling-Salesman Search and Vehicle Routing with Time Windows: Shortest Shopping Loops in Tokyo, Osaka and Seoul under Counter Opening Hours},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Price of Nearest First: How Much Longer than the Shortest Loop
- Chapter 2 · Croes's Pairwise Exchange: Reversing a Stretch, Crossings and Local Optima
- Chapter 3 · Segment Moves and One-Way Streets: the Or-opt Neighbourhood and Asymmetric Travel
- Chapter 5 · The Counters' Clocks: Time-Window Feasibility and the Day with the Most Items
- Chapter 6 · Two Buyers and Random Queues: Vehicle Routing with Time Windows and Planning Slack
- Chapter 7 · Classical Sources East and West: Ding Wei's "One Move, Three Jobs" and Euler's Seven Bridges
- Chapter 8 · Closing the Loop: the Shopping Route Planner and a Pre-Registered Test Plan