关于「Held-Karp 动态规划:精确解、状态数与「高出下界」」,《买手扫货路线与时间窗》给出的定量结论是什么?
结论:Held-Karp 动态规划只记「去过哪些、停在哪里」,把穷举的阶乘降到 \(n2 2n\) 量级。示意首尔日的九站闭环,动态规划用 9216 次扩展、穷举用 181440 条闭环,得到同一个 23.2337 公里。十二站时它只有 24576 个状态,二十站时 10485760 个,二十五站时内存要 3355.4 兆字节;一天十五站以内,精确解随手可得。文献里的「高出约四分之一」量的是大规模下相对于 Held-Karp 下界的超出,六十站时程序复现了 0.2501;十二站时下界与最优几乎重合,最近邻只比最优高 0.1027。有了精确最短,下一个问题就来了:最短的那一圈,能不能在专柜开门的时刻里走完?
数据口径:书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。 第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
核心公式
查看完整验算程序
# 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:]))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》第 4 章「Held-Karp 动态规划:精确解、状态数与「高出下界」」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}