6.1分支限界法概述6.2廣度優先搜索CONTENTS提綱6.3隊列式分支限界法6.4優先隊列式分支限界法第6章朝最優解方向前進—分支限界法1/966.3.1隊列式分支限界法概述6.3隊列式分支限界法在解空間中搜索解時，隊列式分支限界法與廣度優先搜索相同，也是采用普通隊列存儲活結點。從根結點開始一層一層地擴展和搜索結點，同時利用剪支以提高搜索性能。2/961 defbfs(): #隊列式分支限界法算法框架2 定義一個隊列qu3 根結點進隊4 while隊不空時循環:5 出隊結點e6 for擴展結點e產生結點e1:7 ife1滿足constraint()andbound():8 ife1是葉子結點:9 比較得到一個更優解或者直接返回10 else:11 將結點e1進隊3/96在結點e出隊時判斷，也就是在結點e擴展出子結點之前對e進行判斷。在出隊的結點e擴展出子結點e1后再對e1進行判斷。前者的優點是算法設計簡單，后者的優點是節省隊列空間，因為一般情況下解空間中葉子結點可能非常多，而葉子結點是不會擴展的，前者仍然將葉子結點進隊了。判斷是否為葉子結點的兩種方式4/96問題描述：給定一個帶權有向圖G=（V，E），其中每條邊的權是一個正整數。另外給定V中的一個頂點s，稱為源點。計算從源點到其他所有其他各頂點的最短路徑及其長度。這里的路徑長度是指路上各邊權之和。41050201030100024531606.3.2圖的單源最短路徑5/96解4105020103010002453160A=[[[2,10],[4,30],[5,100]], #頂點0 [[2,4]], #頂點1 [[3,50]], #頂點2 [[5,10]], #頂點3 [[3,20],[5,60]], #頂點4 []] #頂點56/96隊列式分支限界法：其中每個結點存放一個進隊的頂點編號。用dist數組存放源點s出發的最短路徑長度，dist[i]表示源點s到頂點i的最短路徑長度，初始時所有dist[i]值為∞。用prev數組存放最短路徑，prev[i]表示源點s到頂點i的最短路徑中頂點i的前驅頂點。7/96wdist[v]uvs源點dist[u]邊松馳操作dist[v]=min{dist[v]，dist[u]+w}8/960243511030100605041020⑦⑧④0dist[0]=0,其他為∞②50310+50<∞:prev[3]=2dist[3]=6030+20<60:prev[3]=4dist[3]=50③60203530+60<100:prev[5]=4dist[5]=90⑤10550+10<90:prev[5]=3dist[5]=60⑥105沒有修改，不進隊最終結果：dist[1]=∞，prev[1]=*dist[4]=30，prev[4]=0dist[2]=10，prev[2]=0dist[5]=60，prev[5]=3dist[3]=50，prev[3]=4i=00+10<∞:prev[2]=0dist[2]=10①1000+30<∞:prev[4]=0dist[4]=30102450+100<∞:prev[5]=0dist[5]=10030i=1i=2i=39/964 defbfs(s): #求解算法6 dist=[INF]*n #dist初始化所有元素為∞7 prev=[-1]*n #prev初始化所有元素為-18 dist[s]=09 qu=deque() #定義一個隊列qu10 qu.append(s) #源點結點進隊10/9611 whilequ: #隊列不空循環12 u=qu.popleft() #出隊頂點u14 foredjinA[u]:15 v,w=edj[0],edj[1] #相鄰頂點為v16 ifdist[u]+w<dist[v]: #剪支：u到v路徑長度更短17 dist[v]=dist[u]+w18 prev[v]=u19 qu.append(v) #頂點v進隊wdist[v]uvs源點dist[u]dist[v]=min{dist[v]，dist[u]+w}11/9621 defdispapath(s,i): #輸出s到i的一條最短路徑23 path=[]24 ifs==i:return25 ifdist[i]==INF:26 print("源點%d到頂點%d沒有路徑"%(s,i))27 else:28 path.append(i) #添加目標頂點29 k=prev[i]30 whilek!=s: #添加中間頂點31 path.append(k)32 k=prev[k]33 path.append(s) #添加源點34 print("源點%d到頂點%d的最短路徑長度:%d,\

