《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述） 課件 第6章分支限界法2

6.1分支限界法概述6.2廣度優(yōu)先搜索CONTENTS提綱6.3隊(duì)列式分支限界法6.4優(yōu)先隊(duì)列式分支限界法第6章朝最優(yōu)解方向前進(jìn)—分支限界法1/966.3.1隊(duì)列式分支限界法概述6.3隊(duì)列式分支限界法在解空間中搜索解時(shí)，隊(duì)列式分支限界法與廣度優(yōu)先搜索相同，也是采用普通隊(duì)列存儲(chǔ)活結(jié)點(diǎn)。從根結(jié)點(diǎn)開(kāi)始一層一層地?cái)U(kuò)展和搜索結(jié)點(diǎn)，同時(shí)利用剪支以提高搜索性能。2/961 defbfs(): #隊(duì)列式分支限界法算法框架2 定義一個(gè)隊(duì)列qu3 根結(jié)點(diǎn)進(jìn)隊(duì)4 while隊(duì)不空時(shí)循環(huán):5 出隊(duì)結(jié)點(diǎn)e6 for擴(kuò)展結(jié)點(diǎn)e產(chǎn)生結(jié)點(diǎn)e1:7 ife1滿(mǎn)足constraint()andbound():8 ife1是葉子結(jié)點(diǎn):9 比較得到一個(gè)更優(yōu)解或者直接返回10 else:11 將結(jié)點(diǎn)e1進(jìn)隊(duì)3/96在結(jié)點(diǎn)e出隊(duì)時(shí)判斷，也就是在結(jié)點(diǎn)e擴(kuò)展出子結(jié)點(diǎn)之前對(duì)e進(jìn)行判斷。在出隊(duì)的結(jié)點(diǎn)e擴(kuò)展出子結(jié)點(diǎn)e1后再對(duì)e1進(jìn)行判斷。前者的優(yōu)點(diǎn)是算法設(shè)計(jì)簡(jiǎn)單，后者的優(yōu)點(diǎn)是節(jié)省隊(duì)列空間，因?yàn)橐话闱闆r下解空間中葉子結(jié)點(diǎn)可能非常多，而葉子結(jié)點(diǎn)是不會(huì)擴(kuò)展的，前者仍然將葉子結(jié)點(diǎn)進(jìn)隊(duì)了。判斷是否為葉子結(jié)點(diǎn)的兩種方式4/96問(wèn)題描述：給定一個(gè)帶權(quán)有向圖G=（V，E），其中每條邊的權(quán)是一個(gè)正整數(shù)。另外給定V中的一個(gè)頂點(diǎn)s，稱(chēng)為源點(diǎn)。計(jì)算從源點(diǎn)到其他所有其他各頂點(diǎn)的最短路徑及其長(zhǎng)度。這里的路徑長(zhǎng)度是指路上各邊權(quán)之和。41050201030100024531606.3.2圖的單源最短路徑5/96解4105020103010002453160A=[[[2,10],[4,30],[5,100]], #頂點(diǎn)0 [[2,4]], #頂點(diǎn)1 [[3,50]], #頂點(diǎn)2 [[5,10]], #頂點(diǎn)3 [[3,20],[5,60]], #頂點(diǎn)4 []] #頂點(diǎn)56/96隊(duì)列式分支限界法：其中每個(gè)結(jié)點(diǎn)存放一個(gè)進(jìn)隊(duì)的頂點(diǎn)編號(hào)。用dist數(shù)組存放源點(diǎn)s出發(fā)的最短路徑長(zhǎng)度，dist[i]表示源點(diǎn)s到頂點(diǎn)i的最短路徑長(zhǎng)度，初始時(shí)所有dist[i]值為∞。用prev數(shù)組存放最短路徑，prev[i]表示源點(diǎn)s到頂點(diǎn)i的最短路徑中頂點(diǎn)i的前驅(qū)頂點(diǎn)。7/96wdist[v]uvs源點(diǎn)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沒(méi)有修改，不進(jìn)隊(duì)最終結(jié)果：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() #定義一個(gè)隊(duì)列qu10 qu.append(s) #源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)10/9611 whilequ: #隊(duì)列不空循環(huán)12 u=qu.popleft() #出隊(duì)頂點(diǎn)u14 foredjinA[u]:15 v,w=edj[0],edj[1] #相鄰頂點(diǎn)為v16 ifdist[u]+w<dist[v]: #剪支：u到v路徑長(zhǎng)度更短17 dist[v]=dist[u]+w18 prev[v]=u19 qu.append(v) #頂點(diǎn)v進(jìn)隊(duì)wdist[v]uvs源點(diǎn)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("源點(diǎn)%d到頂點(diǎn)%d沒(méi)有路徑"%(s,i))27 else:28 path.append(i) #添加目標(biāo)頂點(diǎn)29 k=prev[i]30 whilek!=s: #添加中間頂點(diǎn)31 path.append(k)32 k=prev[k]33 path.append(s) #添加源點(diǎn)34 print("源點(diǎn)%d到頂點(diǎn)%d的最短路徑長(zhǎng)度:%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): #求源點(diǎn)v出發(fā)的所有最短路徑40 globalsum41 sum=042 bfs(s)43 print("求解結(jié)果")44 foriinrange(0,n):dispapath(s,i)45 print("sum=",sum)13/964105020103010002453160程序驗(yàn)證14/96在圖中搜索路徑時(shí)需要解決的一個(gè)重要問(wèn)題是路徑判重，即判斷路徑上是否出現(xiàn)重復(fù)的頂點(diǎn)，因?yàn)楹貜?fù)頂點(diǎn)的路徑是沒(méi)有意義的。上述算法沒(méi)有路徑判重，通過(guò)邊松馳操作總是能夠找到源點(diǎn)s到其他頂點(diǎn)的最短路徑。不僅僅適合權(quán)為正數(shù)的圖，也適合含負(fù)權(quán)的圖，但不適合含負(fù)權(quán)回路的圖。15/96問(wèn)題描述：給定一個(gè)帶權(quán)有向圖G=（V，E），其中每條邊的權(quán)是一個(gè)整數(shù)（可能是負(fù)整數(shù)）。另外給定V中的一個(gè)頂點(diǎn)s，稱(chēng)為源點(diǎn)。計(jì)算從源點(diǎn)到其他所有其他各頂點(diǎn)的最短路徑及其長(zhǎng)度。這里的路徑長(zhǎng)度是指路上各邊權(quán)之和。6.3.3SPFA算法16/96SPFA算法也是一個(gè)求單源最短路徑的算法，全稱(chēng)是ShortestPathFasterAlgorithm（SPFA），是由西南交通大學(xué)段凡丁老師1994年發(fā)明的。解17/96SPFA是6.3.2節(jié)求單源最短路徑算法的改進(jìn)，6.3.2節(jié)的算法中，當(dāng)出隊(duì)結(jié)點(diǎn)（u）時(shí)，考慮某個(gè)相鄰點(diǎn)v，若滿(mǎn)足條件dist[u]+w<dist[v]，修改dist[v]=dist[u]+w（邊松馳），如果頂點(diǎn)v已經(jīng)在隊(duì)列中，后面會(huì)出隊(duì)v并對(duì)其所有出邊松馳的，此時(shí)再將（v）進(jìn)隊(duì)就重復(fù)了，所以改為僅將不在隊(duì)列中的（v）進(jìn)隊(duì)。wdist[v]uvs源點(diǎn)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)在隊(duì)中，均不進(jìn)隊(duì)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布爾數(shù)組visited標(biāo)記一個(gè)頂點(diǎn)是否在隊(duì)列中（初始時(shí)所有元素為False），頂點(diǎn)u進(jìn)隊(duì)時(shí)置visited[u]為T(mén)rue，出隊(duì)時(shí)恢復(fù)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]表示頂點(diǎn)i是否在qu中7 qu=deque()

