主要參考：Python求解tsp問題（動態(tài)規(guī)劃，簡單易懂）CSDN博客
解題思路主要有兩部分：
-
i為當前節(jié)點（城市）舟山，S為還沒有遍歷的節(jié)點（城市集合）攒岛，表示從第i個節(jié)點起，經歷S集合中所有的點鲤脏，到達終點的最短路徑長度。
回溯找到最優(yōu)的路徑吕朵，需要將S集合一一對應一個數字（類似于編碼猎醇，一般用二進制），然后比如從節(jié)點i等于0開始努溃，未經歷集合為
S={1硫嘶，2，3}梧税，而下一步最優(yōu)的節(jié)點 j 等于2沦疾，那么M[i][s]=j，回溯時只用從M[0][S]向后推即可第队。
import numpy as np
import itertools
import random
import matplotlib.pyplot as plt
# 設置中文識別
plt.rcParams['font.sans-serif'] = ['SimHei']
# tsp問題
class Solution:
def __init__(self,X,start_node):
self.X = X #距離矩陣
self.start_node = start_node #開始的節(jié)點
self.array = [[0]*(2**(len(self.X)-1)) for i in range(len(self.X))] #記錄處于x節(jié)點哮塞，未經歷M個節(jié)點時，矩陣儲存x的下一步是M中哪個節(jié)點
def transfer(self, sets):
su = 0
for s in sets:
su = su + 2**(s-1) # 二進制轉換
return su
# tsp總接口
def tsp(self):
s = self.start_node
num = len(self.X)
cities = list(range(num)) #形成節(jié)點的集合
# past_sets = [s] #已遍歷節(jié)點集合
cities.pop(cities.index(s)) #構建未經歷節(jié)點的集合
node = s #初始節(jié)點
return self.solve(node, cities) #求解函數
def solve(self, node, future_sets):
# 迭代終止條件斥铺，表示沒有了未遍歷節(jié)點彻桃，直接連接當前節(jié)點和起點即可
if len(future_sets) == 0:
return self.X[node][self.start_node]
d = 99999
# node如果經過future_sets中節(jié)點，最后回到原點的距離
distance = []
# 遍歷未經歷的節(jié)點
for i in range(len(future_sets)):
s_i = future_sets[i]
copy = future_sets[:]
copy.pop(i) # 刪除第i個節(jié)點晾蜘，認為已經完成對其的訪問
distance.append(self.X[node][s_i] + self.solve(s_i,copy))
# 動態(tài)規(guī)劃遞推方程邻眷，利用遞歸
d = min(distance)
# node需要連接的下一個節(jié)點
next_one = future_sets[distance.index(d)]
# 未遍歷節(jié)點集合
c = self.transfer(future_sets)
# 回溯矩陣眠屎，（當前節(jié)點，未遍歷節(jié)點集合）——>下一個節(jié)點
self.array[node][c] = next_one
return d
# 計算兩點間的歐式距離
def distance(vector1,vector2):
d=0;
for a,b in zip(vector1,vector2):
d+=(a-b)**2;
return d**0.5;
首先在（10肆饶，10）的坐標上改衩，隨機生成10個城市：
# 隨機生成10個坐標點
n = 10
random_list = list(itertools.product(range(1, n), range(1, n)))
cities = random.sample(random_list, n)
x = []
y = []
for city in cities:
x.append(city[0])
y.append(city[1])
fig = plt.figure()
plt.scatter(x,y,label='城市位置',s=30)
plt.xlabel('x')
plt.ylabel('y')
plt.title('TSP問題 隨機初始城市')
plt.legend()
plt.show()
使用歐氏距離計算兩兩城市之間的距離：
distence_matrix = np.zeros([n,n])
for i in range(0, n):
for j in range(n):
distence = distance(cities[i],cities[j])
distence_matrix[i][j] = distence
使用動態(tài)規(guī)劃求解TSP問題：
S = Solution(distence_matrix,0)
print("最短距離：" + str(S.tsp()))
# 開始回溯
M = S.array
lists = list(range(len(S.X)))
start = S.start_node
city_order = []
while len(lists) > 0:
lists.pop(lists.index(start))
m = S.transfer(lists)
next_node = S.array[start][m]
print(start,"--->" ,next_node)
city_order.append(cities[start])
start = next_node
得到最終的訪問路線：
x1 = []
y1 = []
for city in city_order:
x1.append(city[0])
y1.append(city[1])
x2 = []
y2 = []
x2.append(city_order[-1][0])
x2.append(city_order[0][0])
y2.append(city_order[-1][1])
y2.append(city_order[0][1])
plt.plot(x1,y1,label='路線',linewidth=2,marker='o',markersize=8)
plt.plot(x2,y2,label='路線',linewidth=2,color='r',marker='o',markersize=8)
plt.xlabel('x')
plt.ylabel('y')
plt.title('TSP問題 路線圖')
plt.legend()
plt.show()
