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

第6章朝最優(yōu)解方向前進—分支限界法6.1分支限界法概述6.2廣度優(yōu)先搜索CONTENTS提綱6.3隊列式分支限界法6.4優(yōu)先隊列式分支限界法1/37分支限界法=廣度優(yōu)先搜索+剪支。6.1.1什么是分支限界法6.1分支限界法概述算法解空間搜索方式存儲結(jié)點的數(shù)據(jù)結(jié)構(gòu)結(jié)點存儲特性常用應(yīng)用回溯法深度優(yōu)先棧只保存從根結(jié)點到當前擴展結(jié)點的路徑找出滿足約束條件的所有解分支限界法廣度優(yōu)先隊列，優(yōu)先隊列每個結(jié)點只有一次成為活結(jié)點的機會找出一個解或最優(yōu)解2/37求迷宮問題的所有解：應(yīng)該采用回溯法，不適合采用分支限界法。求迷宮問題的一條最短路徑：屬于最優(yōu)解問題，適合采用分支限界法。說明3/376.1.2分支限界法設(shè)計要點1.設(shè)計合適的限界函數(shù)活結(jié)點si1si2si4si3活結(jié)點si2si3sisi為什么分支限界法比回溯法設(shè)計限界函數(shù)更重要？4/37設(shè)計上界限界函數(shù)ub()，若從xi的分支向下搜索所得到的部分解是（x0，x1，…，xi，…，xk），則應(yīng)該滿足： ub(xi)≥ub(xi+1)≥…≥ub(xk)所以根結(jié)點的ub值應(yīng)該大于或等于最優(yōu)解的ub值。如果從si結(jié)點擴展到sj結(jié)點，應(yīng)滿足ub(si)≥ub(sj)，將所有小于ub(si)的結(jié)點剪支。限界函數(shù)的特性假設(shè)解向量x=（x0，x1，…，xn-1），如果目標函數(shù)是求最大值x0x1xn-1ub5/37設(shè)計下界限界函數(shù)lb()，若從xi的分支向下搜索所得到的部分解是（x0，x1，…，xi，…，xk），則應(yīng)該滿足：lb(xi)≤lb(xi+1)≤…≤lb(xk)所以根結(jié)點的bb值應(yīng)該小于或等于最優(yōu)解的lb值。如果從si結(jié)點擴展到sj結(jié)點，應(yīng)滿足lb(si)≤lb(sj)，將所有大于lb(si)的結(jié)點剪支。假設(shè)解向量x=（x0，x1，…，xn-1），如果目標函數(shù)是求最小值x0x1xn-1lb6/372.組織活結(jié)點表1）隊列式分支限界法活結(jié)點表組織成一個隊列，并按照隊列先進先出原則選取下一個結(jié)點為擴展結(jié)點。與廣度優(yōu)先搜索相同。隊列通常采用deque實現(xiàn)。2）優(yōu)先隊列式分支限界法活結(jié)點表組組成一個優(yōu)先隊列，并選取優(yōu)先級最高的活結(jié)點成為當前擴展結(jié)點（跳躍式擴展）。優(yōu)先隊列通常采用heapq實現(xiàn)。7/373.求最優(yōu)解的解向量①對每個擴展結(jié)點保存從根結(jié)點到該結(jié)點的路徑（解向量）。

