《算法设计与分析基础》（Python语言描述） 课件 第6章分支限界法1

第6章朝最优解方向前进—分支限界法6.1分支限界法概述6.2广度优先搜索CONTENTS提纲6.3队列式分支限界法6.4优先队列式分支限界法1/37分支限界法=广度优先搜索+剪支。6.1.1什么是分支限界法6.1分支限界法概述算法解空间搜索方式存储结点的数据结构结点存储特性常用应用回溯法深度优先栈只保存从根结点到当前扩展结点的路径找出满足约束条件的所有解分支限界法广度优先队列，优先队列每个结点只有一次成为活结点的机会找出一个解或最优解2/37求迷宫问题的所有解：应该采用回溯法，不适合采用分支限界法。求迷宫问题的一条最短路径：属于最优解问题，适合采用分支限界法。说明3/376.1.2分支限界法设计要点1.设计合适的限界函数活结点si1si2si4si3活结点si2si3sisi为什么分支限界法比回溯法设计限界函数更重要？4/37设计上界限界函数ub()，若从xi的分支向下搜索所得到的部分解是（x0，x1，…，xi，…，xk），则应该满足： ub(xi)≥ub(xi+1)≥…≥ub(xk)所以根结点的ub值应该大于或等于最优解的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值应该小于或等于最优解的lb值。如果从si结点扩展到sj结点，应满足lb(si)≤lb(sj)，将所有大于lb(si)的结点剪支。假设解向量x=（x0，x1，…，xn-1），如果目标函数是求最小值x0x1xn-1lb6/372.组织活结点表1）队列式分支限界法活结点表组织成一个队列，并按照队列先进先出原则选取下一个结点为扩展结点。与广度优先搜索相同。队列通常采用deque实现。2）优先队列式分支限界法活结点表组组成一个优先队列，并选取优先级最高的活结点成为当前扩展结点（跳跃式扩展）。优先队列通常采用heapq实现。7/373.求最优解的解向量①对每个扩展结点保存从根结点到该结点的路径（解向量）。

1101010101:状态值解向量:[0,0,0]2:状态值解向量:[1,0,0]4:状态值解向量:[1,1,0]5:状态值解向量:[1,0,0]8:状态值解向量:[1,0,1]9:状态值解向量:[1,0,0]6:状态值解向量:[0,1,0]10:状态值解向量:[0,1,1]11:状态值解向量:[0,1,0]7:状态值解向量:[0,0,0]3:状态值解向量:[0,0,0]0答案：0118/37②在每个结点中保存搜索路径中的前驱结点，反推搜索路径（解向量）。1010101011:状态值双亲指针:02:状态值双亲指针:14:状态值双亲指针:25:状态值双亲指针:28:状态值双亲指针:59:状态值双亲指针:56:状态值双亲指针:310:状态值双亲指针:611:状态值双亲指针:67:状态值双亲指针:33:状态值双亲指针:10答案：0119/376.1.3分支限界法的时间分析解空间树共有n+1层（根结点为第0层，叶子结点为第n层）。第1层有m0个结点，每个结点有m1个子结点。第2层有m0m1个结点，同理，第3层有m0m1m2个结点，依此类推，第n层有m0m1…mn-1个结点。则采用分支限界法求所有解的算法的执行时间为

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广度优先搜索广度优先搜索是在访问一个顶点v之后横向搜索v的所有相邻点.在解空间中搜索时类似树的层次遍历方式。11/376.2.1图的广度优先遍历采用广度优先搜索方法遍历图称为图的广度优先遍历，其过程是从起始点v出发，以横向方式一步一步沿着边访问各个顶点，得到遍历序列称为广度优先遍历序列。广度优先遍历采用队列存储活结点，先进队的结点先扩展。同样广度优先遍历特指图的一种遍历方式，而广度优先搜索是一种通用的搜索方式，前者是后者的一种应用。12/376.2.2广度优先搜索算法框架广度优先搜索基本广度优先搜索分层次广度优先搜索多起点广度优先搜索13/371.基本广度优先搜索假设起始搜索点为s，目标点为t，从s出发找t。1 defbfs(): #基本广度优先搜索算法框架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利用其特性快速找最优解。广度优先搜索算法的主要应用15/37在解空间中搜索时需要扩展结点。如果每次扩展的代价都计为相同的p，则第一次找到目标点的代价就一定是最小代价。如果每次扩展的代价不同，则第一次找到目标点的代价就不一定是最小代价。任何情况下利用广度优先搜索都可以找到最优解？16/372.分层次广度优先搜索求不带权图中s到t的最短路径长度。1 defbfs(): #分层次的广度优先搜索算法框架2 定义队列qu和访问标记数组3 置起始点s已经访问4 起始点s进入队列qu5 ans=0