#定義一個(gè)隊(duì)列qu8 qu.append(s) #源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)9 visited[s]=True20/9610 whilequ: #隊(duì)列不空循環(huán)11 u=qu.popleft()

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

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

#頂點(diǎn)v進(jìn)隊(duì)21 visited[v]=True21/96SPFA的時(shí)間復(fù)雜度是O(e)，但一般來(lái)說(shuō)SPFA算法性能優(yōu)于6.3.2節(jié)的算法。不僅僅適合權(quán)為正數(shù)的圖，也適合含負(fù)權(quán)的圖，但不適合含負(fù)權(quán)回路的圖。算法分析22/96問(wèn)題描述：有n個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)，標(biāo)記為1到n。給定一個(gè)列表times，表示信號(hào)經(jīng)過(guò)有向邊的傳遞時(shí)間，times[i]=（ui，vi，wi），其中ui是源結(jié)點(diǎn)，vi是目標(biāo)結(jié)點(diǎn)，wi是一個(gè)信號(hào)從源結(jié)點(diǎn)傳遞到目標(biāo)結(jié)點(diǎn)的時(shí)間?，F(xiàn)在從某個(gè)結(jié)點(diǎn)k（1≤k≤n）發(fā)出一個(gè)信號(hào)，設(shè)計(jì)一個(gè)算法求需要多久才能使所有結(jié)點(diǎn)都收到信號(hào)？如果不能使所有結(jié)點(diǎn)收到信號(hào)，返回-1