1101010101:狀態(tài)值解向量:[0,0,0]2:狀態(tài)值解向量:[1,0,0]4:狀態(tài)值解向量:[1,1,0]5:狀態(tài)值解向量:[1,0,0]8:狀態(tài)值解向量:[1,0,1]9:狀態(tài)值解向量:[1,0,0]6:狀態(tài)值解向量:[0,1,0]10:狀態(tài)值解向量:[0,1,1]11:狀態(tài)值解向量:[0,1,0]7:狀態(tài)值解向量:[0,0,0]3:狀態(tài)值解向量:[0,0,0]0答案：0118/37②在每個結(jié)點中保存搜索路徑中的前驅(qū)結(jié)點，反推搜索路徑（解向量）。1010101011:狀態(tài)值雙親指針:02:狀態(tài)值雙親指針:14:狀態(tài)值雙親指針:25:狀態(tài)值雙親指針:28:狀態(tài)值雙親指針:59:狀態(tài)值雙親指針:56:狀態(tài)值雙親指針:310:狀態(tài)值雙親指針:611:狀態(tài)值雙親指針:67:狀態(tài)值雙親指針:33:狀態(tài)值雙親指針:10答案：0119/376.1.3分支限界法的時間分析解空間樹共有n+1層（根結(jié)點為第0層，葉子結(jié)點為第n層）。第1層有m0個結(jié)點，每個結(jié)點有m1個子結(jié)點。第2層有m0m1個結(jié)點，同理，第3層有m0m1m2個結(jié)點，依此類推，第n層有m0m1…mn-1個結(jié)點。則采用分支限界法求所有解的算法的執(zhí)行時間為

T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。例如，在子集樹中有m0=m1=…=mn-1=c，對應(yīng)算法的時間復(fù)雜度為O(cn)，在排列樹中有m0=n，m1=n-1，…，mn-1=1，對應(yīng)算法的時間復(fù)雜度為O(n!)。10/376.2廣度優(yōu)先搜索廣度優(yōu)先搜索是在訪問一個頂點v之后橫向搜索v的所有相鄰點.在解空間中搜索時類似樹的層次遍歷方式。11/376.2.1圖的廣度優(yōu)先遍歷采用廣度優(yōu)先搜索方法遍歷圖稱為圖的廣度優(yōu)先遍歷，其過程是從起始點v出發(fā)，以橫向方式一步一步沿著邊訪問各個頂點，得到遍歷序列稱為廣度優(yōu)先遍歷序列。廣度優(yōu)先遍歷采用隊列存儲活結(jié)點，先進隊的結(jié)點先擴展。同樣廣度優(yōu)先遍歷特指圖的一種遍歷方式，而廣度優(yōu)先搜索是一種通用的搜索方式，前者是后者的一種應(yīng)用。12/376.2.2廣度優(yōu)先搜索算法框架廣度優(yōu)先搜索基本廣度優(yōu)先搜索分層次廣度優(yōu)先搜索多起點廣度優(yōu)先搜索13/371.基本廣度優(yōu)先搜索假設(shè)起始搜索點為s，目標點為t，從s出發(fā)找t。1 defbfs(): #基本廣度優(yōu)先搜索算法框架2 定義隊列qu和訪問標記數(shù)組3 置起始點s已經(jīng)訪問4 起始點s進入隊列qu5 while隊列qu不空:6 出隊結(jié)點e7 ife==t:return #第一次遇到t便返回8 for從e擴展出e1:9 置e1已經(jīng)訪問10 將結(jié)點e1進入隊列qu14/37利用其特性快速找最優(yōu)解。廣度優(yōu)先搜索算法的主要應(yīng)用15/37在解空間中搜索時需要擴展結(jié)點。如果每次擴展的代價都計為相同的p，則第一次找到目標點的代價就一定是最小代價。如果每次擴展的代價不同，則第一次找到目標點的代價就不一定是最小代價。任何情況下利用廣度優(yōu)先搜索都可以找到最優(yōu)解？16/372.分層次廣度優(yōu)先搜索求不帶權(quán)圖中s到t的最短路徑長度。1 defbfs(): #分層次的廣度優(yōu)先搜索算法框架2 定義隊列qu和訪問標記數(shù)組3 置起始點s已經(jīng)訪問4 起始點s進入隊列qu5 ans=0

#表示最短路徑長度6 while隊列qu不空: #外循環(huán)的次數(shù)是s到t的層次數(shù)7 cnt=len(qu) #當前層的結(jié)點個數(shù)為cnt8 foriinrange(0,cnt): #循環(huán)cnt次擴展每個結(jié)點9 出隊結(jié)點e10 ife==t:returnans #找到目標點返回ans11 for從e擴展出e1:12 置e1已經(jīng)訪問13 將結(jié)點e1進入隊列qu14 ans+=115 return-1 #表示沒有找到t17/373.多起點廣度優(yōu)先搜索求不帶權(quán)圖中多個頂點（用頂點集合S表示）到t的最短路徑長度。1 intbfs(): #多起點的廣度優(yōu)先搜索算法框架2 定義隊列qu和訪問標記數(shù)組3 置S中所有的起始點已經(jīng)訪問4 將S中所有的起始點進入隊列qu5 ans=1

