這個問題可以堪稱一個全排列，[起點，剩下的全排列]

回溯法

import numpy as npclass backtracking_Traveling_saleman:# 初始化，明確起點def __init__(self,graph,start=0):# 頂點的個數self.vertex_num = len(graph)self.graph = graphself.start = start# 當前解，當前解為頂點的集合[起點，頂點1，...頂點n-1],初始時，第0個為起點# 從第一個到n-1個為排列樹# 解為[起點，頂點1，...頂點n-1]# 解的目標函數為：起點到頂點1距離（depth =1）+頂點1到頂點2的+...+頂點depth-1到depth的距離# 頂點n-2到頂點n-1(depth=n-1)距離，最后還要構成環路+頂點n-1到起點的距離，求上述和的最小值。self.curSolution = [i for i in range(self.vertex_num)]# 用于存最好的解self.bestSolution = [-1] *self.vertex_num# 當前花費初始距離為0self.curCost = 0# 界初始為很大，得到一個解之后更新，也可以提前更新self.bestCost = np.infdef backtracking(self,depth):# 當到達最后一個頂點，為遞歸出口if depth == self.vertex_num-1:# 最后一層時，目前函數應該為：當前的距離和+前一個頂點到最后頂點距離+最后頂點到起點的距離temp_cost = self.curCost + self.graph[self.curSolution[depth-1]][self.curSolution[depth]] + self.graph[self.curSolution[depth]][self.curSolution[self.start]]# 當前解優于最優解的話，更新最優解，假如求可行解的話，就需要把可行解保存起來if temp_cost < self.bestCost:self.bestCost = temp_costself.bestSolution[:] = self.curSolution[:]else:# 下面就是排列樹的處理，我們需要求除了起點之外的[頂點1，...頂點n-1]n-1個起點的全排列# 我們處理的是標號，也就是self.curSolution = [i for i in range(self.vertex_num)]# 所以我們全排列都是self.curSolution里面的數for i in range(depth,self.vertex_num): # self.curSolution[depth],self.curSolution[i] = self.curSolution[i],self.curSolution[depth]# 當滿足我們定義的界時，才可以進入下一層，也就是走過的長度<最優值的話（注意我們這兒要求的是最小值），我們才繼續搜索，否則剪掉# 有沒有人注意到這里是depth-1到i,而不是depth-1 到 depth?# 實際上我們學習到模板應該是，先交換，然后滿足constraint() && bound() 回溯，最后再交換# 編碼時先交換的話，這個地方就應該寫成depth-1 到 depth，還沒交換的話就是depth-1到i# 這里是做了優化處理，不滿足條件的話，交換都沒有必要執行if self.curCost + self.graph[self.curSolution[depth-1]][self.curSolution[i]] < self.bestCost:# 全排列，把 當前 和第一位交換，除第一位以外剩下的的進行全排列self.curSolution[depth],self.curSolution[i] = self.curSolution[i],self.curSolution[depth]# 同理這里為什么是depth-1 到 depth，為不是depth-1到i，也是一樣的道理self.curCost += self.graph[self.curSolution[depth-1]][self.curSolution[depth]]# 進入下一層self.backtracking(depth+1)# 回溯處理，恢復現場self.curCost -= self.graph[self.curSolution[depth-1]][self.curSolution[depth]]self.curSolution[depth],self.curSolution[i] = self.curSolution[i],self.curSolution[depth] # self.curSolution[depth],self.curSolution[i] = self.curSolution[i],self.curSolution[depth]def print_Result(self):# 我們需要求除了起點之外的[頂點1，...頂點n-1]n-1個起點的全排列self.backtracking(1)print(self.bestCost) print(self.bestSolution)

限界分支法，優先級隊列實現方式

約束條件：只能未走過的點
代價函數：走過的長度+后續未走過的長度

如下的優先級隊列方式實現，當前最后解一直到底部才更新，沒有提前更新，所以首先有一次走到底部，而越靠近root的結點的界是越小的，因為大部分都是最小出邊和，那么走到底之后，就會回到靠近靠近root的結點再次往下走，加入當前最優解較大的話，那他就一直處于優先級隊列的尾部，無出頭之日，那優先級隊列就相當于深度優先回溯了。

