旅行商问题求解器 TSP

旅行商问题求解器 TSP

旅行商问题求解器是一个实用且具有教育意义的计算器，用于解决经典的旅行商问题 (TSP)：给定一组城市和两两之间的距离，寻找访问每个城市恰好一次并返回起点的最短可能路径。该求解器接受平面坐标或自定义距离矩阵，根据问题规模自动选择最佳算法，并将生成的路线渲染为动画 SVG 地图。

什么是旅行商问题？

形式上，给定一个带有顶点集 $V = \{1, 2, \dots, n\}$ 和边权重 $d(i, j)$ 的完全赋权图 $G = (V, E)$，TSP 寻求顶点的排列 $\pi$，使以下各项最小化：

最后一项用于闭合回路。TSP 是组合优化领域中历史最悠久、研究最深入的问题之一——它在一般情况下是 NP-hard 的，这意味着目前还没有已知算法能在多项式时间内解决所有实例。尽管如此，它出现在无数现实世界的应用中：车辆路径规划、PCB 钻孔、DNA 测序、仓库拣选路径、天文观测调度，甚至是农村邮递。

此求解器的工作原理

Held–Karp 动态规划（精确算法）

对于小规模实例（最多 12 个城市），求解器使用 1962 年由 Richard Bellman 和 Michael Held & Richard Karp 独立发表的 Held–Karp 算法计算可证明的最优路径。关键递推式如下，其中 $C(S, j)$ 是从顶点 1 到顶点 $j$ 恰好访问子集 $S$ 的最短路径：

最优路径成本即为 $\min_{j} [C(\{1,\dots,n\}, j) + d(j, 1)]$。Held–Karp 的运行时间复杂度为 $O(2^n \cdot n^2)$，空间复杂度为 $O(2^n \cdot n)$——这比暴力破解的 $n!$ 有了巨大进步，但仍然是指数级的。超过约 20 个城市后，内存占用就会变得不切实际。

Nearest-Neighbor + 2-opt（启发式算法）

对于较大的实例，求解器使用两阶段启发式算法。首先，Nearest-Neighbor（最近邻算法）通过从每个起始顶点贪婪地走向最近的未访问城市来构建一条快速路径。求解器尝试多个起始顶点并保留最佳路径。然后，2-opt 局部搜索通过迭代地移除两条边并以唯一可能的另一种方式重新连接产生的两条路径来改进路线：

从几何上看，2-opt 移除了路线中的所有“交叉”：任何两个交叉的线段总是可以通过解叉来获得更短的总长度。算法在没有单一交换能提供帮助的局部最优处停止，这被称为 2-optimal 路线。在现实的欧几里得实例中，2-opt 通常能在几毫秒内找到与真实最优解相差 2–5% 以内的路线。

输入格式

坐标模式 (x, y)

每行一个城市。每行格式为 标签, x, y —— 标签是可选的。求解器会自动计算欧几里得距离，并在真实位置可视化城市。

距离矩阵模式

一个 $n \times n$ 的非负距离方阵，每行一行，值由空格或逗号分隔。矩阵可以是对称的或非对称的——非对称矩阵模拟了单行道、可用性不同的机票价格以及受风力影响的旅行。可在“矩阵标签”字段中选择性地提供标签。

算法比较

如何使用此求解器

1. 选择输入模式。 如果您的城市有明确的 (x, y) 位置，请选择“坐标”；如果您的成本是非欧几里得或非对称的，请选择“距离矩阵”。
2. 粘贴或输入数据。 每行一个城市或一行矩阵。点击表单上方的快速示例按钮可预填有效示例。
3. 选择算法。 保持“自动”以使用正确的默认设置：当实例足够小以保证可证明的最优性时使用 Held–Karp，否则使用 NN + 2-opt。如果您想进行比较，可以强制指定特定算法。
4. 选择闭合或开放。 闭合路径返回起点——这是传统的 TSP。开放路径模式解决相关的哈米尔顿路径问题，即销售员在不同的城市结束行程。
5. 点击“求解”。 结果页面会显示路径总长度、路线动画 SVG（点击“重放动画”再次观看）、完整城市序列、逐边明细以及突出显示路径边的距离矩阵。

实例详解

考虑五个城市——一个矩形加一个顶点：A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5)。求解器返回：

• 路线： A → D → E → C → B → A
• 长度： $3 + \sqrt{8} + \sqrt{8} + 3 + 4 \approx$ 15.66
• 是否最优？ 是 —— Held–Karp 证明不存在更短的路线。
• 为什么是这个顺序？ 该路线追踪了这五个点的凸包 (A → D → E → C → B → A)。欧几里得 TSP 的一个经典性质是，最优路径按循环顺序访问凸包上的点；内部点则插在相邻的凸包邻居之间。任何自身交叉的路径，如 A → C → B → D → E → A（长度 $\approx 21.8$），总是可以通过 2-opt 解叉得到更短的结果。

现实世界的应用