。

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

要求設(shè)計(jì)如下方法：

def

networkDelayTime(self,times,n,k)->int6.3.4實(shí)戰(zhàn)—網(wǎng)絡(luò)延遲時(shí)間（LeetCode743★★）23/96從結(jié)點(diǎn)k傳遞信號(hào)到某個(gè)結(jié)點(diǎn)v的時(shí)間就是從k到v的最短路徑長(zhǎng)度，這樣該問(wèn)題轉(zhuǎn)換為求單源最短路徑問(wèn)題，在所有的最大連接長(zhǎng)度中求最大值就是題目的答案。先由times建立圖的鄰接表adj（見(jiàn)第2章2.9.1節(jié)圖的鄰接表存儲(chǔ)結(jié)構(gòu)），每個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)對(duì)應(yīng)圖中一個(gè)頂點(diǎn)。為了簡(jiǎn)便，通過(guò)減1將頂點(diǎn)編號(hào)改為0～n-1。采用6.3.2節(jié)的隊(duì)列式分支限界法求出源點(diǎn)k-1到其他所有所有頂點(diǎn)的最短路徑長(zhǎng)度dist數(shù)組。再在dist數(shù)組中求最大值ans，若ans=INF說(shuō)明不能使所有結(jié)點(diǎn)收到信號(hào)，返回-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

#源點(diǎn)為s9

dist[s]=010

qu=deque()

#定義一個(gè)隊(duì)列qu11

qu.append(s)

#源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)26/9612

while

qu:

#隊(duì)列不空循環(huán)13

u=qu.popleft()

#出隊(duì)頂點(diǎn)u14

for

e

in

adj[u]:15

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

#相鄰頂點(diǎn)為v16

if

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

#邊松馳17

dist[v]=dist[u]+w18

qu.append(v)

#頂點(diǎn)v進(jìn)隊(duì)19

ans=max(dist)20

if

ans==INF:return

-121

else:

return

ans27/96采用SPFA算法求源點(diǎn)k-1到其他所有所有頂點(diǎn)的最短路徑長(zhǎng)度dist數(shù)組。其他與解法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

#源點(diǎn)為s10

dist[s]=011

qu=deque()

#定義一個(gè)隊(duì)列qu12

qu.append(s)

#源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)13

visited[s]=True29/9614

while

qu:

#隊(duì)列不空循環(huán)15

u=qu.popleft()

#出隊(duì)頂點(diǎn)u16

visited[u]=False17

for

e

in

adj[u]:18

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

#相鄰頂點(diǎn)為v19

if

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

#剪支20

dist[v]=dist[u]+w21

if

not

visited[v]:

#若頂點(diǎn)v不在隊(duì)中22

qu.append(v)

#將頂點(diǎn)v進(jìn)隊(duì)23

visited[v]=True24

ans=max(dist)25

if

ans==INF:return

-126

else:

return

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

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

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

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

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

四個(gè)方向之一移動(dòng)，一條路徑耗費(fèi)的體力值是路徑上相鄰格子之間高度差絕對(duì)值的最大值。

要求設(shè)計(jì)如下方法：

def

minimumEffortPath(self,

heights)

->

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

QNode:

#優(yōu)先隊(duì)列結(jié)點(diǎn)類(lèi)2

def

__init__(self,x,y,length):

#構(gòu)造方法3

self.x,self.y=x,y

#位置4

self.length=length

#路徑長(zhǎng)度5

def

__lt__(self,other):

#length越小越優(yōu)先出隊(duì)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=[]

