本文實例講述了Python基于回溯法子集樹模板解決旅行商問題（TSP）。分享給大家供大家參考，具體如下：

問題

旅行商問題（Traveling Salesman Problem,TSP）是旅行商要到若干個城市旅行，各城市之間的費用是已知的，為了節省費用，旅行商決定從所在城市出發，到每個城市旅行一次后返回初始城市，問他應選擇什么樣的路線才能使所走的總費用最短？

分析

此問題可描述如下：G=(V,E)是帶權的有向圖，找到包含V中每個結點一個有向環，亦即一條周游路線，使得這個有向環上所有邊成本之和最小。

這個問題與前一篇文章//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相關內容可查看本站專題：《Python數據結構與算法教程》、《Python Socket編程技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》