旅行商问题： Python, C++ 算法
编辑团队
什么是旅行商问题（TSP）？
旅行商问题（TSP）是理论计算机科学中的一个经典组合优化问题。给定一个城市图，TSP 要求找到一条最短路径，该路径访问每个节点恰好一次，并最终返回出发城市。
题目陈述中列出了各个城市以及每两个城市之间的距离。
目的： 从出发城市出发，依次访问其他每个城市一次，最后返回出发城市。目标是找到最短的往返路线。
TSP 示例
考虑下图，其中 1、2、3 和 4 代表城市，每条边的权重代表这些城市之间的距离。
目标是找到一条最短的旅游路线，从出发城市出发，访问其他每个城市一次，然后返回出发城市。
对于上图，最优路径为 1-2-4-3-1最短行程费用为 10 + 25 + 30 + 15 = 80.
旅行商问题的不同解决方案
旅行商问题被归类为NP难问题，因为目前尚无已知的多项式时间算法能够精确求解它。问题的复杂度随城市数量的增加呈指数级增长。
攻击旅行商问题的方法有很多种。最常见的方法有：
蛮力法： 朴素方法计算所有可能的路径并进行比较。包含 n 个城市的图中的路径数量为 n!这使得暴力搜索超过十个城市后，计算成本会非常高昂。
分支定界法： 问题被分解成若干子问题，这些子问题的解组合起来可以得到最优解。有效的剪枝方法会舍弃那些无法超越当前最优成本的部分路径。
本教程演示了 动态规划方法这是分支定界算法的记忆化版本，与 Bellman-Held-Karp 算法相匹配。
动态规划： 这是一种通过重用重叠区域来寻找最优解的精确方法。ping 子问题的结果。它比接近最优解的速度慢。 贪婪方法但它总是返回全局最优解。
该方法的计算复杂度为 O(N² × 2^N)我们将在本文后面讨论这一点。
最近邻方法： 一种启发式贪婪算法，总是直接跳转到最近的未访问城市。它比动态规划的计算成本低得多，但不能保证找到最优路径，因此适用于速度比精确最小值更重要的近似最优解。
旅行商问题的算法
我们使用动态规划方法来解决旅行商问题。在开始算法之前，让我们先明确几个术语：
- 图
G = (V, E)是顶点和边的集合。 V是顶点的集合。E是边的集合。- 顶点通过边连接。
Dist(i, j)表示顶点 i 和 j 之间的非负距离。
假设 S 是从集合 {1, 2, 3, …, n} 中抽取的城市子集，其中 i 和 j 是该子集中的两个城市。 cost(i, S, j) 是从 i 出发，访问 S 中的每个城市恰好一次，到 j 结束的最短路径的长度。
例如， cost(1, {2, 3, 4}, 1) 表示最短路径，其中：
- 出发城市为 1
- 城市 2、3 和 4 仅访问过一次
- 终点是 1
动态规划的递推式为：
- 米
cost(i, {}, i) = 0这意味着我们从 i 开始，到 i 结束，成本为零。 - 日期
|S| > 1，定义cost(i, S, 1) = ∞HPMC胶囊i ≠ 1因为真正的旅游费用目前还不得而知。 - 从城市 1 开始，选择下一个城市，以便
cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]HPMC胶囊i ∈ S和i ≠ j.
对于上图，邻接矩阵如下：
| dist(i, j) | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
算法的运行过程如下：
步骤1） 旅程从城市 1 开始，依次访问其他所有城市一次，然后返回城市 1。
步骤2） S 是城市的一个子集。对于每个 |S| > 1，初始化 cost(i, S, 1) = ∞。 这里 cost(i, S, j) 表示从 i 出发，访问 S 中的每个城市一次，最终到达 j 的路径。我们从无穷远处开始，因为此时距离未知。因此，其值为：
cost(2, {3, 4}, 1) = ∞ 这意味着我们从城市 2 出发，途经城市 3 和 4，最终到达城市 1，但成本未知。类似地：
cost(3, {2, 4}, 1) = ∞
cost(4, {2, 3}, 1) = ∞
步骤3） 对于 S 的每个子集，计算：
cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]，在 Moku:Pro 上 j ∈ S 和 i ≠ j.
这是从城市 i 出发，访问城市子集一次，然后返回城市 j 的最低成本路径。由于该路径从城市 1 出发，因此最优成本为 cost(1, {other cities}, 1).
逐步处理循环
现在 S = {1, 2, 3, 4}。共有四个元素，因此子集的数量为 。 2^4 = 16这些子集包括：
1）|S| = 0： {φ}
2）|S| = 1： {{1}, {2}, {3}, {4}}
3）|S| = 2： {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4）|S| = 3： {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5）|S| = 4： {{1, 2, 3, 4}}
因为行程是从城市 1 开始的，所以我们在计算中间成本时可以舍弃包含城市 1 的所有子集。
算法计算过程如下：
1）|S| = Φ：
- cost(2, Φ, 1) = dist(2, 1) = 10
- cost(3, Φ, 1) = dist(3, 1) = 15
- cost(4, Φ, 1) = dist(4, 1) = 20
2）|S| = 1：
- cost(2, {3}, 1) = dist(2, 3) + cost(3, Φ, 1) = 35 + 15 = 50
- cost(2, {4}, 1) = dist(2, 4) + cost(4, Φ, 1) = 25 + 20 = 45
- cost(3, {2}, 1) = dist(3, 2) + cost(2, Φ, 1) = 35 + 10 = 45
- cost(3, {4}, 1) = dist(3, 4) + cost(4, Φ, 1) = 30 + 20 = 50
- cost(4, {2}, 1) = dist(4, 2) + cost(2, Φ, 1) = 25 + 10 = 35
- cost(4, {3}, 1) = dist(4, 3) + cost(3, Φ, 1) = 30 + 15 = 45
3）|S| = 2：
- cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
- cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
- cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75
4）|S| = 3：
- cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80
因此，最优解是 1-2-4-3-1.
伪代码
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, ..., n} of size s
Cost (s, S, 1) = Infinity
for all i in S and i != 1
Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)
在 C/ 中实现C++
以下是实现方式 C++以下版本修复了源代码早期版本的问题。 return 该错误导致程序在第一次排列后就返回结果，而不是枚举所有路径。
#include <bits/stdc++.h> using namespace std; #define V 4 #define MAX 1000000 int tsp(int graph[][V], int s) { vector<int> vertex; for (int i = 0; i < V; i++) if (i != s) vertex.push_back(i); int min_cost = MAX; do { int current_cost = 0; int j = s; for (int i = 0; i < vertex.size(); i++) { current_cost += graph[j][vertex[i]]; j = vertex[i]; } current_cost += graph[j][s]; min_cost = min(min_cost, current_cost); } while (next_permutation(vertex.begin(), vertex.end())); return min_cost; } int main() { int graph[][V] = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } }; int s = 0; cout << tsp(graph, s) << endl; return 0; }
输出：
80
在实施 Python
此 Python 实施过程与此类似 C++ 版本。它修正了源文件的…… from itertools, import 逗号拼写错误，错位 return 内环内部，以及多余的压痕 s = 0.
from sys import maxsize from itertools import permutations V = 4 def tsp(graph, s): vertex = [] for i in range(V): if i != s: vertex.append(i) min_cost = maxsize for perm in permutations(vertex): current_cost = 0 k = s for j in perm: current_cost += graph[k][j] k = j current_cost += graph[k][s] min_cost = min(min_cost, current_cost) return min_cost graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] s = 0 print(tsp(graph, s))
输出：
80
TSP 的学术解决方案
计算机科学家几十年来一直在寻找改进的旅行商问题多项式时间算法。但迄今为止，旅行商问题仍然是NP难问题。
一些已发表的技术降低了特定类型旅行商问题实例的实际复杂度：
- 经典的对称旅行商问题可以通过以下方式解决： 零后缀法.
- 此 基于生物地理学的优化算法 使用迁移策略来解决与旅行商问题相对应的优化问题。
- 此 多目标进化算法 专为多目标 TSP 问题设计，并以 NSGA-II 算法为基础。
- 此 多Agent系统 该方法利用固定的计算资源解决 N 个城市的旅行商问题。
- 此 林-克尼汉启发法 及其后继者 洛康赫 对于拥有数百万个城市的实例，将旅游路线的误差控制在最佳路线的 2-3% 以内。
- 和睦 使用割平面和分支切割法计算包含数万个城市的基准实例的精确最优解。
旅行商问题的应用
旅行商问题在现实世界中以纯粹形式和变体形式出现。其主要应用包括：
- 规划、物流和微芯片制造： 微芯片行业的芯片插入问题被建模为 TSP 的变体，以最大限度地减少机器人手臂的移动时间。
- DNA测序： 在 DNA 测序中使用了改进的 TSP，其中城市代表 DNA 片段，距离代表片段之间的相似性。
- 天文： 天文学家利用 TSP 来最大限度地减少在观测目标之间转动望远镜所花费的时间。
- 最优控制： TSP 问题模型模拟了在最小化遍历成本的同时必须满足多个约束条件的最优控制问题。
- 最后一英里交货： AmazonUPS 和外卖应用程序通过解决动态 TSP 变体问题来安排司机的送货顺序。
- 仓库拣货： 机器人和人工拣货员遵循 TSP 优化路线，从而缩短配送中心内的行走时间。
TSP 的复杂性分析
- 时间复杂度： Held-Karp动态规划方法解决了2个问题。N 每个起始节点的子集，给出
N × 2^N子问题。每个子问题的组合时间复杂度为线性。如果起始节点未指定，则需要一个遍历 N 个节点的外部循环。总时间复杂度为O(N² × 2^N). - 空间复杂度： DP 表存储
C(S, i)对于顶点集的每个子集 S，共有 2 个N 每个节点有子集，因此空间复杂度为O(N × 2^N)，通常写作O(2^N)当 N 被视为固定值时。
接下来，了解一下 埃拉托斯特尼筛法.