#定義一個(gè)優(yōu)先隊(duì)列pqu16

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

#源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)17

dist[0][0]=060/9618

while

pqu:

#隊(duì)列不空循環(huán)19

e=heapq.heappop(pqu)

#出隊(duì)結(jié)點(diǎn)e20

x,y=e.x,e.y21

if

x==m-1

and

y==n-1:return

e.length

#終點(diǎn)返回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]:

#剪支：當(dāng)前路徑長(zhǎng)度更短27

dist[nx][ny]=curlen28

e1=QNode(nx,ny,curlen)

#創(chuàng)建子結(jié)點(diǎn)e129

heapq.heappush(pqu,e1)

#結(jié)點(diǎn)e1進(jìn)隊(duì)30

return

-161/96上述程序提交結(jié)果為通過(guò)，執(zhí)行用時(shí)為808ms，內(nèi)存消耗為16.7MB。62/966.4.4實(shí)戰(zhàn)—完成所有工作的最短時(shí)間（LeetCode1723）問(wèn)題描述：給你一個(gè)整數(shù)數(shù)組

jobs

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

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

#上界8 def__lt__(self,other): #按ub越大越優(yōu)先出隊(duì)9 returnself.ub>other.ub65/96W=6序號(hào)i物品編號(hào)no重量w價(jià)值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): #結(jié)點(diǎn)e進(jìn)隊(duì)操作7 globaln,bestv,bestx,bestw8 ife.i==n: #到達(dá)葉子結(jié)點(diǎn)9 ife.cv>bestv:

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

#定義一個(gè)優(yōu)先隊(duì)列pqu18 e=QNode()19 e.i,e.cw,e.cv=0,0,0 #根結(jié)點(diǎn)層次為020 e.x=[-1]*n21 bound(e)22 heapq.heappush(pqu,e) #源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)68/9623 whilepqu: #隊(duì)不空循環(huán)24 e=heapq.heappop(pqu) #出隊(duì)結(jié)點(diǎn)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 #左孩子結(jié)點(diǎn)的層次加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 #右孩子結(jié)點(diǎn)的層次加138 bound(e2) #求出不選擇物品i的價(jià)值上界39 ife2.ub>bestv: #右剪支40 EnQueue(e2,pqu)69/9642 defknap(g,n,W): #求0/1背包問(wèn)題43 globalbestx,bestv,bestw,sum44 g.sort() #按v/w遞減排序45 bestx=[-1]*n #存放最優(yōu)解向量46 bestv=0 #存放最大價(jià)值,初始為047 bestw=0 #最優(yōu)解總重量48 sum=0 #累計(jì)搜索的結(jié)點(diǎn)個(gè)數(shù)49 bfs() #i從0開(kāi)始50 print("求解結(jié)果")51 foriinrange(0,n):52 ifbestx[i]==1:print("選取第%d個(gè)物品"%(g[i].no))53 print("總重量=%d,總價(jià)值=%d"%(bestw,bestv))54 print("sum=",sum)70/96無(wú)論采用隊(duì)列式分支限界法還是優(yōu)先隊(duì)列式分支限界法求解0/1背包問(wèn)題，最壞情況下要搜索整個(gè)解空間樹(shù)，所以最壞時(shí)間復(fù)雜度均為O(n×2n)。算法分析71/96問(wèn)題描述：有n（n≥1）個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)任務(wù)只能分配給一個(gè)人，每個(gè)人只能執(zhí)行一個(gè)任務(wù)。第i個(gè)人執(zhí)行第j個(gè)任務(wù)的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務(wù)0任務(wù)1任務(wù)2任務(wù)3092781643725818376946.4.6任務(wù)分配問(wèn)題72/96解優(yōu)先隊(duì)列結(jié)點(diǎn)類(lèi)型：1 classQNode: #優(yōu)先隊(duì)列結(jié)點(diǎn)類(lèi)2 def__init__(self):3 self.i=0 #人員編號(hào)(層次)4 self.cost=0 #已經(jīng)分配任務(wù)所需要的成本5 self.x=[] #當(dāng)前解向量6 self.used=[] #used[i]為真表示任務(wù)i已經(jīng)分配7 self.lb=0 #下界8 def__lt__(self,other): #按lb越小越優(yōu)先出隊(duì)9 returnself.lb<other.lb73/96lb為當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)分配方案的成本下界。對(duì)于第i層的某個(gè)結(jié)點(diǎn)e，當(dāng)搜索到該結(jié)點(diǎn)時(shí)表示已經(jīng)為人員0～i-1分配好了任務(wù)（人員i尚未分配任務(wù)），余下分配的成本下界是c數(shù)組中第i行～第n-1行各行的最小元素和minsum，顯然這樣的分配方案的最小成本為e.cost+minsum。74/96第i層第i+1層xi=jee1minsume1.lb=e1.cost+minsum求結(jié)點(diǎn)e的最小成本的限界函數(shù)如下（同回溯法）。1 defbound(e): #求結(jié)點(diǎn)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人員任務(wù)0任務(wù)1任務(wù)2任務(wù)309278164372581837694例如：e.i=2人員0已分配任務(wù)1人員1已分配任務(wù)0minsum=1+4=575/96用bestx數(shù)組存放最優(yōu)分配方案，bestc（初始值為∞）存放最優(yōu)成本。若一個(gè)結(jié)點(diǎn)的lb滿(mǎn)足lb≥bestc則該路徑走下去不可能找到最優(yōu)解，將其剪支，也就是僅僅擴(kuò)展?jié)M足lb<bestc的結(jié)點(diǎn)。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): #結(jié)點(diǎn)e進(jìn)隊(duì)操作2globaln,bestx,bestc3ife.i==n: #到達(dá)葉子結(jié)點(diǎn)4 ife.cost<bestc: #比較更新最優(yōu)解5 bestc=e.cost6 bestx=copy.deepcopy(e.x)7 else:heapq.heappush(pqu,e) #非葉子結(jié)點(diǎn)進(jìn)隊(duì)78/969 defbfs(): #優(yōu)先隊(duì)列式分支限界算法10 globalc,n,bextx,bestc,sum11 pqu=[]

