众所周知，TSP问题是一个NP问题，想精确求得解需要指数级的计算量。即使使用分支限界方法等非近似算法算得依然很慢。在大部分情况只能考虑通过近似的方法来求解。比较好的近似算法有：
Lin–Kernighan 在100以内几乎可以得到最优解，速度很快，时间复杂度 O ( n 2.2 ) O(n^{2.2}) O(n2.2)Christofides 理论最坏情况可以达到1.5倍的近似比，时间复杂度 O ( n 3 ) O(n^3) O(n3)
但是由William J. Cook等人实现的精确求解器Concorde，通过特殊的数值优化技巧却达到了很快的速度。规模几百左右的TSP问题都能够在很快求解。非常适用用来做学术研究。
本文对该求解器的python包装版本pyconcorde进行了安装和使用。记录了详细的配置步骤和实验结果。
安装环镜语言环境：python 3.8
系统环境：ubuntu 20 x64 或 OSX 12.0.1 x64
安装依赖git clone https://github.com/jvkersch/pyconcorde cd pyconcorde pip install . -i https://pypi.tuna.tsinghua.edu.cn/simple pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple使用示例
from concorde.tsp import TSPSolver
from typing import *
from random import random
import matplotlib.pyplot as plt
import numpy as np
def tsp(dots:List[Tuple[float, float]])->List[int]:
"""
TSP最优算法（concorde）
:param dots: 一系列的点的坐标，点之间的距离表示代价
:return: 一系列点的编号，代表得到的哈密顿环
"""
# solver only supports integral edge weights, so here float will be rounded to two
# decimals, multiplied by 100 and converted to integer
xs = []
ys = []
for (x, y) in dots:
xs.append(int(x * 1000))
ys.append(int(y * 1000))
solver = TSPSolver.from_data(xs, ys, norm="EUC_2D")
solution = solver.solve()
#print(solution.found_tour)
#print(solution.optimal_value)
#print(solution.tour)
return solution.tour.tolist()
class ConcordeTsp(object):
"""
TSP算法封装类
使用方法：ConcordeTsp(dots).tsp()
其中，dots为二维平面上的点的列表
"""
def __init__(self, dots:List[Tuple[float, float]]):
# 去除重复的点
dotSet = set()
dotFilted = []
for dot in dots:
if not dot in dotSet:
dotSet.add(dot)
dotFilted.append(dot)
self.__dots = dotFilted
def tsp(self)->List[int]:
"""
:return: tsp回路的近似解，返回结果不包含初始结点
"""
return tsp(self.__dots)
if __name__ == "__main__":
"""以下是测试代码"""
dots = []
xs = []
ys = []
for i in range(51):
x = random()
y = random()
dots.append((x, y))
xs.append(x)
ys.append(y)
path = ConcordeTsp(dots).tsp()
print(path)
path.append(path[0])
plt.scatter(np.array(xs)[path], np.array(ys)[path])
for i in range(len(xs)):
plt.annotate(str(path[i]),
xy=(xs[path[i]], ys[path[i]]),
xytext=(xs[path[i]] + 0.0001, ys[path[i]] + 0.0001))
# 这里xy是需要标记的坐标，xytext是标签显示的位置
plt.plot(np.array(xs)[path], np.array(ys)[path])
plt.show()
请查看 concordewapper.py 中的测试代码。下面是一个规模为51的欧式空间TSP问题的运行结果
OSX 系统需要在pyconcorde中的setup.py开头处添加以下代码（为了跳过SSL验证，否则安装pyconcorde会报错）。
import ssl ssl._create_default_https_context = ssl._create_unverified_context
本项目使用的是pyconcorde版本是 0.1.0
