這篇文章主要介紹了Python基於回溯法子集樹模板解決旅行商問題（TSP）,簡單描述了旅行商問題並結合實例形式分析了Python使用回溯法子集樹模板解決旅行商問題的相關實現步驟與操作技巧,需要的朋友可以參考下
本文實例講述了Python基於回溯法子集樹模板解決旅行商問題（TSP）。分享給大家供大家參考，具體如下：
問題
#旅行商問題（Traveling Salesman Problem,TSP）是旅行商要到若干個城市旅行，各城市之間的費用是已知的，為了節省費用，旅行商決定從所在城市出發，到每個城市旅行一次後返回初始城市，問他應選擇什麼樣的路線才能使所走的總費用最短？
分析
#此問題可描述如下：G=(V,E)是帶權的有向圖，找到包含V中每個結點一個有向環，亦即一條週遊路線，使得這個有向環上所有邊成本之和最小。
這個問題與前一篇http://www.jb51.net/article/122933.htm的差別就是，本題是帶權的圖。只要一點小小的修改即可。
解的長度是固定的n+1。
對圖中的每一個節點，都有自己的鄰接節點。對某個節點而言，其所有的鄰接節點構成這個節點的狀態空間。當路徑到達這個節點時，遍歷其狀態空間。
最終，一定可以找到最優解!
顯然，繼續套用回溯法子集樹模板！ ！ ！
程式碼
'''旅行商问题（Traveling Salesman Problem,TSP）'''
# 用邻接表表示带权图
n = 5 # 节点数
a,b,c,d,e = range(n) # 节点名称
graph = [
{b:7, c:6, d:1, e:3},
{a:7, c:3, d:7, e:8},
{a:6, b:3, d:12, e:11},
{a:1, b:7, c:12, e:2},
{a:3, b:8, c:11, d:2}
]
x = [0]*(n+1) # 一个解（n+1元数组，长度固定）
X = [] # 一组解
best_x = [0]*(n+1) # 已找到的最佳解（路径）
min_cost = 0 # 最小旅费
# 冲突检测
def conflict(k):
global n,graph,x,best_x,min_cost
# 第k个节点，是否前面已经走过
if k < n and x[k] in x[:k]:
return True
# 回到出发节点
if k == n and x[k] != x[0]:
return True
# 前面部分解的旅费之和超出已经找到的最小总旅费
cost = sum([graph[node1][node2] for node1,node2 in zip(x[:k], x[1:k+1])])
if 0 < min_cost < cost:
return True
return False # 无冲突
# 旅行商问题（TSP）
def tsp(k): # 到达（解x的）第k个节点
global n,a,b,c,d,e,graph,x,X,min_cost,best_x
if k > n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n）
cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # 计算总旅费
if min_cost == 0 or cost < min_cost:
best_x = x[:]
min_cost = cost
#print(x)
else:
for node in graph[x[k-1]]: # 遍历节点x[k-1]的邻接节点（状态空间）
x[k] = node
if not conflict(k): # 剪枝
tsp(k+1)
# 测试
x[0] = c # 出发节点：路径x的第一个节点（随便哪个）
tsp(1) # 开始处理解x中的第2个节点
print(best_x)
print(min_cost)效果圖
以上是實例講解Python基於回溯法子集樹模板解決旅行商問題（TSP）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
