《算法設計與分析基礎》（Python語言描述） 課件 第6章分支限界法1

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

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②在每個結點中保存搜索路徑中的前驅結點，反推搜索路徑（解向量）。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層（根結點為第0層，葉子結點為第n層）。第1層有m0個結點，每個結點有m1個子結點。第2層有m0m1個結點，同理，第3層有m0m1m2個結點，依此類推，第n層有m0m1…mn-1個結點。則采用分支限界法求所有解的算法的執(zhí)行時間為

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

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

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

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

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

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

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

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

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

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

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

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

QNode:

#隊列結點類2

def

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

self.p=x

#當前位置4

self.bstep=y

#從當前位置向后跳次數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

#最少跳躍次數22/3716

while

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

cnt=len(qu)

#隊列中元素個數為cnt18

for

i

in

range(0,cnt):19

e=qu.popleft()

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

#結點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)

#結點e2進隊30

ans+=1

#跳躍次數增131

return

-1

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

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

要求設計如下方法：

def

slidingPuzzle(self,

board)

->

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

0

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

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)，與數組按下標查找的性能差不多。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轉換為一個字符串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

#最少移動次數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]交換的結果30

a=list(s)

#將s轉換為列表a31

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

32

return

''.join(a)

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

要求設計如下方法： def

orangesRotting(self,

grid)

->

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

QNode:

#隊列結點類2

def

__init__(self,x,y):

#構造方法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),le