• 物流与配送 —— 优化司机在 15 个站点之间的日常路线，以尽量减少燃料和时间。
• 制造业 —— 排列 CNC 钻头在 PCB 上打孔的顺序，以尽量减少机头移动。
• 基因组组装 —— 根据重叠相似性排列 DNA 片段，编码为距离矩阵。
• 天文学 —— 安排望远镜在目标恒星之间的转动，以最大化观测时间。
• 仓库拣选 —— 排列通道访问顺序，以最少的步数完成订单。
• 旅游规划 —— 规划一个多城市旅行，最大限度地减少旅行时间和票价成本。

常见问题解答

什么是旅行商问题？

旅行商问题 (TSP) 要求找到访问每个城市恰好一次并返回起始城市的最短可能路径。它是组合优化中最著名的问题之一，在一般情况下属于 NP-hard 问题，这意味着目前还没有已知算法能在多项式时间内解决所有实例。

什么是 Held–Karp 算法？

Held–Karp 是一种动态规划算法，它在 $O(2^n \cdot n^2)$ 时间和 $O(2^n \cdot n)$ 内存内精确解决 TSP。它比暴力破解（n 阶乘）快得多，但仍是指数级的，因此在实践中仅用于约 20 个城市以下的实例。本求解器在城市数量不超过 12 个时使用 Held–Karp。

什么是 2-opt，为什么要使用它？

2-opt 是一种局部搜索启发式算法，它反复从当前路径中移除两条边，并以另一种可能的方式重新连接产生的两条路径。当新路径更短时，保留该交换。2-opt 每次迭代在多项式时间内运行，并能一致地找到与最优路径相差几个百分点以内的路径，这就是为什么它是大规模 TSP 实例的经典首选启发式算法。

我该什么时候使用坐标还是距离矩阵？

当您的城市位于具有直线距离的平面上时（例如地图上的点、仓库位置或电路板上的钻孔），请使用坐标。当成对成本非欧几里得时（例如机票价格、考虑交通的旅行时间、单行道距离或非对称成本），请使用距离矩阵。矩阵模式接受任何非负距离，甚至是由于单行道引起的非对称距离。

2-opt 解决方案是最优的吗？

不是，2-opt 返回的是 2-最优路径，这意味着无法通过交换单对边来产生更短的路线。这是一个局部最优解，在表现良好的实例上通常在全局最优解的几个百分点以内，但不保证是全局最佳。对于小规模实例的可证明最优路径，请选择 Held–Karp。

此工具是否支持非对称距离矩阵？

支持。在距离矩阵模式下，您可以输入任何非负方阵，包括 $D[i][j]$ 与 $D[j][i]$ 不同的非对称矩阵。Held–Karp 和 2-opt 都能正确处理非对称矩阵。这对于具有单行道、交通或受风力影响的飞行成本等实际路由问题非常有用。

延伸阅读

• 旅行商问题 — 维基百科
• Held–Karp 算法 — 维基百科
• 2-opt — 维基百科
• 最近邻算法 — 维基百科

进阶数学计算:

• antilog计算器
• beta函数计算器
• 二项式系数计算器
• 二项概率分布计算器
• 按位计算器 精选
• 中央极限定理计算器
• 组合计算器 精选
• 互补误差函数计算器 精选
• 复数计算器
• 熵计算器
• 误差函数计算器 精选
• 指数衰减计算器-高精度
• 指数增长计算器 高精度
• 指数积分计算器
• 指数计算器-高精度 精选
• 阶乘计算器
• 伽玛功能计算器
• 黄金比例计算器
• 半衰期计算器 精选
• 百分比增长率计算器 精选
• 排列计算器
• 泊松分布计算器
• 多项式根计算器与详细步骤
• 概率计算器
• 概率分布计算器
• 比例计算器 精选
• 二次公式计算器
• 科学计算器
• 科学记数法计算器 精选
• 有效数字计算器 新
• 立方和计算器
• 连续数之和计算器
• 平方和计算器
• 真值表生成器
• 集合论计算器
• 韦恩图生成器3集合
• 中国剩余定理计算器
• 欧拉函数计算器
• 扩展欧几里得算法计算器
• 模乘逆元计算器
• 连分数计算器
• 迪杰斯特拉最短路径计算器
• 最小生成树计算器
• 图度数序列验证器
• 错排 子阶乘计算器
• 斯特林数计算器
• 鸽巢原理计算器
• 马尔可夫链稳态分布计算器
• 四舍五入计算器 新
• 负二项分布计算器 新
• 重复排列计算器 新
• 模幂运算计算器 新
• 原根计算器 精选
• 布尔代数化简器 新
• 卡诺图 (K-Map) 求解器 新
• 图着色计算器 新
• 拓扑排序计算器 新
• 邻接矩阵计算器 新
• 容斥原理计算器 新
• 线性规划求解器 新
• 旅行商问题求解器 TSP 新
• 哈密顿路径检查器 新
• 平面图检查器 新
• 网络最大流计算器 新
• 稳定婚姻问题求解器 新
• 群论阶数计算器 新
• 环与域计算器 新