#表示最短路徑長度6 while隊列qu不空: #外循環(huán)的次數(shù)就是s到t的層次數(shù)7 cnt=len(qu)

#當前層的結(jié)點個數(shù)為cnt8 foriinrange(0,cnt)：

#循環(huán)cnt次擴展每個結(jié)點9 出隊結(jié)點e10 ife==t:returnans #找到目標點返回ans11 for從e擴展出e1:12 置e1已經(jīng)訪問13 將結(jié)點e1進入隊列qu14 ans+=115 return-1 #表示沒有找到t18/37問題描述：有一只跳蚤的家在數(shù)軸上的位置x處，請你幫助它從位置0出發(fā)到達它的家。跳蚤跳躍的規(guī)則如下：

（1）跳蚤可以往前跳恰好a個位置（即往右跳）。

（2）跳蚤可以往后跳恰好b個位置（即往左跳）。

（3）跳蚤不能連續(xù)往后跳2次。

（4）跳蚤不能跳到任何forbidden數(shù)組中的位置。

（5）跳蚤可以往前跳超過它的家的位置，但是它不能跳到負整數(shù)的位置。

給定一個整數(shù)數(shù)組forbidden，其中forbidden[i]是跳蚤不能跳到的位置，同時給定整數(shù)a，b和x，設(shè)計一個算法求跳蚤到家的最少跳躍次數(shù)，如果沒有恰好到達x的可行方案，則返回-1。

例如，forbidden={14，4，18，1，15}，a=3，b=15，x=9，結(jié)果為3，對應(yīng)的跳蚤跳躍路徑是0->3->6->9。6.2.3實戰(zhàn)—到家的最少跳躍次數(shù)（LeetCode1654★★）19/37解跳蚤從位置0出發(fā)跳到位置x，只有向前和向后兩種跳躍方式，無論哪種方式都計一次，求的是最小跳躍次數(shù)，滿足廣搜特性，采用分層次廣度優(yōu)先遍歷求最優(yōu)解。x的最大值為2000，每次跳躍不超過2000，又規(guī)定不能連續(xù)往后跳2次，所以最大的跳躍位置不可能超過6000，設(shè)置MAXX=6000。由于跳蚤不能連續(xù)往后跳2次，需要記錄當前向后跳躍的次數(shù)，因此當前狀態(tài)表示為（當前位置，向后跳躍次數(shù)），訪問標記數(shù)組設(shè)計為二維數(shù)組visited[MAXX+1][2]。forbidden數(shù)組表示不能跳到的位置，初始時將forbidden中所有位置的visited元素置為true。20/371 class

QNode:

#隊列結(jié)點類2

def

__init__(self,x,y): #構(gòu)造方法3

self.p=x

#當前位置4

self.bstep=y

#從當前位置向后跳次數(shù)21/376 class

Solution:7

def

minimumJumps(self,

forbidden,a,b,x)

->

int:8

MAXX=60009

visited=[[False]*2

for

i

in

range(0,MAXX+1)]10

for

e

in

forbidden: #forbidden中所有位置為不可訪問的11

visited[e][0]=visited[e][1]=True

12

qu=deque()

#用雙端隊列作為隊列qu13

qu.append(QNode(0,0))

#起始點進隊14

visited[0][0]=True

#置已訪問標記15

ans=0

#最少跳躍次數(shù)22/3716

while

qu: #隊不空時循環(huán)17

cnt=len(qu)

#隊列中元素個數(shù)為cnt18

for

i

in

range(0,cnt):19

e=qu.popleft()

#出隊結(jié)點e20

curx,bstep=e.p,e.bstep21

if

curx==x:return

ans

#遇到x返回ans22

e1=QNode(curx+a,0)

#向前跳躍一次23

if

e1.p<=MAXX