路徑:"%(s,i,dist[i]),end='')35 forjinrange(len(path)-1,-1,-1): #反向輸出36 print(path[j],end='')37 print()12/9639 defsolve(A,n,s): #求源點v出發的所有最短路徑40 globalsum41 sum=042 bfs(s)43 print("求解結果")44 foriinrange(0,n):dispapath(s,i)45 print("sum=",sum)13/964105020103010002453160程序驗證14/96在圖中搜索路徑時需要解決的一個重要問題是路徑判重，即判斷路徑上是否出現重復的頂點，因為含重復頂點的路徑是沒有意義的。上述算法沒有路徑判重，通過邊松馳操作總是能夠找到源點s到其他頂點的最短路徑。不僅僅適合權為正數的圖，也適合含負權的圖，但不適合含負權回路的圖。15/96問題描述：給定一個帶權有向圖G=（V，E），其中每條邊的權是一個整數（可能是負整數）。另外給定V中的一個頂點s，稱為源點。計算從源點到其他所有其他各頂點的最短路徑及其長度。這里的路徑長度是指路上各邊權之和。6.3.3SPFA算法16/96SPFA算法也是一個求單源最短路徑的算法，全稱是ShortestPathFasterAlgorithm（SPFA），是由西南交通大學段凡丁老師1994年發明的。解17/96SPFA是6.3.2節求單源最短路徑算法的改進，6.3.2節的算法中，當出隊結點（u）時，考慮某個相鄰點v，若滿足條件dist[u]+w<dist[v]，修改dist[v]=dist[u]+w（邊松馳），如果頂點v已經在隊列中，后面會出隊v并對其所有出邊松馳的，此時再將（v）進隊就重復了，所以改為僅將不在隊列中的（v）進隊。wdist[v]uvs源點dist[u]dist[v]=min{dist[v]，dist[u]+w}18/96⑥④②50310+50<∞:prev[3]=2dist[3]=60⑤10550+10<90:prev[5]=3dist[5]=600dist[0]=0,其他為∞i=0i=1i=2i=3(3)和(5)在隊中，均不進隊41050201030100024531600+10<∞:prev[2]=0dist[2]=10①1000+30<∞:prev[4]=0dist[4]=3010250+100<∞:prev[5]=0dist[5]=10030430+20<60:prev[3]=4dist[3]=50③60203530+60<100:prev[5]=4dist[5]=9019/96布爾數組visited標記一個頂點是否在隊列中（初始時所有元素為False），頂點u進隊時置visited[u]為True，出隊時恢復visited[u]為False。1 defSPFA(s): #SPFA算法2 globalA,n,dist,prev,sum3 dist=[INF]*n#dist初始化所有元素為∞4 prev=[-1]*n#prev初始化所有元素為-15 dist[s]=06 visited=[False]*n #visited[i]表示頂點i是否在qu中7 qu=deque()

#定義一個隊列qu8 qu.append(s) #源點結點進隊9 visited[s]=True20/9610 whilequ: #隊列不空循環11 u=qu.popleft()

#出隊頂點u12 visited[u]=False14 foredjinA[u]:15 v,w=edj[0],edj[1] #u的相鄰頂點為v16 ifdist[u]+w<dist[v]:

#剪支：u到v路徑長度更短17 dist[v]=dist[u]+w18 prev[v]=u19 ifnotvisited[v]: #若頂點v不在隊中20 qu.append(v)

#頂點v進隊21 visited[v]=True21/96SPFA的時間復雜度是O(e)，但一般來說SPFA算法性能優于6.3.2節的算法。不僅僅適合權為正數的圖，也適合含負權的圖，但不適合含負權回路的圖。算法分析22/96問題描述：有n個網絡結點，標記為1到n。給定一個列表times，表示信號經過有向邊的傳遞時間，times[i]=（ui，vi，wi），其中ui是源結點，vi是目標結點，wi是一個信號從源結點傳遞到目標結點的時間?，F在從某個結點k（1≤k≤n）發出一個信號，設計一個算法求需要多久才能使所有結點都收到信號？如果不能使所有結點收到信號，返回-1

