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

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

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

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

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

#當(dāng)前層的結(jié)點(diǎn)個數(shù)為cnt8 foriinrange(0,cnt)：

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

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

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

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

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

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

給定一個整數(shù)數(shù)組forbidden，其中forbidden[i]是跳蚤不能跳到的位置，同時給定整數(shù)a，b和x，設(shè)計(jì)一個算法求跳蚤到家的最少跳躍次數(shù)，如果沒有恰好到達(dá)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實(shí)戰(zhàn)—到家的最少跳躍次數(shù)（LeetCode1654★★）19/37解跳蚤從位置0出發(fā)跳到位置x，只有向前和向后兩種跳躍方式，無論哪種方式都計(jì)一次，求的是最小跳躍次數(shù)，滿足廣搜特性，采用分層次廣度優(yōu)先遍歷求最優(yōu)解。x的最大值為2000，每次跳躍不超過2000，又規(guī)定不能連續(xù)往后跳2次，所以最大的跳躍位置不可能超過6000，設(shè)置MAXX=6000。由于跳蚤不能連續(xù)往后跳2次，需要記錄當(dāng)前向后跳躍的次數(shù)，因此當(dāng)前狀態(tài)表示為（當(dāng)前位置，向后跳躍次數(shù)），訪問標(biāo)記數(shù)組設(shè)計(jì)為二維數(shù)組visited[MAXX+1][2]。forbidden數(shù)組表示不能跳到的位置，初始時將forbidden中所有位置的visited元素置為true。20/371 class

QNode:

#隊(duì)列結(jié)點(diǎn)類2

def

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

self.p=x

#當(dāng)前位置4

self.bstep=y

#從當(dāng)前位置向后跳次數(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()

#用雙端隊(duì)列作為隊(duì)列qu13

qu.append(QNode(0,0))

#起始點(diǎn)進(jìn)隊(duì)14

visited[0][0]=True

#置已訪問標(biāo)記15

ans=0

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

while

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

cnt=len(qu)

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

for

i

in

range(0,cnt):19

e=qu.popleft()

#出隊(duì)結(jié)點(diǎn)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é)點(diǎn)e1進(jìn)隊(duì)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é)點(diǎn)e2進(jìn)隊(duì)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ù)字進(jìn)行交換，面板的目標(biāo)狀態(tài)是{{1，2，3}，{4，5，0}}。設(shè)計(jì)一個算法求由給定的面板初始狀態(tài)到目標(biāo)狀態(tài)的最少移動次數(shù)，如果不能到達(dá)目標(biāo)狀態(tài)則返回-1。

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

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

def

slidingPuzzle(self,

board)

->

int6.2.4實(shí)戰(zhàn)—滑動謎題（LeetCode773★★★）25/37解顯然本問題滿足廣搜特性，采用分層次廣度優(yōu)先遍歷求最優(yōu)解（最少移動次數(shù)）。本問題中狀態(tài)是由board確定的，僅僅考慮0的位置是不夠的，因?yàn)?的位置相同其他數(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所示，這樣目標(biāo)狀態(tài)t="123450"。123405102132430455"123405"26/37為了實(shí)現(xiàn)移動操作（

0

與一個上下左右相鄰數(shù)字交換），將位置映射關(guān)系采用位置鄰接表表示，如下圖所示，例如位置4為0，只能與位置1、3或者5的數(shù)字進(jìn)行交換。對應(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ù)組按下標(biāo)查找的性能差不多。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()

#定義一個隊(duì)列11

visited=set()

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

qu.append(s)

#初始狀態(tài)s進(jìn)隊(duì)13

visited.add(s)14

ans=0

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

while

qu:16

cnt=len(qu)

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

for

k

in

range(0,cnt):18

curs=qu.popleft()

#出隊(duì)curs19

if

curs==t:return

ans

#找到目標(biāo)返回ans20

i=curs.index('0')

#查找'0'的位置i21

for

j

in

adj[i]:

#找位置i的相鄰位置j22

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

#擴(kuò)展23

if

nboard

not

in

visited:

#nboard未訪問過24

qu.append(nboard)

#nboard狀態(tài)進(jìn)隊(duì)25

visited.add(nboard)

#置已訪問標(biāo)記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è)計(jì)如下方法： def

orangesRotting(self,

grid)

->

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

QNode:

#隊(duì)列結(jié)點(diǎn)類2

def

__init__(self,x,y):

#構(gòu)造方法3

self.x,self.y=x,y

#當(dāng)前位置(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