追蹤解

追蹤解，上述實(shí)現(xiàn)的情況下，解都在最后一層，根本不知道之前的路徑是怎樣的，廣度優(yōu)先搜索，同一個(gè)緯度，假如不加指標(biāo)判斷的話，根本不知道最優(yōu)解是選擇的哪一個(gè)，所以需要同一個(gè)緯度的每一個(gè)結(jié)點(diǎn)，記住他之前的路徑，才能在最優(yōu)解的時(shí)候之前是怎么走過來的，每一個(gè)結(jié)點(diǎn)用一個(gè)數(shù)組記錄路徑，這樣實(shí)現(xiàn)的感覺消耗有點(diǎn)大啊，通常看見是采用鏈表方式

限界分支法本質(zhì)還是空間樹，樹的話，還是用鏈表實(shí)現(xiàn)比較容易和直觀

把之前實(shí)現(xiàn)基于數(shù)組的形式修改成結(jié)點(diǎn)鏈表方式

實(shí)現(xiàn)如下：

#%% # 修改成結(jié)點(diǎn)，為了追蹤解，新增兩個(gè)變量，是否選擇物品和前一個(gè)物品的結(jié)點(diǎn) class Node:def __init__(self, CurCost=None,CurValue=None,Flag=None,parent=None):# 部分解所占體積self.CurCost = CurCost# 部分解所占價(jià)值self.CurValue = CurValue# 當(dāng)前結(jié)點(diǎn)是否選擇了物品self.isleft = Flag# 前一個(gè)結(jié)點(diǎn)是誰self.parent = parentclass FIFO_01_Pack_with_solution_tracking:def __init__(self,N,V,C,W):self.num =Nself.Volume = Vself.Cost = Cself.Value = W# 存放最優(yōu)解self.BestResult = [False]*N # 最優(yōu)解結(jié)點(diǎn)，這里是葉子結(jié)點(diǎn)self.BestNode = Node(0,0,False,None)#用于存放活結(jié)點(diǎn)，便于理解，把根結(jié)點(diǎn)，以及第0層結(jié)束標(biāo)志-1放進(jìn)去# 結(jié)點(diǎn)包括2個(gè)屬性：當(dāng)前空間大小，當(dāng)前的價(jià)值大小self.queue = [Node(0,0,False,None),Node(-1,-1,False,None),] # 實(shí)現(xiàn)時(shí)葉子結(jié)點(diǎn)不加入到活結(jié)點(diǎn)列表，當(dāng)屬于葉子結(jié)點(diǎn)時(shí)，增加對(duì)結(jié)果的處理def enQueen(self,node,depth):if depth == self.num -1:CurValue = node.CurValueif CurValue > self.BestNode.CurValue:self.BestNode.CurValue = CurValueself.BestNode.isleft = node.isleftself.BestNode.parent = node.parent else:self.queue.append(node)def pack_01(self): # selected = [0]*self.num # 首先取出根結(jié)點(diǎn)depth = 0node = self.queue.pop(0)CurCost = node.CurCostCurValue = node.CurValuewhile True:# 判斷左結(jié)點(diǎn)能否加入到隊(duì)列，能的話，把當(dāng)前空間和當(dāng)前價(jià)值放入隊(duì)列if CurCost + self.Cost[depth] < self.Volume:# 這時(shí)的父節(jié)點(diǎn)就是nodeself.enQueen(Node(CurCost + self.Cost[depth],CurValue + self.Value[depth],True,node),depth)# 右結(jié)點(diǎn)總是可以加入隊(duì)列的，因?yàn)闆]有約束條件的限制self.enQueen(Node(CurCost,CurValue,False,node),depth)# 然后彈出下一個(gè)結(jié)點(diǎn)node = self.queue.pop(0)CurCost = node.CurCostCurValue = node.CurValue# 當(dāng)同一層處理完畢時(shí)，先判斷是否能夠輸出結(jié)果，判斷的標(biāo)準(zhǔn)是隊(duì)列是否為空，# 這時(shí)下一層的所有結(jié)點(diǎn)已經(jīng)加入了隊(duì)列，這時(shí)需要把下一層# 增加一個(gè)結(jié)尾-1便于判斷，然后進(jìn)入下一層，彈出下一個(gè)結(jié)點(diǎn)if CurCost == -1:if not self.queue:return self.BestNode.CurValueself.enQueen(Node(-1,-1,False,None),depth)depth += 1node = self.queue.pop(0)CurCost = node.CurCostCurValue = node.CurValuedef solution_Tracking(self):#追蹤解從self.BestNode開始追蹤for j in range(self.num-1,-1,-1):self.BestResult[j] = self.BestNode.isleftself.BestNode = self.BestNode.parentreturn self.BestResultdef print_Result(self):print(self.pack_01())print(self.solution_Tracking())N = 8 V = 30 C = [11,2,3,9,13,6,15,7,19] W = [5.0,2.0,5.0,7.0,5.0,11.0,6.0,14.0]FIFO_01_Pack_with_solution_tracking(N,V,C,W).print_Result()39.0 [False, True, True, True, False, True, False, True]

總結(jié)

以上是生活随笔為你收集整理的限界分支法（队列方式）追踪解：01背包问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。