。

例如，times={{2，1，1}，{2，3，1}，{3，4，1}}，n=4，k=2，結果為2。

要求設計如下方法：

def

networkDelayTime(self,times,n,k)->int6.3.4實戰—網絡延遲時間（LeetCode743★★）23/96從結點k傳遞信號到某個結點v的時間就是從k到v的最短路徑長度，這樣該問題轉換為求單源最短路徑問題，在所有的最大連接長度中求最大值就是題目的答案。先由times建立圖的鄰接表adj（見第2章2.9.1節圖的鄰接表存儲結構），每個網絡結點對應圖中一個頂點。為了簡便，通過減1將頂點編號改為0～n-1。采用6.3.2節的隊列式分支限界法求出源點k-1到其他所有所有頂點的最短路徑長度dist數組。再在dist數組中求最大值ans，若ans=INF說明不能使所有結點收到信號，返回-1，否則返回ans。解法124/961 class

Solution:2

def

networkDelayTime(self,times,n,k)->int:3

INF=0x3f3f3f3f4

adj=[[]

for

i

in

range(n)]

#圖的鄰接表5

for

x

in

times:

#遍歷times建立鄰接表6

adj[x[0]-1].append([x[1]-1,x[2]])adj[x[0]-1]x[1]-1x[2](x[0],x[1],x[2])25/968

s=k-1

#源點為s9

dist[s]=010

qu=deque()

#定義一個隊列qu11

qu.append(s)

#源點結點進隊26/9612

while

qu:

#隊列不空循環13

u=qu.popleft()

#出隊頂點u14

for

e

in

adj[u]:15

v,w=e[0],e[1]

#相鄰頂點為v16

if

dist[u]+w<dist[v]:

#邊松馳17

dist[v]=dist[u]+w18

qu.append(v)

#頂點v進隊19

ans=max(dist)20

if

ans==INF:return

-121

else:

return

ans27/96采用SPFA算法求源點k-1到其他所有所有頂點的最短路徑長度dist數組。其他與解法1相同。解法228/961 class

Solution:2

def

networkDelayTime(self,times,n,k)->int:3

INF=0x3f3f3f3f4

adj=[[]

for

i

in

range(n)]

#圖的鄰接表5

for

x

in

times:

#遍歷times建立鄰接表6

adj[x[0]-1].append([x[1]-1,x[2]])7

dist=[INF]*n8

visited=[False]*n9

s=k-1

#源點為s10

dist[s]=011

qu=deque()

#定義一個隊列qu12

qu.append(s)

#源點結點進隊13

visited[s]=True29/9614

while

qu:

#隊列不空循環15

u=qu.popleft()

#出隊頂點u16

visited[u]=False17

for

e

in

adj[u]:18

v,w=e[0],e[1]

#相鄰頂點為v19

if

dist[u]+w<dist[v]:

#剪支20

dist[v]=dist[u]+w21

if

not

visited[v]:

#若頂點v不在隊中22

qu.append(v)

#將頂點v進隊23

visited[v]=True24

ans=max(dist)25

if

ans==INF:return

-126

else:

return

