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

第6章朝最优解方向前进—分支限界法;分支限界法=广度优先有哪些信誉好的足球投注网站+剪支。;;;设计上界限界函数ub()，若从xi的分支向下有哪些信誉好的足球投注网站所得到的部分解是（x0，x1，…，xi，…，xk），则应该满足：

ub(xi)≥ub(xi+1)≥…≥ub(xk)

所以根结点的ub值应该大于或等于最优解的ub值。如果从si结点扩展到sj结点，应满足ub(si)≥ub(sj)，将所有小于ub(si)的结点剪支。;设计下界限界函数lb()，若从xi的分支向下有哪些信誉好的足球投注网站所得到的部分解是（x0，x1，…，xi，…，xk），则应该满足：

lb(xi)≤lb(xi+1)≤…≤lb(xk)

所以根结点的bb值应该小于或等于最优解的lb值。如果从si结点扩展到sj结点，应满足lb(si)≤lb(sj)，将所有大于lb(si)的结点剪支。;;;;;;;;;;;;;;;;;;;;;;;;;;;;1 class?QNode:??????? #队列结点类

2???? def?__init__(self,x,y):?? #构造方法

3?????? self.x,self.y=x,y?? #当前位置(x,y);5 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])? #行列数

10??????qu=deque()?? #定义一个队列qu

11??????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??????????????? #经过的最小分钟数;15?? while?qu:? #队不空循环

16????? flag=False

17???? cnt=len(qu) #求队列中元素个数cnt

18????? for?i?in?range(0,cnt):? #循环cnt次处理该层所有结点

19???????? e=qu.popleft()???? #出队结点e

20???????? for?di?in?range(0,4):? #四周有哪些信誉好的足球投注网站

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

22????????? if?nx=0?and?nxm?and?ny=0?and?nyn?

and?grid[nx][ny]==1:

23???????????? grid[nx][ny]=2? #新鲜橘子变为腐烂橘子

24???????????? qu.append(QNode(nx,ny))? #腐烂橘子进队

25???????????? flag=True?? #表示有新鲜橘子变为腐烂橘子

26??? if?flag:?ans+=1?? #有新鲜橘子变为腐烂时ans增1;27???? for?i?in?range(0,m):?? #判断是否还存在新鲜橘子

28???????? for?j?in?range(0,n):

29??????????? if?grid[i][j]==1:

return?-1? #还存在新鲜橘子,返回-1

30???? return?ans;6.1分支限界法概述;;1 defbfs(): #队列式分支限界法算法框架

2 定义一个队列qu

3 根结点进队

4 while队不空时循环:

5 出队结点e

6 for扩展结点e产生结点e1:

7 ife1满足constraint()andbound():

8 ife1是叶子结点:

9 比较得到一个更优解或者直接返回

10 else:

11 将结点e1进队;;;解;队列式分支限界法：其中每个结点存放一个进队的顶点编号。

用dist数组存放源点s出发的最短路径长度，dist[i]表示源点s到顶点i的最短路径长度，初始时所有dist[i]值为∞。

用prev数组存放最短路径，prev[i]表示源点s到顶点i的最短路径中顶点i的前驱顶点。;;0;4 defbfs(s): #求解算法

6 dist=[INF]*n