关于「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 件。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 181440, 23.2337, 9216

counters9 (Seoul, illustrative km)
Held-Karp2304 states, 9216 transitions
brute force181440 loops checked
Held-Karp best23.2337 km SGHABCDEFI
brute force best 23.2337 km SGHABCDEFI
lengths agree: True; work ratio brute/HK19.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

核心公式

\[f(S, j) = \min_{i \in S \setminus \{j\}} \big( f(S \setminus \{j\}, i) + d_{ij} \big),\]
查看完整验算程序
# 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}
}

本书其他章节结论