ans30/96程序提交結果均通過。解法1運行時間為92ms，解法2運行時間為72ms。消耗空間幾乎相同。從運行時間看出，SPFA算法的性能略好。比較31/96有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價值最大的方案。W=6物品編號重量w價值v0541342233116.3.50/1背包問題32/96解空間與用回溯法求解的解空間相同，根結點層次i=0，第i層表示對物品i的決策，只有選擇和不選擇兩種情況，每次二選一，葉子結點的層次是n。用x表示解向量。x[i]=0x[i]=1第i層結點選擇物品i的子結點e1不選擇物品i的子結點e2解33/96另外用bestx和bestv（初始設置為0）分別表示最優解向量和最大總價值。設計隊列結點類型如下：1 classQNode: #隊列中結點類型2 def__init__(self):3 self.i=0 #當前層次(物品序號)4 self.cw=0 #當前總重量5 self.cv=0 #當前總價值6 self.x=[] #當前解向量7 self.ub=0.0 #上界34/96限界函數：先按單位重量價值遞減排序。4 defbound(e): #求結點e的上界函數值6 rw=W-e.cw #背包的剩余容量7 b=e.cv #表示物品價值的上界值8 j=e.i9 whilej<nandg[j].w<=rw:10 rw-=g[j].w #選擇物品j11 b+=g[j].v #累計價值12 j+=113 ifj<n: #最后物品只能部分裝入14 b+=1.0*g[j].v/g[j].w*rw15 e.ub=b同回溯法求解的限界函數35/96對于第i層的結點e，求出結點e的上界函數值ub，其剪支如下：左剪支：終止選擇物品i超重的分支，也就是僅僅擴展滿足e.cw+w[i]≤W條件的子結點e1，即滿足該條件時將e1進隊。右剪支：終止在不選擇物品i時即使選擇剩余所有滿足限重的物品有不可能得到更優解的分支，也就是僅僅擴展滿足e.ub>bestv條件的子結點e2，即滿足該條件時將e2進隊。36/96W=6序號i物品編號no重量w價值vv/w02231.511341.32311130540.8(cw,cv,ub)僅擴展e.ub>bestv的右結點0,0,8105,7,82,3,6.4106,8,85,7,7.801×6,8,8103,4,6.42,3,6.2014,5,6.63,4,6.400001111111000××××××××××6,5,55,4,4××101,1,50,0,4103,4,6.60,0,52,3,80,0,6.610bestv=8結果：bestv=837/9617 defEnQueue(e,qu): #結點e進隊操作18 globaln,bestv,bestx,bestw19 ife.i==n: #到達葉子結點20 ife.cv>bestv: #比較更新最優解21 bestv=e.cv22 bestx=copy.deepcopy(e.x)23 bestw=e.cw24 else:qu.append(e) #非葉子結點進隊38/9626 defbfs(): #求0/1背包最優解的算法27 globalg,n,W,bextx,bestw,sum28 qu=deque()

