旅行商问题

旅行商问题（traveling salesperson problem，TSP）要求从一个地点出发，访问其余每个地点恰好一次，再返回起点，使总路程或费用最小。它同时决定访问顺序和闭合路线，不能用逐段选最近地点来保证全局最优。

设四座城市为 $0,1,2,3$，道路费用的单位为千元，矩阵为 $$C=\left(\begin{array}{cccc}0& 2& 9& 4\\ 2& 0& 3& 8\\ 9& 3& 0& 5\\ 4& 8& 5& 0\end{array}\right).$$ 这里费用对称，但并未假定满足三角不等式；例如从零经一到二的费用五，小于直接到二的九。矩阵表示城市间一次转移的费用，不要求把这组数据画成欧氏直线距离。

闭合路线与子回路

令 $x_{ij}\in \{0,1\}$ 表示是否从城市 $i$ 直接去 $j$。在有向完整图中，要求每点一个出边、一个入边，还不足以形成一次覆盖全体的旅行：两组互不相交的环也满足这些局部条件。还须排除真子集内部的闭环： $$\begin{array}{cc}min& \sum _{i\ne j}{c}_{ij}{x}_{ij},\\ \sum _{j\ne i}{x}_{ij}& =1,\sum _{j\ne i}{x}_{ji}=1,\\ \sum _{i,j\in S,i\ne j}{x}_{ij}& \le |S|-1\\ & (2\le |S|\le n-1).\end{array}$$ 入出度条件把选中边分解成若干不交环；任何非全体的环都会违反其顶点集对应的不等式。因此这些条件共同保证一条全体闭环。主例也可直接枚举六种访问顺序；把反向旅行合并后，三个不同环的费用为十四、二十四、二十四。

图的位置只用于看清连边，不按费用比例绘制；绿色边组成0至1至2至3至0，费用2+3+5+4=14。

按已访问集合递推

固定起点零。对非空集合 $S\subseteq \{1,\dots ,n-1\}$ 和 $j\in S$，定义 $D(S,j)$ 为从零出发、恰好访问集合 $S$、最后停在 $j$ 的最小费用。最后一步必从某个 $i\in S\setminus \{j\}$ 来，于是 $$\begin{array}{cc}D(\{j\},j)& =c_{0j},\\ D(S,j)& =\underset{i\in S\setminus \{j\}}{min}\{D(S\setminus \{j\},i)+c_{ij}\},\\ z_{\ast }& =\underset{j}{min}\{D(V\setminus \{0\},j)+c_{j0}\}.\end{array}$$ 删去一条最优路径的末边，余下路径必须在同一状态下最优，否则替换后就能改进原路径。反之，每个递推候选都可接成合法路径。按集合大小归纳，得到整张表的正确性；最后加返程边才是闭合旅行。

主例单点值为二、九、四。两点状态依次有 $D(\{1,2\},1)=12$、$D(\{1,2\},2)=5$，$D(\{1,3\},1)=12$、$D(\{1,3\},3)=10$，以及 $D(\{2,3\},2)=9$、$D(\{2,3\},3)=14$。三个全集合终点值为十二、十五、十，加返程后为十四、二十四、十四，前后两个十四是同一无向环的反向。

精确实现及规模

位掩码记录集合，表项记录最优值与前驱。输入为有限非负方阵，输出费用和闭合路线；一个城市约定为零费用。代码允许非对称费用，因而也能求解有向版本。

Python 3

import math

def held_karp(cost):
    c = tuple(tuple(row) for row in cost)
    n = len(c)
    if n == 0 or any(len(row) != n for row in c):
        raise ValueError("nonempty square matrix required")
    if any(not math.isfinite(x) or x < 0 for row in c for x in row):
        raise ValueError("finite nonnegative costs required")
    if n == 1:
        return 0, (0, 0)
    table = {}
    for j in range(1, n):
        table[(1 << (j - 1), j)] = (c[0][j], 0)
    full = (1 << (n - 1)) - 1
    for mask in range(1, full + 1):
        for j in range(1, n):
            bit = 1 << (j - 1)
            if not mask & bit or mask == bit:
                continue
            prev = mask ^ bit
            table[(mask, j)] = min(
                (table[(prev, i)][0] + c[i][j], i)
                for i in range(1, n) if prev & (1 << (i - 1)))
    value, j = min((table[(full, j)][0] + c[j][0], j)
                   for j in range(1, n))
    reverse, mask = [], full
    while mask:
        reverse.append(j)
        previous = table[(mask, j)][1]
        mask ^= 1 << (j - 1)
        j = previous
    return value, (0, *reversed(reverse), 0)

C = [[0,2,9,4], [2,0,3,8], [9,3,0,5], [4,8,5,0]]
print(held_karp(C))
# (14, (0, 3, 2, 1, 0))

不变量是每个已填状态都已考虑全部可能前驱；删去末位后掩码严格减小，故循环顺序满足依赖关系。状态数为 $O(n{2}^n)$，每个检查至多 $n$ 个前驱，时间为 $O(n^2{2}^n)$，含回溯指针的空间为 $O(n{2}^n)$。这比阶乘枚举省得多，仍会随城市数指数增长；启发式返回一条路线，也不自动证明它最优。

变式。 两座城市间来回费用分别为三、五，最优闭合费用为八；非对称矩阵不能只把某条去程费用乘二。若允许一个地点被多次访问，或要给多辆车分配任务，模型已分别涉及最短游走或车辆路径规划。

参考文献

• Michael Held、Richard M. Karp，A Dynamic Programming Approach to Sequencing Problems，IBM原作者书目；期刊版发表于1962年，DOI：10.1137/0110015。本文递推与算例独立展开。