#表示最短路径长度6 while队列qu不空: #外循环的次数是s到t的层次数7 cnt=len(qu) #当前层的结点个数为cnt8 foriinrange(0,cnt): #循环cnt次扩展每个结点9 出队结点e10 ife==t:returnans #找到目标点返回ans11 for从e扩展出e1:12 置e1已经访问13 将结点e1进入队列qu14 ans+=115 return-1 #表示没有找到t17/373.多起点广度优先搜索求不带权图中多个顶点（用顶点集合S表示）到t的最短路径长度。1 intbfs(): #多起点的广度优先搜索算法框架2 定义队列qu和访问标记数组3 置S中所有的起始点已经访问4 将S中所有的起始点进入队列qu5 ans=1

#表示最短路径长度6 while队列qu不空: #外循环的次数就是s到t的层次数7 cnt=len(qu)

#当前层的结点个数为cnt8 foriinrange(0,cnt)：

#循环cnt次扩展每个结点9 出队结点e10 ife==t:returnans #找到目标点返回ans11 for从e扩展出e1:12 置e1已经访问13 将结点e1进入队列qu14 ans+=115 return-1 #表示没有找到t18/37问题描述：有一只跳蚤的家在数轴上的位置x处，请你帮助它从位置0出发到达它的家。跳蚤跳跃的规则如下：

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

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

（3）跳蚤不能连续往后跳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实战—到家的最少跳跃次数（LeetCode1654★★）19/37解跳蚤从位置0出发跳到位置x，只有向前和向后两种跳跃方式，无论哪种方式都计一次，求的是最小跳跃次数，满足广搜特性，采用分层次广度优先遍历求最优解。x的最大值为2000，每次跳跃不超过2000，又规定不能连续往后跳2次，所以最大的跳跃位置不可能超过6000，设置MAXX=6000。由于跳蚤不能连续往后跳2次，需要记录当前向后跳跃的次数，因此当前状态表示为（当前位置，向后跳跃次数），访问标记数组设计为二维数组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: #队不空时循环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上述程序提交结果为通过，执行用时为188ms，内存消耗为15.7MB。24/37问题描述：有一个2×3的面板board，其中放置有5个物品，用数字1~5来表示，另外一个空位置用0表示。一次移动定义为0与一个上下左右的相邻数字进行交换，面板的目标状态是{{1，2，3}，{4，5，0}}。设计一个算法求由给定的面板初始状态到目标状态的最少移动次数，如果不能到达目标状态则返回-1。

例如，board={{1，2，3}，{4，0，5}}，结果为1，只需要交换0和5即可。

要求设计如下方法：

def

slidingPuzzle(self,

board)

->

int6.2.4实战—滑动谜题（LeetCode773★★★）25/37解显然本问题满足广搜特性，采用分层次广度优先遍历求最优解（最少移动次数）。本问题中状态是由board确定的，仅仅考虑0的位置是不够的，因为0的位置相同其他数字的顺序不同时构成不同的状态。在搜索过程不能访问之前出现的重复状态。由于这里board不是单个整数，判断重复比较麻烦，为此将board转换为一个字符串。例如board={{1，2，3}，{4，0，5}}转换为“123405”，如下图3所示，这样目标状态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存放已访问的状态，其查找时间接近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()

#状态访问标记12

qu.append(s)

#初始状态s进队13

visited.add(s)14

ans=0

#最少移动次数28/3715

while

qu:16

cnt=len(qu)

#队不空时循环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状态进队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)

#连接为新字符串后返回上述程序提交结果为通过，执行用时为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实战—腐烂的橘子（LeetCode994）31/37分钟0分钟1分钟2分钟3分钟432/37返回4解采用多起点+分层的广度优先遍历的方法。用ans表示经过的最小分钟数（初始为0）。先将所有腐烂橘子进队（可能有多个腐烂橘子），然后一层一层地搜索相邻新鲜橘子，当有相邻新鲜橘子时就将其变为腐烂橘子，此时置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