#定義一個隊列29 e=QNode()30 e.i,e.cw,e.cv=0,0,0 #根結點層次為031 e.x=[-1]*n32 qu.append(e) #根結點進隊39/9633 whilequ: #隊不空循環34 e=qu.popleft() #出隊結點e36 ife.cw+g[e.i].w<=W: #左剪支37 e1=QNode()38 e1.cw=e.cw+g[e.i].w #選擇物品e.i39 e1.cv=e.cv+g[e.i].v40 e1.x=copy.deepcopy(e.x);e1.x[e.i]=141 e1.i=e.i+1 #左子結點的層次加142 EnQueue(e1,qu)43 e2=QNode()44 e2.cw,e2.cv=e.cw,e.cv #不選擇物品e.i45 e2.x=copy.deepcopy(e.x);e2.x[e.i]=046e2.i=e.i+1 #右子結點的層次加147bound(e2) #求出不選擇物品i的上界48ife2.ub>bestv: #右剪支49 EnQueue(e2,qu)40/9651 defknap(g,n,W): #求0/1背包問題52 globalbestx,bestv,bestw,sum53 g.sort() #按v/w遞減排序54 bestx=[-1]*n #存放最優解向量55 bestv=0 #存放最大價值,初始為056 bestw=0 #最優解總重量57 sum=0 #累計搜索的結點個數58 bfs() #i從0開始59 print("求解結果")60 foriinrange(0,n):61 ifbestx[i]==1:print("選取第%d個物品"%(g[i].no))62 print("總重量=%d,總價值=%d"%(bestw,bestv))63 print("sum=",sum)41/96程序驗證W=6物品編號重量w價值v05413422331142/96求解0/1背包問題的解空間是一棵高度為n+1的滿二叉樹。bound()方法的時間復雜度為O(n)。最壞時間復雜度仍然為O(n×2n)。算法分析43/96解空間與用回溯法求解的解空間相同，根結點層次i=0，第i層表示對物品i的決策，只有選擇和不選擇兩種情況，每次二選一，葉子結點的層次是n。用x表示解向量。x[i]=0x[i]=1第i層結點選擇物品i的子結點e1不選擇物品i的子結點e2解44/96另外用bestx和bestv（初始設置為0）分別表示最優解向量和最大總價值。設計隊列結點類型如下：classQNode{ //隊列中結點類型 inti; //當前層次(物品序號) intcw; //當前總重量 intcv; //當前總價值 intx[]; //當前解向量 doubleub; //上界}45/966.4.1隊列式分支限界法概述6.4優先隊列式分支限界法采用優先隊列存儲活結點，用PriorityQueue實現。根據需要設計相應的限界函數，求最大值問題設計上界函數ub，求最小值問題設計下界函數lb。不同于隊列式分支限界法中結點一層一層地出隊，優先隊列式分支限界法中結點出隊（擴展結點）是跳躍式，這樣有助于快速地找到一個解，并以此為基礎進行剪支，所以通常算法的時間性能更好。46/961 defbfs(): #優先隊列式分支限界法框架2 定義一個優先隊列pqu3 根結點進隊4 while隊pqu不空時循環:5 出隊結點e6 for擴展結點e產生結點e1:7 ife1滿足constraint()andbound():8 ife1是葉子結點:9 比較得到一個更優解或者直接返回最優解10 else:11 將結點e1進隊47/96問題描述：給定一個帶權有向圖G=（V，E），其中每條邊的權是一個正整數。另外給定V中的一個頂點s，稱為源點。計算從源點到其他所有其他各頂點的最短路徑及其長度。這里的路徑長度是指路上各邊權之和。41050201030100024531606.4.2圖的單源最短路徑48/96解4105020103010002453160A=[[[2,10],[4,30],[5,100]], #頂點0 [[2,4]], #頂點1 [[3,50]], #頂點2 [[5,10]], #頂點3 [[3,20],[5,60]], #頂點4 []] #頂點549/961 classQNode: #優先隊列結點類2 def__init__(self,i,vno,length): #構造方法3 self.i=i #結點的層次4 self.vno=vno #頂點編號5 self.length=length #路徑長度6 def__lt__(self,other): #按length越小越優先出隊7 returnself.length<other.length優先隊列式分支限界法求解。隊列結點類型聲明如下：解50/96初始化dist數組所有元素為∞，定義元素類型為QNode的優先隊列pqu。先將根結點進隊，隊不空時循環，出隊一個結點，對相應頂點的所有出邊做松馳操作，直到隊列為空，最后的dist[i]就是源點到頂點i的最短路徑長度。51/960,0頂點編號，lengthdist[i]=∞02435110301006050410200+10<∞:prev[2]=0dist[2]=102,100→24,300+30<∞:prev[4]=0dist[4]=300→45,1000+100<∞:prev[5]=0dist[5]=1000→53,6010+50<∞:prev[3]=2dist[3]=602→33,5030+20<60:prev[3]=4dist[3]=504→35,9030+60<100:prev[5]=4dist[5]=904→55,6050+10<90prev[5]=3dist[5]=603→5dist[1]=∞，prev[1]=* dist[2]=10，prev[2]=0dist[3]=50，prev[3]=4 dist[4]=30，prev[4]=0dist[5]=60，prev[5]=3求頂點0出發的最短路徑52/963 defbfs(s): #優先隊列式分支限界算法4 globalA,n,dist,prev,sum5 dist=[INF]*n #dist初始化為∞6 prev=[-1]*n #prev初始化為-17 dist[s]=08 pqu=[]

#定義一個優先隊列pqu9 heapq.heappush(pqu,QNode(0,s,0)) #源點結點進隊53/9610 whilepqu: #隊列不空循環11 e=heapq.heappop(pqu) #出隊結點e12 u=e.vno14 foredjinA[u]:15 v,w=edj[0],edj[1] #相鄰頂點為v16 ifdist[u]+w<dist[v]:

#剪支17 dist[v]=dist[u]+w18 e1=QNode(e.i+1,v,dist[v]) #建立相鄰點的結點e119 prev[v]=u20 heapq.heappush(pqu,e1) #頂點v進隊54/96上述算法中理論上所有邊都需要做一次松馳操作。最壞時間復雜度為O(e)，其中e為圖的邊數。算法分析55/96問題描述：有一個m×n的二維數組height表示地圖，height[i][j]表示(i，j)位置的高度。