and

not

visited[e1.p][e1.bstep]:24

visited[e1.p][e1.bstep]=True25

qu.append(e1)

#結(jié)點e1進隊26

e2=QNode(curx-b,bstep+1)

#向后跳躍一次27 if

e2.p>=0

and

e2.bstep<2

and

not

visited[e2.p][e2.bstep]:28

visited[e2.p][e2.bstep]=True29

qu.append(e2)

#結(jié)點e2進隊30

ans+=1

#跳躍次數(shù)增131

return

-1

#不能跳到x返回-123/37上述程序提交結(jié)果為通過，執(zhí)行用時為188ms，內(nèi)存消耗為15.7MB。24/37問題描述：有一個2×3的面板board，其中放置有5個物品，用數(shù)字1~5來表示，另外一個空位置用0表示。一次移動定義為0與一個上下左右的相鄰數(shù)字進行交換，面板的目標狀態(tài)是{{1，2，3}，{4，5，0}}。設(shè)計一個算法求由給定的面板初始狀態(tài)到目標狀態(tài)的最少移動次數(shù)，如果不能到達目標狀態(tài)則返回-1。

例如，board={{1，2，3}，{4，0，5}}，結(jié)果為1，只需要交換0和5即可。

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

def

slidingPuzzle(self,

board)

->

int6.2.4實戰(zhàn)—滑動謎題（LeetCode773★★★）25/37解顯然本問題滿足廣搜特性，采用分層次廣度優(yōu)先遍歷求最優(yōu)解（最少移動次數(shù)）。本問題中狀態(tài)是由board確定的，僅僅考慮0的位置是不夠的，因為0的位置相同其他數(shù)字的順序不同時構(gòu)成不同的狀態(tài)。在搜索過程不能訪問之前出現(xiàn)的重復(fù)狀態(tài)。由于這里board不是單個整數(shù)，判斷重復(fù)比較麻煩，為此將board轉(zhuǎn)換為一個字符串。例如board={{1，2，3}，{4，0，5}}轉(zhuǎn)換為“123405”，如下圖3所示，這樣目標狀態(tài)t="123450"。123405102132430455"123405"26/37為了實現(xiàn)移動操作（

0

與一個上下左右相鄰數(shù)字交換），將位置映射關(guān)系采用位置鄰接表表示，如下圖所示，例如位置4為0，只能與位置1、3或者5的數(shù)字進行交換。對應(yīng)的位置鄰接表如下：

adj=[[1,3],[0,4,2],[1,5],[0,4],[1,3,5],[2,4]]01234501,310,2,421,530,441,3,552,4采用集合set對象visited存放已訪問的狀態(tài)，其查找時間接近O(1)，與數(shù)組按下標查找的性能差不多。27/371 class

Solution:2

def

slidingPuzzle(self,

board:

List[List[int]])

->

int:3

m,n=2,34

t="123450"5

s=""6

for

i

in

range(0,m):

#將board轉(zhuǎn)換為一個字符串7

for

j

in

range(0,n):8

s+=str(board[i][j])9

adj=[[1,3],[0,4,2],[1,5],[0,4],[1,3,5],[2,4]]10

qu=deque()

#定義一個隊列11

visited=set()

#狀態(tài)訪問標記12

qu.append(s)

#初始狀態(tài)s進隊13

visited.add(s)14

ans=0

#最少移動次數(shù)28/3715

while

qu:16

cnt=len(qu)

#隊不空時循環(huán)17

for

k

in

range(0,cnt):18

curs=qu.popleft()

#出隊curs19

if

curs==t:return

ans

#找到目標返回ans20

i=curs.index('0')

#查找'0'的位置i21

for

j

in

adj[i]:

#找位置i的相鄰位置j22

nboard=self.swap(curs,i,j)

#擴展23

if

nboard

not

in

visited:

#nboard未訪問過24

qu.append(nboard)

#nboard狀態(tài)進隊25

visited.add(nboard)

#置已訪問標記26

ans+=127

return

-129/3729

def

swap(self,s,i,j):

#返回s[i]與s[j]交換的結(jié)果30