import numpy as np import heapq class Node:def __init__(self,curCost=None,depth=None,rcost = None,path = None,lbound =None):# 限界函數，我們定義限界函數為：當前走過的長度+未走過的結點最小出邊的長度和# 這個用于優先級隊列排序self.lbound = lbound# 當前走過的距離self.curCost = curCost# 當前的解的深度self.depth = depth# 路徑，從0到depth為已走過的，depth+1到n-1為未走過的結點self.path = path# depth到n-1為未走過的結點的最小出邊的和self.rcost = rcost# 這個用于結點比較大小，之前的（weights,node)方式有時會出問題，是有時候，# 現在使用這種方式，lt means less thandef __lt__(self,other):return int(self.lbound) <int(other.lbound)class prune_Traveling_saleman:def __init__(self,graph,start=0):self.num = len(graph)self.graph = graphself.start = start# 用于存儲最優的結果self.bestNode = Node(np.inf,-1,-1,None,-1)# 用于存儲每個頂點的最小出邊self.minOut = [np.inf]*self.num# 所有的最小出邊之和self.minSum =0for i in range(self.num):for j in range(self.num):if i !=j and graph[i][j] < self.minOut[i]:self.minOut[i] = graph[i][j]self.minSum += self.minOut[i]def traveling_Saleman(self):pqueue =[]# 第0層，就是起點，也可以認為是第一層，這里為了處理數據方便成為第0層# [i for i in range(self.num)]為開始的路徑[0,1,2,3],path[0]是已經確定為0# 最開始curCost =0，depth=0，rcost =self.minSum，lbound= self.minSumcurNode = Node(0,0,self.minSum,[i for i in range(self.num)],self.minSum)# 把第一個結點放入pqueue = [curNode,]depth =0while depth <= self.num-2:# 彈出結點curNode = heapq.heappop(pqueue)curCost = curNode.curCostdepth = curNode.depthrcost = curNode.rcostpath = curNode.path# 當處于倒數第2層時，就可以處理最后結果了，可以考慮結束了if depth == self.num-2:# 處于當處于倒數第2層時，lbound就是當前走過的距離+當前結點到最后一個結點的距離# + 最后一個結點到起點的距離；實際上也可以考慮self.num-1層，那就只需要加上# 當前結點到起點的距離lbound = curCost + self.graph[path[depth]][path[depth+1]] + self.graph[path[depth+1]][path[0]]# 如果下界小于當前最優的結果，就可以考慮輸出結果了if lbound < self.bestNode.curCost:# 把當前值和當前路徑輸出self.bestNode.curCost = lboundself.bestNode.path = path# 以下只是方便退出，當depth == self.num-1時退出node = Node(lbound,depth+1,lbound,path,lbound)heapq.heappush(pqueue,node)else:# 一般情況下首先更新下一層，也就是未走過結點最小出邊和，# 需要減去當前結點的最小出邊，temp_rcost = rcost - self.minOut[path[depth]]for i in range(depth+1,self.num):# 當前走過的距離，需要更新為加上當前結點到下一個結點的距離temp_cur = curCost + self.graph[path[depth]][path[i]]# 當前結點的下界為，當前走過的距離+未走過結點最小出邊和lbound = temp_cur + temp_rcost# 只有當下界小于self.bestNode.curCost才有放入優先級隊列的必要if lbound < self.bestNode.curCost:# # 放入前需要更新path里面這一層depth加入的結點號# 只要把path[depth]記錄為當前選擇的結點就行了，同時path[depth]位置# 之前放置的那個結點放到剛剛空的那個地方就行了# 這一層還有其他的分支，所有不能直接在path上操作，因為這樣下一個分支也# 用這個path就亂了。也可以可以先換了，壓入之后再換回來temp_path = path[:]temp_path[depth+1],temp_path[i] = temp_path[i],temp_path[depth+1]# 把這個分支壓入優先級隊列node = Node(temp_cur,depth+1,temp_rcost,temp_path,lbound)heapq.heappush(pqueue,node)def print_Result(self):self.traveling_Saleman()print(self.bestNode.curCost)print(self.bestNode.path)

測試結果

g =[[0,5,9,4],[5,0,13,2],[9,13,0,7],[4,2,7,0]]backtracking_Traveling_saleman(g,0).print_Result() prune_Traveling_saleman(g,0).print_Result()23 [0, 1, 3, 2] 23 [0, 1, 3, 2]

實際上也可以考慮self.num-1層，那就只需要加上當前結點到起點的距離

def traveling_Saleman(self):pqueue =[]# 第1層，就是起點，也可以認為是第一層，這里為了處理數據方便成為第1層curNode = Node(0,0,self.minSum,[i for i in range(self.num)],self.minSum)pqueue = [curNode,]curNode = heapq.heappop(pqueue)curCost = curNode.curCostdepth = curNode.depthrcost = curNode.rcostpath = curNode.pathwhile depth <= self.num-1:# 處于解的最后一層，lbound就為當前的距離+當前點到起點的距離# 在這種情況下需要注意，需要把結點彈出放在循環體的最后，到達self.num就# 退出循環了，不會再進入判斷體，否者進入判斷，else就會報越界if depth == self.num-1:lbound = curCost + self.graph[path[depth]][path[0]]if lbound < self.bestNode.curCost:self.bestNode.curCost = lboundself.bestNode.path = pathnode = Node(lbound,depth+1,lbound,path,lbound)heapq.heappush(pqueue,node)else: temp_rcost = rcost - self.minOut[path[depth]]for i in range(depth+1,self.num):temp_cur = curCost + self.graph[path[depth]][path[i]]lbound = temp_cur + temp_rcostif lbound < self.bestNode.curCost:# should fixtemp_path = path[:]temp_path[depth+1],temp_path[i] = temp_path[i],temp_path[depth+1]node = Node(temp_cur,depth+1,temp_rcost,temp_path,lbound)heapq.heappush(pqueue,node)curNode = heapq.heappop(pqueue)curCost = curNode.curCostdepth = curNode.depthrcost = curNode.rcostpath = curNode.pathdef print_Result(self):self.traveling_Saleman()print(self.bestNode.curCost)print(self.bestNode.path)

總結

以上是生活随笔為你收集整理的货郎问题：回溯法和限界分支法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。