#定義一個(gè)優(yōu)先隊(duì)列pqu12 e=QNode()13 e.i,e.cost=0,0 #根結(jié)點(diǎn)層次為014 e.x=[-1]*n15 e.used=[False]*n16 bound(e)17 heapq.heappush(pqu,e) #源點(diǎn)結(jié)點(diǎn)進(jìn)隊(duì)79/9618 whilepqu: #隊(duì)不空循環(huán)19 e=heapq.heappop(pqu) #出隊(duì)結(jié)點(diǎn)e20 sum+=121 forjinrange(0,n): #共n個(gè)任務(wù)22 ife.used[j]:continue #任務(wù)j已分配時(shí)跳過(guò)23 e1=QNode()24 e1.i=e.i+1 #子結(jié)點(diǎn)的層次加125 e1.cost=e.cost+c[e.i][j]26 e1.x=copy.deepcopy(e.x);e1.x[e.i]=j #人e.i分任務(wù)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): #求解任務(wù)分配問(wèn)題33 globalbestx,bestc,sum34 sum=0 #累計(jì)搜索結(jié)點(diǎn)個(gè)數(shù)35 bestx=[-1]*n #最優(yōu)解向量36 bestc=INF #最優(yōu)解的成本37 bfs()38 print("求解結(jié)果")39 forkinrange(0,n):40 print("人員%d分配任務(wù)%d"%(k,bestx[k]))41 print("總成本=%d"%(bestc))42 print("sum=",sum)81/96程序驗(yàn)證人員任務(wù)0任務(wù)1任務(wù)2任務(wù)30927816437258183769482/96算法的解空間是排列樹(shù)，最壞的時(shí)間復(fù)雜度為O(n×n!)。算法分析83/96問(wèn)題描述：假設(shè)有一個(gè)貨郎擔(dān)要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市，要求路徑長(zhǎng)度最短的路徑。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貨郎擔(dān)問(wèn)題84/96解85/96僅僅求以s為起點(diǎn)經(jīng)過(guò)圖中所有其他頂點(diǎn)回到起點(diǎn)s的最短路徑長(zhǎng)度（TSP路徑長(zhǎng)度）。先不考慮回邊，設(shè)置bestd數(shù)組，bestd[i]表示s經(jīng)過(guò)所有其他頂點(diǎn)到頂點(diǎn)i的最短路徑長(zhǎng)度。當(dāng)bestd數(shù)組求出后，