引用之前ACM博客状压DP一文对于TSP问题的描述：
经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需经过所有城市后，回到起点。应该如何选择路线，使得总行程距离最短。从图论的观点来看是，该问题实质是在一个有权完全无向图中找一个权值最小的哈密顿回路。
大部分TSP问题都是NP-hard问题，即没有多项式时间复杂度的算法，一般倾向于剪枝搜索或者状压DP的方式解决。这类问题地点数量通常很小。
以上主要考虑的是TSP问题精确解的求法，在数模中我们可以求近似解，从中筛选较优解。
DP首先回顾一下之前状压DP的方法： 关键点：1. 状态压缩已访问节点，实际上可以直接用数组表示集合，这里通过状压的方法用一个数表示集合 2. 转移状态由已访问节点集合以及最后访问节点确定 C++程序实现： 时间复杂度：
O
(
n
2
∗
2
n
)
O(n^2 * 2^n)
O(n2∗2n) 在
P
≠
N
P
Pneq{NP}
P=NP情况下TSP问题不存在多项式时间的常数近似。但是，TSP问题在度量空间是可以有多项式时间的常数近似。所谓度量空间，就是空间中的任意3点满足三角不等式。 因为满足三角不等式，所以
W
(
C
)
≤
2
W
(
T
)
W(C)leq2W(T)
W(C)≤2W(T) ，而
W
(
T
)
≤
O
P
T
W(T){leq}OPT
W(T)≤OPT ,所以
W
(
C
)
≤
2
O
P
T
W(C)leq2OPT
W(C)≤2OPT ，这意味着该近似解不会超过最优解的2倍。 我们发现：由于G’是一棵树的边double而得，对G’进行dfs遍历，递归时走原边，回溯时走复制边，跳过重复的点得到实际就是树的前/中/后序序列。 python程序实现： 时间复杂度：以上实现比较低效，主要是Prim算法中findEdge()函数会重复访问一条边，通过类似Dijkstra算法中用堆存储所有边，依次弹出所有边并判断一下是否是由已访问点连向未访问点的，可以保证所有边访问一次，这样的时间复杂度为
O
(
m
l
o
g
m
)
O(mlogm)
O(mlogm) ，而
1
/
2
n
∗
n
≥
m
1/2n*ngeq{m}
1/2n∗n≥m ，因此可以表示为
O
(
n
3
l
o
g
n
)
O(n^3logn)
O(n3logn) 。 https://zhuanlan.zhihu.com/p/315210267 讨论度量空间下TSP问题的两个近似算法
定义状态：
f
[
s
t
a
t
u
s
]
[
j
]
：
表
示
状
态
为
s
t
a
t
u
s
（
即
已
经
过
s
t
a
t
u
s
所
表
示
点
集
）
，
最
后
访
问
的
是
节
点
j
的
最
短
距
离
f[status][j]： 表示状态为 status （即已经过 status 所表示点集），最后访问的是节点 j 的最短距离
f[status][j]：表示状态为status（即已经过status所表示点集），最后访问的是节点j的最短距离
递推方程：
f
[
s
t
a
t
u
s
]
[
j
]
=
m
i
n
k
∈
s
t
a
t
u
s
&
&
j
∉
s
t
a
t
u
s
(
f
[
s
t
a
t
u
s
−
(
1
<
<
j
)
]
[
k
]
+
d
i
s
[
k
]
[
j
]
)
f[status][j] = min_{k{in}status&&j{notin}status}(f[status-(1<// 参照第二个递推方程
for (int i = 1; i < (1 << n); i++) { // i即是status,枚举状态
for (int j = 0; j < n; j++) { // 枚举
if (!((i >> j) & 1)) continue; // 枚举状态f[i]可能的最后访问节点
for (int k = 0; k < n; k++) { // j -> k，k为状态f[i|(1<
from cmath import inf
import numpy as np
# import matplotlib.pyplot as plt
# 代价函数，具有三角不等式性质
def Price(v1, v2):
return np.linalg.norm(np.array(v1) - np.array(v2))
# Prim算法 #
# 找已访问点和未访问点相连的最短边
def findEdge(vis, unvis):
minWeight, _from, _to = np.inf, np.inf, np.inf
# i -> j
for i in vis:
for j, w in enumerate(G[i]):
if w < minWeight and j in unvis:
_from = i
_to = j
minWeight = G[i][j]
return (_from, _to), minWeight
# 获得未访问点集
def getUnvis(G, vis):
unvis = []
[unvis.append(i) for i, _ in enumerate(G) if i not in vis]
return unvis
def Prim(G, root = 0):
vis = [root] # 维护已访问点集
Path = []
while len(vis) != G.shape[0]:
unvis = getUnvis(G, vis)
(_from, _to), minWeight = findEdge(vis, unvis)
vis.append(_to)
Path.append((_from, _to))
T = np.full_like(G, np.inf) # 最小生成树的矩阵形式
for (i, j) in Path:
T[i][j] = G[i][j]
T[j][i] = G[j][i]
return T, Path
# 获得最小生成树的前序序列
def preOrder(T, root = 0):
vis = [False] * T.shape[0]
stack = [root]
L = []
while len(stack) != 0:
u = stack.pop()
L.append(u)
vis[u] = True
nxt = np.where(T[u] != np.inf)[0]
if len(nxt) > 0:
[stack.append(v) for v in reversed(nxt) if vis[v] is False]
return L
# Prim算法 #
# 生成哈密顿回路
def H(G, L):
H = np.full_like(G, np.inf)
Path = []
for i, _from in enumerate(L[0:-1]):
_to = L[i + 1]
H[_from][_to] = G[_from][_to]
H[_to][_from] = G[_to][_from]
Path.append((_from, _to))
return H, Path
# def Draw(city, Path):
# fig = plt.figure()
city = [(2, 6), (2, 4), (1, 3), (4, 6), (5, 5), (4, 4), (6, 4), (3, 2)] # 城市坐标
G = []
# 建图
for i, p1 in enumerate(city):
line = []
for j, p2 in enumerate(city):
line.append(Price(p1, p2)) if i != j else line.append(np.inf)
G.append(line)
G = np.array(G) # 邻接矩阵
# print(G)
# 1.选择任意一个起点
root = 0
# 2.Prim求最小生成树
T, T_Path = Prim(G, root = root)
# print(T)
# 3.前序遍历得到顶点表L
L = preOrder(T, root = root)
# 4.根据L生成汉密顿回路H
L.append(root)
H, H_Path = H(G, L)
print('最小生成树的路径为：{}'.format(T_Path))
[print(chr(97 + v), end = ',' if i < len(L) - 1 else 'n') for i, v in enumerate(L)]
print('哈密顿回路的路径为：{}'.format(H_Path))
print('哈密顿回路产生的代价为：{}'.format(sum(G[i][j] for (i, j) in H_Path)))
求最小生成树T：
求前序序列L：
https://www.jianshu.com/p/d1e004bdea8d 近似解python实现
https://www.isolves.com/it/cxkf/sf/2020-07-19/24491.html SOM（竞争神经网络）算法求解
https://zhuanlan.zhihu.com/p/467270686 TSP求解算法集合