a=list(s)

#將s轉(zhuǎn)換為列表a31

a[i],a[j]=a[j],a[i]

32

return

''.join(a)

#連接為新字符串后返回上述程序提交結(jié)果為通過，執(zhí)行用時為44ms，內(nèi)存消耗為15.1MB。123405123045"123405",i=4"123045",j=3交換30/37問題描述：給定一個類似迷宮的網(wǎng)格grid，值0代表空單元格，值1代表新鮮橘子，值2代表腐爛的橘子。每分鐘任何與腐爛的橘子相鄰（4個方位）的新鮮橘子都會腐爛，求沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。如果不可能，返回-1。

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

orangesRotting(self,

grid)

->

int6.2.5實戰(zhàn)—腐爛的橘子（LeetCode994）31/37分鐘0分鐘1分鐘2分鐘3分鐘432/37返回4解采用多起點+分層的廣度優(yōu)先遍歷的方法。用ans表示經(jīng)過的最小分鐘數(shù)（初始為0）。先將所有腐爛橘子進隊（可能有多個腐爛橘子），然后一層一層地搜索相鄰新鮮橘子，當有相鄰新鮮橘子時就將其變?yōu)楦癄€橘子，此時置ans++（表示腐爛一次相鄰橘子花費一分鐘），并且將這些新腐爛橘子進隊。在這樣做完即隊列為空時再判斷圖中是否存在新鮮橘子，若還存在新鮮橘子，則返回-1表示不可能腐爛所有橘子，否則返回ans表示最少ans分鐘就可以腐爛所有橘子。33/371 class

QNode:

#隊列結(jié)點類2

def

__init__(self,x,y):

#構(gòu)造方法3

self.x,self.y=x,y

#當前位置(x,y)34/375 class

Solution:6

def

orangesRotting(self,

grid:

List[List[int]])

->

int:7

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

#水平方向偏移量8

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

#垂直方向偏移量9

m,n=len(grid),len(grid[0])

#行列數(shù)10

qu=deque()

#定義一個隊列qu11

for

i

in

range(0,m):12

for

j

in

range(0,n):13

if

grid[i][j]==2: qu.append(QNode(i,j)) #所有腐爛的橘子進隊14

ans=0

#經(jīng)過的最小分鐘數(shù)35/3715

while

qu:

#隊不空循環(huán)16

flag=False17

cnt=len(qu) #求隊列中元素個數(shù)cnt18

for

i

in

range(0,cnt):

#循環(huán)cnt次處理該層所有結(jié)點19

e=qu.popleft()

#出隊結(jié)點e20

for

di

in

range(0,4):

#四周搜索21

nx,ny=e.x+dx[di],e.y+dy[di]22

if

nx>=0

and

nx<m

and

ny>=0

and

ny<n

and

grid[nx][ny]==1:23

grid[nx][ny]=2

#新鮮橘子變?yōu)楦癄€橘子24

qu.append(QNode(nx,ny))

#腐爛橘子進隊25

flag=True

#表示有新鮮橘子變?yōu)楦癄€橘子26

if

flag:

ans+=1

#有新鮮橘子變?yōu)楦癄€時ans增136/3727

for

i

in

range(0,m):

#判斷是否還存在新鮮橘子28

for

j

in

range(0,n):29

if

grid[i][j]==1: return

-1

#還存在新鮮橘子,返回-130

return