設計一個算法求從左上角(0，0)走到右下角(m-1，n-1)的最小體力消耗值，每次可以往上、下、左、右

四個方向之一移動，一條路徑耗費的體力值是路徑上相鄰格子之間高度差絕對值的最大值。

要求設計如下方法：

def

minimumEffortPath(self,

heights)

->

int:6.4.3實戰—最小體力消耗路徑（LeetCode1631★★）56/96例如，heights=[[1，2，2]，[3，8，2]，[5，3，5]]，最優行走路徑如下，該路徑的高度是[1，3，5，3，5]，連續格子的差值絕對值最大為2，所以結果為2。222212238253557/96本問題不同于常規的路徑問題。地圖中位置用一個頂點表示，一條邊(x，y)→(nx，ny)，其權值為abs(heights[nx][ny]-heights[x][y])，這里的路徑長度不是路徑中所有邊的權值和，而是最大的權值。現在要求頂點(0，0)到頂點(m-1，n-1)的最小路徑長度。解222212238253558/961 class

QNode:

#優先隊列結點類2

def

__init__(self,x,y,length):

#構造方法3

self.x,self.y=x,y

#位置4

self.length=length

#路徑長度5

def

__lt__(self,other):

#length越小越優先出隊6

return

self.length<other.length59/968 class

Solution:9

def

minimumEffortPath(self,

heights)

->

int:10

INF=0x3f3f3f3f11

dx=[0,0,1,-1]

#水平方向偏移量12

dy=[1,-1,0,0]

#垂直方向偏移量13

m,n=len(heights),len(heights[0])14

dist=[[INF]*n

for

i

in

range(m)]

#dist[m][n]15

pqu=[]

#定義一個優先隊列pqu16

heapq.heappush(pqu,QNode(0,0,0))

#源點結點進隊17

dist[0][0]=060/9618

while

pqu:

#隊列不空循環19

e=heapq.heappop(pqu)

#出隊結點e20

x,y=e.x,e.y21

if

x==m-1

and

y==n-1:return

e.length

#終點返回22

for

di

in

range(0,4):23

nx,ny=x+dx[di],y+dy[di]24

if

nx<0

or

nx>=m

or

ny<0

or

ny>=n:continue25

curlen=max(e.length,abs(heights[nx][ny]-heights[x][y]))26

if

curlen<dist[nx][ny]:

#剪支：當前路徑長度更短27

dist[nx][ny]=curlen28

e1=QNode(nx,ny,curlen)

#創建子結點e129

heapq.heappush(pqu,e1)

#結點e1進隊30

return

-161/96上述程序提交結果為通過，執行用時為808ms，內存消耗為16.7MB。62/966.4.4實戰—完成所有工作的最短時間（LeetCode1723）問題描述：給你一個整數數組

jobs

，其中jobs[i]是完成第i項工作要花費的時間。將這些工作分配給k位工人。所有工作都應該分配給工人，且每項工作只能分配給一位工人。工人的工作時間是完成分配給他們的所有工作花費時間的總和。設計一套最佳的工作分配方案，使工人的最大工作時間得以最小化，返回分配方案中盡可能最小的最大工作時間。

例如，jobs={1，2，4，7，8}，k=2，結果為11，對應的一種分配方案是1號工人分配時間為1、2、8的任務（工作時間=1+2+8=11），2號工人分配時間為4、7的任務（工作時間=4+7=11），最大工作時間是11。自學63/96有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價值最大的方案。W=6物品編號重量w價值v0541342233116.4.50/1背包問題64/96采用優先隊列式分支限界法求解0/1背包問題時，按結點的限界函數值ub越大越優先出隊，所以每個結點都有ub值。解1 classQNode: #優先隊列中結點類型2 def__init__(self):3 self.i=0 #當前層次(物品序號)4 self.cw=0 #當前總重量5 self.cv=0 #當前總價值6 self.x=[] #當前解向量7 self.ub=0.0

