TSP求解器在线

伪代码

旅行商问题没有快速的精确算法，因此务实的做法分两个阶段：先快速构造一条尚可的回路，再做局部改进直到无法继续为止。

// 阶段一：最近邻，以 O(n^2) 构造一条回路
回路 = [起点]
当仍有城市未访问时:
    下一个 = 距回路末端最近的未访问城市
    回路.追加(下一个)
回路.追加(起点)              // 闭合回路

// 阶段二：2-opt，消除交叉直到无改进
重复直到没有改进:
    对回路中每一对边 (a,b) 与 (c,d):
        若 dist(a,c) + dist(b,d) < dist(a,b) + dist(c,d):
            反转 b 与 c 之间的回路片段

// 精确解，n 较小时：Held-Karp 动态规划
dp[S][j] = 对 S\{j} 中的 k 取 dp[S\{j}][k] + dist(k, j) 的最小值

2-opt 这一步值得从几何角度理解。若回路中两条边相交，交换它们的端点并反转中间片段，依据三角不等式必然缩短回路。因此 2-opt 字面意义上就是把一根绳圈上的结解开。

分步示例演算

对矩形四角上的四座城市先跑最近邻再跑 2-opt，这里贪心选择可能明显出错。

示例图: 城市 A(0,0)、B(0,3)、C(4,3)、D(4,0)。距离：A-B 3、B-C 4、C-D 3、A-D 4，两条对角线 A-C 与 B-D 均为 5。

1. 从 A 开始最近邻. 距 A 最近的城市是 B，距离 3。前往 B。
2. 从 B 出发. 未访问的还有距离 4 的 C 与距离 5 的 D。选 C。
3. 从 C 出发. 只剩 D，距离 3。选它，再以代价 4 闭合回到 A。
4. 贪心结果. 回路 A 到 B 到 C 到 D 到 A 代价为 3 + 4 + 3 + 4 = 14。这里它恰好就是最优解，因此我们扰动一下：假设启发式给出的是 A 到 C 到 B 到 D 到 A，代价 5 + 4 + 5 + 4 = 18，这条回路的边彼此交叉。
5. 2-opt 修复. 考察边 A-C 与 B-D。它们当前贡献 5 + 5 = 10。改接成 A-B 与 C-D 后为 3 + 3 = 6，改进了 4，于是反转 C 与 B 之间的片段。回路变为 A 到 B 到 C 到 D 到 A，代价 14，此后再无任何 2-opt 移动能带来改进。

最优回路是代价 14 的矩形周长，而不是代价 18 的任何一条含交叉对角线的回路。这就是 TSP 启发式算法的缩影：一次快速的构造性扫描已经很接近，局部搜索再把贪心选择引入的交叉消除掉。

复杂度及其来源

时间: 启发式 O(n^2)，精确 O(n^2 · 2^n) · 空间: 启发式 O(n^2)，精确 O(n · 2^n)

最近邻在 n 个步骤中每一步都扫描全部剩余城市，因此为 O(n 的平方)。每一轮 2-opt 检验全部 O(n 的平方) 对边并反复进行直到无改进，实践中很快，但最坏情况没有有用的上界。Held-Karp 是精确算法，其表以子集与端点为索引：共有 2 的 n 次方个子集乘以 n 个端点，每个表项花费 O(n)，因此时间为 O(n 的平方乘以 2 的 n 次方)，内存为 O(n 乘以 2 的 n 次方)。这在 n = 20 到 25 附近就是一堵硬墙，因为 2 的 25 次方乘以 25 已超过十亿个表项。对全部排列做暴力枚举更糟，为 O(n 的阶乘)。

何时使用旅行商问题，何时不宜

选用哪种方法几乎完全取决于城市数量，以及你是否需要可证明的最优解。

常见陷阱

• 在大规模上期待精确答案. TSP 是 NP 困难的。目前没有任何算法能在合理时间内精确求解 1000 座城市，找到一个就等于解决了 P 与 NP 之争。若某个工具声称能在大规模实例上迅速给出精确最优解，它返回的其实是启发式回路。
• 只依赖最近邻. 贪心构造通常比最优解差约 25%，在最坏情况下可以差到任意程度，因为最后剩下的几座城市会迫使出现很长的边。请务必在其后接一轮局部搜索。
• 把 Christofides 用于非度量距离. 它 1.5 倍的近似保证依赖于三角不等式。存在单行道、非对称代价或禁行路线时，这个上界根本不成立。
• 把 TSP 与车辆路径问题混为一谈. TSP 只有一台车辆，没有载重限制也没有时间窗。一旦引入车队或载重上限，就需要 VRP 或 CVRP 的方法；把一条 TSP 回路切成几段并不是合法的 VRP 解。
• 忽视起点城市无关紧要这一点. TSP 回路是一个环，旋转它不改变任何东西。把起点当作有意义的实现既浪费计算，也可能对完全相同的回路报出不同的代价。

常见问题

什么是旅行商问题？

给定一组城市以及每一对城市之间的距离，TSP 要求找出一条最短路线，恰好访问每座城市一次并回到起点。它是组合优化中被研究得最多的问题之一，属于 NP 困难问题，也就是说目前没有已知的多项式时间精确算法。

为什么 TSP 这么难解？

不同回路的数量按 (n-1)!/2 增长，因此 20 座城市就已经允许大约六亿亿条回路。没有任何已知算法能在最坏情况下避免指数级的工作量。最好的精确方法 Held-Karp 动态规划运行在 O(n 的平方乘以 2 的 n 次方)，超过大约 25 座城市就不再可行。

解决 TSP 最好的算法是什么？

这取决于规模。低于约 20 座城市时，Held-Karp 给出精确最优解。对满足度量性质的实例，Christofides 保证回路不超过最优解的 1.5 倍。对大规模的真实实例，Lin-Kernighan 或最近邻加 2-opt 能在数秒内给出与最优解相差几个百分点的回路。

2-opt 究竟做了什么？

它反复从回路中移除两条边，再把由此产生的两条路径反向接回去，若回路变短就保留这一改动。从几何上看它消除的是交叉：只要回路中有两条边相交，依据三角不等式，不交叉的接法必然更短。

TSP 与车辆路径问题有什么区别？

TSP 让单台车辆走遍所有城市，除了每座城市访问一次之外没有别的约束。VRP 则让一支车队从仓库出发，通常带有载重上限，往往还有时间窗和司机班次。TSP 是 VRP 在单车辆且载重无限时的特例。