ans上述程序提交結(jié)果為通過，執(zhí)行用時為48ms，內(nèi)存消耗為15MB。37/376.1分支限界法概述6.2廣度優(yōu)先搜索CONTENTS提綱6.3隊列式分支限界法6.4優(yōu)先隊列式分支限界法第6章朝最優(yōu)解方向前進—分支限界法38/966.3.1隊列式分支限界法概述6.3隊列式分支限界法在解空間中搜索解時，隊列式分支限界法與廣度優(yōu)先搜索相同，也是采用普通隊列存儲活結(jié)點。從根結(jié)點開始一層一層地擴展和搜索結(jié)點，同時利用剪支以提高搜索性能。39/961 defbfs(): #隊列式分支限界法算法框架2 定義一個隊列qu3 根結(jié)點進隊4 while隊不空時循環(huán):5 出隊結(jié)點e6 for擴展結(jié)點e產(chǎn)生結(jié)點e1:7 ife1滿足constraint()andbound():8 ife1是葉子結(jié)點:9 比較得到一個更優(yōu)解或者直接返回10 else:11 將結(jié)點e1進隊40/96在結(jié)點e出隊時判斷，也就是在結(jié)點e擴展出子結(jié)點之前對e進行判斷。在出隊的結(jié)點e擴展出子結(jié)點e1后再對e1進行判斷。前者的優(yōu)點是算法設(shè)計簡單，后者的優(yōu)點是節(jié)省隊列空間，因為一般情況下解空間中葉子結(jié)點可能非常多，而葉子結(jié)點是不會擴展的，前者仍然將葉子結(jié)點進隊了。判斷是否為葉子結(jié)點的兩種方式41/96問題描述：給定一個帶權(quán)有向圖G=（V，E），其中每條邊的權(quán)是一個正整數(shù)。另外給定V中的一個頂點s，稱為源點。計算從源點到其他所有其他各頂點的最短路徑及其長度。這里的路徑長度是指路上各邊權(quán)之和。41050201030100024531606.3.2圖的單源最短路徑42/96解4105020103010002453160A=[[[2,10],[4,30],[5,100]], #頂點0 [[2,4]], #頂點1 [[3,50]], #頂點2 [[5,10]], #頂點3 [[3,20],[5,60]], #頂點4 []] #頂點543/96隊列式分支限界法：其中每個結(jié)點存放一個進隊的頂點編號。用dist數(shù)組存放源點s出發(fā)的最短路徑長度，dist[i]表示源點s到頂點i的最短路徑長度，初始時所有dist[i]值為∞。用prev數(shù)組存放最短路徑，prev[i]表示源點s到頂點i的最短路徑中頂點i的前驅(qū)頂點。44/96wdist[v]uvs源點dist[u]邊松馳操作dist[v]=min{dist[v]，dist[u]+w}45/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沒有修改，不進隊最終結(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=346/964 defbfs(s): #求解算法6 dist=[INF]*n #dist初始化所有元素為∞7 prev=[-1]*n #prev初始化所有元素為-18 dist[s]=09 qu=deque() #定義一個隊列qu10 qu.append(s) #源點結(jié)點進隊47/9611 whilequ: #隊列不空循環(huán)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}48/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()49/9639 defsolve(A,n,s): #求源點v出發(fā)的所有最短路徑40 globalsum41 sum=042 bfs(s)43 print("求解結(jié)果")44 foriinrange(0,n):dispapath(s,i)45 print("sum=",sum)50/964105020103010002453160程序驗證51/96在圖中搜索路徑時需要解決的一個重要問題是路徑判重，即判斷路徑上是否出現(xiàn)重復(fù)的頂點，因為含重復(fù)頂點的路徑是沒有意義的。上述算法沒有路徑判重，通過邊松馳操作總是能夠找到源點s到其他頂點的最短路徑。不僅僅適合權(quán)為正數(shù)的圖，也適合含負權(quán)的圖，但不適合含負權(quán)回路的圖。52/96問題描述：給定一個帶權(quán)有向圖G=（V，E），其中每條邊的權(quán)是一個整數(shù)（可能是負整數(shù)）。另外給定V中的一個頂點s，稱為源點。計算從源點到其他所有其他各頂點的最短路徑及其長度。這里的路徑長度是指路上各邊權(quán)之和。6.3.3SPFA算法53/96SPFA算法也是一個求單源最短路徑的算法，全稱是ShortestPathFasterAlgorithm（SPFA），是由西南交通大學(xué)段凡丁老師1994年發(fā)明的。解54/96SPFA是6.3.2節(jié)求單源最短路徑算法的改進，6.3.2節(jié)的算法中，當出隊結(jié)點（u）時，考慮某個相鄰點v，若滿足條件dist[u]+w<dist[v]，修改dist[v]=dist[u]+w（邊松馳），如果頂點v已經(jīng)在隊列中，后面會出隊v并對其所有出邊松馳的，此時再將（v）進隊就重復(fù)了，所以改為僅將不在隊列中的（v）進隊。wdist[v]uvs源點dist[u]dist[v]=min{dist[v]，dist[u]+w}55/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]=9056/96布爾數(shù)組visited標記一個頂點是否在隊列中（初始時所有元素為False），頂點u進隊時置visited[u]為True，出隊時恢復(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]表示頂點i是否在qu中7 qu=deque()