#上界8 def__lt__(self,other): #按ub越大越優先出隊9 returnself.ub>other.ub65/96W=6序號i物品編號no重量w價值vv/w02231.511341.32311130540.8bestv=80,0,8015××0174,5,6.6×012,3,80,0,6.61015,7,82,3,6.42016,8,85,7,7.8310×6,8,840163,4,6.6×01××8019×3,4,6.401××10end66/966 defEnQueue(e,pqu): #結點e進隊操作7 globaln,bestv,bestx,bestw8 ife.i==n: #到達葉子結點9 ife.cv>bestv:

#比較更新最優解10 bestv=e.cv11 bestx=copy.deepcopy(e.x)12 bestw=e.cw13 else:heapq.heappush(pqu,e) #非葉子結點進隊67/9615 defbfs(): #優先隊列式分支限界法求0/1背包問題16 globalg,n,W,bextx,bestw,sum17 pqu=[]

#定義一個優先隊列pqu18 e=QNode()19 e.i,e.cw,e.cv=0,0,0 #根結點層次為020 e.x=[-1]*n21 bound(e)22 heapq.heappush(pqu,e) #源點結點進隊68/9623 whilepqu: #隊不空循環24 e=heapq.heappop(pqu) #出隊結點e26 ife.cw+g[e.i].w<=W:

#左剪支27 e1=QNode()28 e1.cw=e.cw+g[e.i].w #選擇物品e.i29 e1.cv=e.cv+g[e.i].v30 e1.x=copy.deepcopy(e.x);e1.x[e.i]=131 e1.i=e.i+1 #左孩子結點的層次加132 bound(e1)33 EnQueue(e1,pqu)34 e2=QNode()35 e2.cw,e2.cv=e.cw,e.cv #不選擇物品e.i36 e2.x=copy.deepcopy(e.x);e2.x[e.i]=037 e2.i=e.i+1 #右孩子結點的層次加138 bound(e2) #求出不選擇物品i的價值上界39 ife2.ub>bestv: #右剪支40 EnQueue(e2,pqu)69/9642 defknap(g,n,W): #求0/1背包問題43 globalbestx,bestv,bestw,sum44 g.sort() #按v/w遞減排序45 bestx=[-1]*n #存放最優解向量46 bestv=0 #存放最大價值,初始為047 bestw=0 #最優解總重量48 sum=0 #累計搜索的結點個數49 bfs() #i從0開始50 print("求解結果")51 foriinrange(0,n):52 ifbestx[i]==1:print("選取第%d個物品"%(g[i].no))53 print("總重量=%d,總價值=%d"%(bestw,bestv))54 print("sum=",sum)70/96無論采用隊列式分支限界法還是優先隊列式分支限界法求解0/1背包問題，最壞情況下要搜索整個解空間樹，所以最壞時間復雜度均為O(n×2n)。算法分析71/96問題描述：有n（n≥1）個任務需要分配給n個人執行，每個任務只能分配給一個人，每個人只能執行一個任務。第i個人執行第j個任務的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務0任務1任務2任務3092781643725818376946.4.6任務分配問題72/96解優先隊列結點類型：1 classQNode: #優先隊列結點類2 def__init__(self):3 self.i=0 #人員編號(層次)4 self.cost=0 #已經分配任務所需要的成本5 self.x=[] #當前解向量6 self.used=[] #used[i]為真表示任務i已經分配7 self.lb=0 #下界8 def__lt__(self,other): #按lb越小越優先出隊9 returnself.lb<other.lb73/96lb為當前結點對應分配方案的成本下界。對于第i層的某個結點e，當搜索到該結點時表示已經為人員0～i-1分配好了任務（人員i尚未分配任務），余下分配的成本下界是c數組中第i行～第n-1行各行的最小元素和minsum，顯然這樣的分配方案的最小成本為e.cost+minsum。74/96第i層第i+1層xi=jee1minsume1.lb=e1.cost+minsum求結點e的最小成本的限界函數如下（同回溯法）。1 defbound(e): #求結點e的下界值3 minsum=04 fori1inrange(e.i,n): #求c[e.i..n-1]行中最小元素和5 minc=INF6 forj1inrange(0,n):7 ifnote.used[j1]andc[i1][j1]<minc:minc=c[i1][j1]8minsum+=minc9 e.lb=e.cost+minsum人員任務0任務1任務2任務309278164372581837694例如：e.i=2人員0已分配任務1人員1已分配任務0minsum=1+4=575/96用bestx數組存放最優分配方案，bestc（初始值為∞）存放最優成本。若一個結點的lb滿足lb≥bestc則該路徑走下去不可能找到最優解，將其剪支，也就是僅僅擴展滿足lb<bestc的結點。76/96i=0，cost=0lb=10x[]={0,0,0,0}798561i=1，cost=9lb=17x[]={0,0,0,0}i=1，cost=2lb=10x[]={1,0,0,0}i=1，cost=7lb=20x[]={2,0,0,0}i=1，cost=8lb=18x[]={3,0,0,0}j=0c[0][0]=9j=1c[0][1]=2j=2c[0][2]=7j=3c[0][3]=82i=2，cost=8lb=13x[]={1,0,0,0}i=2，cost=5lb=14x[]={1,2,0,0}i=2，cost=9lb=17x[]={1,3,0,0}j=0c[1][0]=6j=2c[1][2]=3j=3c[1][3]=7103i=3，cost=9lb=13x[]={1,0,2,0}i=3，cost=16lb=25x[]={1,0,3,0}j=2c[2][2]=1j=3c[2][3]=84i=4，cost=13lb=13x[]={1,0,2,3}j=3c[3][3]=4bestc=1377/961 defEnQueue(e,pqu): #結點e進隊操作2globaln,bestx,bestc3ife.i==n: #到達葉子結點4 ife.cost<bestc: #比較更新最優解5 bestc=e.cost6 bestx=copy.deepcopy(e.x)7 else:heapq.heappush(pqu,e) #非葉子結點進隊78/969 defbfs(): #優先隊列式分支限界算法10 globalc,n,bextx,bestc,sum11 pqu=[]