#定義一個隊列qu8 qu.append(s) #源點結(jié)點進隊9 visited[s]=True57/9610 whilequ: #隊列不空循環(huán)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]=True58/96SPFA的時間復(fù)雜度是O(e)，但一般來說SPFA算法性能優(yōu)于6.3.2節(jié)的算法。不僅僅適合權(quán)為正數(shù)的圖，也適合含負權(quán)的圖，但不適合含負權(quán)回路的圖。算法分析59/96問題描述：有n個網(wǎng)絡(luò)結(jié)點，標記為1到n。給定一個列表times，表示信號經(jīng)過有向邊的傳遞時間，times[i]=（ui，vi，wi），其中ui是源結(jié)點，vi是目標結(jié)點，wi是一個信號從源結(jié)點傳遞到目標結(jié)點的時間?，F(xiàn)在從某個結(jié)點k（1≤k≤n）發(fā)出一個信號，設(shè)計一個算法求需要多久才能使所有結(jié)點都收到信號？如果不能使所有結(jié)點收到信號，返回-1

。

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

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

def

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

s=k-1

#源點為s9

dist[s]=010

qu=deque()

#定義一個隊列qu11

qu.append(s)

#源點結(jié)點進隊63/9612

while

qu:

#隊列不空循環(huán)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

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

#源點結(jié)點進隊13

visited[s]=True66/9614

while

qu:

#隊列不空循環(huán)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

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

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

#定義一個優(yōu)先隊列pqu9 heapq.heappush(pqu,QNode(0,s,0)) #源點結(jié)點進隊90/9610 whilepqu: #隊列不空循環(huán)11 e=heapq.heappop(pqu) #出隊結(jié)點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]) #建立相鄰點的結(jié)點e119 prev[v]=u20 heapq.heappush(pqu,e1) #頂點v進隊91/96上述算法中理論上所有邊都需要做一次松馳操作。最壞時間復(fù)雜度為O(e)，其中e為圖的邊數(shù)。算法分析92/96問題描述：有一個m×n的二維數(shù)組height表示地圖，height[i][j]表示(i，j)位置的高度。

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

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

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

def

minimumEffortPath(self,

heights)

->

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

QNode:

#優(yōu)先隊列結(jié)點類2

def

__init__(self,x,y,length):

#構(gòu)造方法3

self.x,self.y=x,y

#位置4

self.length=length

#路徑長度5

def

__lt__(self,other):

#length越小越優(yōu)先出隊6

return

self.length<other.length96/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=[]

#定義一個優(yōu)先隊列pqu16

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

#源點結(jié)點進隊17

dist[0][0]=097/9618

while

pqu:

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

e=heapq.heappop(pqu)

#出隊結(jié)點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)

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

heapq.heappush(pqu,e1)

#結(jié)點e1進隊30

return

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

jobs

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

例如，jobs={1，2，4，7，8}，k=2，結(jié)果為11，對應(yīng)的一種分配方案是1號工人分配時間為1、2、8的任務(wù)（工作時間=1+2+8=11），2號工人分配時間為4、7的任務(wù)（工作時間=4+7=11），最大工作時間是11。自學(xué)100/96有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價值最大的方案。W=6物品編號重量w價值v0541342233116.4.50/1背包問題101/96采用優(yōu)先隊列式分支限界法求解0/1背包問題時，按結(jié)點的限界函數(shù)值ub越大越優(yōu)先出隊，所以每個結(jié)點都有ub值。解1 classQNode: #優(yōu)先隊列中結(jié)點類型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越大越優(yōu)先出隊9 returnself.ub>other.