#定義一個優先隊列pqu12 e=QNode()13 e.i,e.cost=0,0 #根結點層次為014 e.x=[-1]*n15 e.used=[False]*n16 bound(e)17 heapq.heappush(pqu,e) #源點結點進隊79/9618 whilepqu: #隊不空循環19 e=heapq.heappop(pqu) #出隊結點e20 sum+=121 forjinrange(0,n): #共n個任務22 ife.used[j]:continue #任務j已分配時跳過23 e1=QNode()24 e1.i=e.i+1 #子結點的層次加125 e1.cost=e.cost+c[e.i][j]26 e1.x=copy.deepcopy(e.x);e1.x[e.i]=j #人e.i分任務j27 e1.used=copy.deepcopy(e.used);e1.used[j]=True28 bound(e1) #求e1的lb29 ife1.lb<bestc: #剪支30 EnQueue(e1,pqu)80/9632 defallocate(c,n): #求解任務分配問題33 globalbestx,bestc,sum34 sum=0 #累計搜索結點個數35 bestx=[-1]*n #最優解向量36 bestc=INF #最優解的成本37 bfs()38 print("求解結果")39 forkinrange(0,n):40 print("人員%d分配任務%d"%(k,bestx[k]))41 print("總成本=%d"%(bestc))42 print("sum=",sum)81/96程序驗證人員任務0任務1任務2任務30927816437258183769482/96算法的解空間是排列樹，最壞的時間復雜度為O(n×n!)。算法分析83/96問題描述：假設有一個貨郎擔要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市，要求路徑長度最短的路徑。89736858602135875路徑1：0→1→2→3→0：28路徑2：0→1→3→2→0：29路徑3：0→2→1→3→0：26路徑4：0→2→3→1→0：23路徑5：0→3→2→1→0：59路徑6：0→3→1→2→0：596.4.7貨郎擔問題84/96解85/96僅僅求以s為起點經過圖中所有其他頂點回到起點s的最短路徑長度（TSP路徑長度）。先不考慮回邊，設置bestd數組，bestd[i]表示s經過所有其他頂點到頂點i的最短路徑長度。當bestd數組求出后，