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

6.1分支限界法概述6.2广度优先搜索CONTENTS提纲6.3队列式分支限界法6.4优先队列式分支限界法第6章朝最优解方向前进—分支限界法1/966.3.1队列式分支限界法概述6.3队列式分支限界法在解空间中搜索解时，队列式分支限界法与广度优先搜索相同，也是采用普通队列存储活结点。从根结点开始一层一层地扩展和搜索结点，同时利用剪支以提高搜索性能。2/961 defbfs(): #队列式分支限界法算法框架2 定义一个队列qu3 根结点进队4 while队不空时循环:5 出队结点e6 for扩展结点e产生结点e1:7 ife1满足constraint()andbound():8 ife1是叶子结点:9 比较得到一个更优解或者直接返回10 else:11 将结点e1进队3/96在结点e出队时判断，也就是在结点e扩展出子结点之前对e进行判断。在出队的结点e扩展出子结点e1后再对e1进行判断。前者的优点是算法设计简单，后者的优点是节省队列空间，因为一般情况下解空间中叶子结点可能非常多，而叶子结点是不会扩展的，前者仍然将叶子结点进队了。判断是否为叶子结点的两种方式4/96问题描述：给定一个带权有向图G=（V，E），其中每条边的权是一个正整数。另外给定V中的一个顶点s，称为源点。计算从源点到其他所有其他各顶点的最短路径及其长度。这里的路径长度是指路上各边权之和。41050201030100024531606.3.2图的单源最短路径5/96解4105020103010002453160A=[[[2,10],[4,30],[5,100]], #顶点0 [[2,4]], #顶点1 [[3,50]], #顶点2 [[5,10]], #顶点3 [[3,20],[5,60]], #顶点4 []] #顶点56/96队列式分支限界法：其中每个结点存放一个进队的顶点编号。用dist数组存放源点s出发的最短路径长度，dist[i]表示源点s到顶点i的最短路径长度，初始时所有dist[i]值为∞。用prev数组存放最短路径，prev[i]表示源点s到顶点i的最短路径中顶点i的前驱顶点。7/96wdist[v]uvs源点dist[u]边松驰操作dist[v]=min{dist[v]，dist[u]+w}8/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没有修改，不进队最终结果：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=39/964 defbfs(s): #求解算法6 dist=[INF]*n #dist初始化所有元素为∞7 prev=[-1]*n #prev初始化所有元素为-18 dist[s]=09 qu=deque() #定义一个队列qu10 qu.append(s) #源点结点进队10/9611 whilequ: #队列不空循环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}11/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()12/9639 defsolve(A,n,s): #求源点v出发的所有最短路径40 globalsum41 sum=042 bfs(s)43 print("求解结果")44 foriinrange(0,n):dispapath(s,i)45 print("sum=",sum)13/964105020103010002453160程序验证14/96在图中搜索路径时需要解决的一个重要问题是路径判重，即判断路径上是否出现重复的顶点，因为含重复顶点的路径是没有意义的。上述算法没有路径判重，通过边松驰操作总是能够找到源点s到其他顶点的最短路径。不仅仅适合权为正数的图，也适合含负权的图，但不适合含负权回路的图。15/96问题描述：给定一个带权有向图G=（V，E），其中每条边的权是一个整数（可能是负整数）。另外给定V中的一个顶点s，称为源点。计算从源点到其他所有其他各顶点的最短路径及其长度。这里的路径长度是指路上各边权之和。6.3.3SPFA算法16/96SPFA算法也是一个求单源最短路径的算法，全称是ShortestPathFasterAlgorithm（SPFA），是由西南交通大学段凡丁老师1994年发明的。解17/96SPFA是6.3.2节求单源最短路径算法的改进，6.3.2节的算法中，当出队结点（u）时，考虑某个相邻点v，若满足条件dist[u]+w<dist[v]，修改dist[v]=dist[u]+w（边松驰），如果顶点v已经在队列中，后面会出队v并对其所有出边松驰的，此时再将（v）进队就重复了，所以改为仅将不在队列中的（v）进队。wdist[v]uvs源点dist[u]dist[v]=min{dist[v]，dist[u]+w}18/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]=9019/96布尔数组visited标记一个顶点是否在队列中（初始时所有元素为False），顶点u进队时置visited[u]为True，出队时恢复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) #源点结点进队9 visited[s]=True20/9610 whilequ: #队列不空循环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]=True21/96SPFA的时间复杂度是O(e)，但一般来说SPFA算法性能优于6.3.2节的算法。不仅仅适合权为正数的图，也适合含负权的图，但不适合含负权回路的图。算法分析22/96问题描述：有n个网络结点，标记为1到n。给定一个列表times，表示信号经过有向边的传递时间，times[i]=（ui，vi，wi），其中ui是源结点，vi是目标结点，wi是一个信号从源结点传递到目标结点的时间。现在从某个结点k（1≤k≤n）发出一个信号，设计一个算法求需要多久才能使所有结点都收到信号？如果不能使所有结点收到信号，返回-1

。

例如，times={{2，1，1}，{2，3，1}，{3，4，1}}，n=4，k=2，结果为2。

要求设计如下方法：

def

networkDelayTime(self,times,n,k)->int6.3.4实战—网络延迟时间（LeetCode743★★）23/96从结点k传递信号到某个结点v的时间就是从k到v的最短路径长度，这样该问题转换为求单源最短路径问题，在所有的最大连接长度中求最大值就是题目的答案。先由times建立图的邻接表adj（见第2章2.9.1节图的邻接表存储结构），每个网络结点对应图中一个顶点。为了简便，通过减1将顶点编号改为0～n-1。采用6.3.2节的队列式分支限界法求出源点k-1到其他所有所有顶点的最短路径长度dist数组。再在dist数组中求最大值ans，若ans=INF说明不能使所有结点收到信号，返回-1，否则返回ans。解法124/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])25/968

s=k-1

#源点为s9

dist[s]=010

qu=deque()

#定义一个队列qu11

qu.append(s)

#源点结点进队26/9612

while

qu:

#队列不空循环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

ans27/96采用SPFA算法求源点k-1到其他所有所有顶点的最短路径长度dist数组。其他与解法1相同。解法228/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)

#源点结点进队13

visited[s]=True29/9614

while

qu:

#队列不空循环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

ans30/96程序提交结果均通过。解法1运行时间为92ms，解法2运行时间为72ms。消耗空间几乎相同。从运行时间看出，SPFA算法的性能略好。比较31/96有n个编号为0～n-1的物品，重量为w={w0，w1，…，wn-1}，价值为v={v0，v1，…，vn-1}，给定一个容量为W的背包。从这些物品中选取全部或者部分物品装入该背包中，每个物品要么选中要么不选中，即物品不能被分割，找到选中物品不仅能够放到背包中而且价值最大的方案。W=6物品编号重量w价值v0541342233116.3.50/1背包问题32/96解空间与用回溯法求解的解空间相同，根结点层次i=0，第i层表示对物品i的决策，只有选择和不选择两种情况，每次二选一，叶子结点的层次是n。用x表示解向量。x[i]=0x[i]=1第i层结点选择物品i的子结点e1不选择物品i的子结点e2解33/96另外用bestx和bestv（初始设置为0）分别表示最优解向量和最大总价值。设计队列结点类型如下：1 classQNode: #队列中结点类型2 def__init__(self):3 self.i=0 #当前层次(物品序号)4 self.cw=0 #当前总重量5 self.cv=0 #当前总价值6 self.x=[] #当前解向量7 self.ub=0.0 #上界34/96限界函数：先按单位重量价值递减排序。4 defbound(e): #求结点e的上界函数值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同回溯法求解的限界函数35/96对于第i层的结点e，求出结点e的上界函数值ub，其剪支如下：左剪支：终止选择物品i超重的分支，也就是仅仅扩展满足e.cw+w[i]≤W条件的子结点e1，即满足该条件时将e1进队。右剪支：终止在不选择物品i时即使选择剩余所有满足限重的物品有不可能得到更优解的分支，也就是仅仅扩展满足e.ub>bestv条件的子结点e2，即满足该条件时将e2进队。36/96W=6序号i物品编号no重量w价值vv/w02231.511341.32311130540.8(cw,cv,ub)仅扩展e.ub>bestv的右结点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结果：bestv=837/9617 defEnQueue(e,qu): #结点e进队操作18 globaln,bestv,bestx,bestw19 ife.i==n: #到达叶子结点20 ife.cv>bestv: #比较更新最优解21 bestv=e.cv22 bestx=copy.deepcopy(e.x)23 bestw=e.cw24 else:qu.append(e) #非叶子结点进队38/9626 defbfs(): #求0/1背包最优解的算法27 globalg,n,W,bextx,bestw,sum28 qu=deque()

#定义一个队列29 e=QNode()30 e.i,e.cw,e.cv=0,0,0 #根结点层次为031 e.x=[-1]*n32 qu.append(e) #根结点进队39/9633 whilequ: #队不空循环34 e=qu.popleft() #出队结点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 #左子结点的层次加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 #右子结点的层次加147bound(e2) #求出不选择物品i的上界48ife2.ub>bestv: #右剪支49 EnQueue(e2,qu)40/9651 defknap(g,n,W): #求0/1背包问题52 globalbestx,bestv,bestw,sum53 g.sort() #按v/w递减排序54 bestx=[-1]*n #存放最优解向量55 bestv=0 #存放最大价值,初始为056 bestw=0 #最优解总重量57 sum=0 #累计搜索的结点个数58 bfs() #i从0开始59 print("求解结果")60 foriinrange(0,n):61 ifbestx[i]==1:print("选取第%d个物品"%(g[i].no))62 print("总重量=%d,总价值=%d"%(bestw,bestv))63 print("sum=",sum)41/96程序验证W=6物品编号重量w价值v05413422331142/96求解0/1背包问题的解空间是一棵高度为n+1的满二叉树。bound()方法的时间复杂度为O(n)。最坏时间复杂度仍然为O(n×2n)。算法分析43/96解空间与用回溯法求解的解空间相同，根结点层次i=0，第i层表示对物品i的决策，只有选择和不选择两种情况，每次二选一，叶子结点的层次是n。用x表示解向量。x[i]=0x[i]=1第i层结点选择物品i的子结点e1不选择物品i的子结点e2解44/96另外用bestx和bestv（初始设置为0）分别表示最优解向量和最大总价值。设计队列结点类型如下：classQNode{ //队列中结点类型 inti; //当前层次(物品序号) intcw; //当前总重量 intcv; //当前总价值 intx[]; //当前解向量 doubleub; //上界}45/966.4.1队列式分支限界法概述6.4优先队列式分支限界法采用优先队列存储活结点，用PriorityQueue实现。根据需要设计相应的限界函数，求最大值问题设计上界函数ub，求最小值问题设计下界函数lb。不同于队列式分支限界法中结点一层一层地出队，优先队列式分支限界法中结点出队（扩展结点）是跳跃式，这样有助于快速地找到一个解，并以此为基础进行剪支，所以通常算法的时间性能更好。46/961 defbfs(): #优先队列式分支限界法框架2 定义一个优先队列pqu3 根结点进队4 while队pqu不空时循环:5 出队结点e6 for扩展结点e产生结点e1:7 ife1满足constraint()andbound():8 ife1是叶子结点:9 比较得到一个更优解或者直接返回最优解10 else:11 将结点e1进队47/96问题描述：给定一个带权有向图G=（V，E），其中每条边的权是一个正整数。另外给定V中的一个顶点s，称为源点。计算从源点到其他所有其他各顶点的最短路径及其长度。这里的路径长度是指路上各边权之和。41050201030100024531606.4.2图的单源最短路径48/96解4105020103010002453160A=[[[2,10],[4,30],[5,100]], #顶点0 [[2,4]], #顶点1 [[3,50]], #顶点2 [[5,10]], #顶点3 [[3,20],[5,60]], #顶点4 []] #顶点549/961 classQNode: #优先队列结点类2 def__init__(self,i,vno,length): #构造方法3 self.i=i #结点的层次4 self.vno=vno #顶点编号5 self.length=length #路径长度6 def__lt__(self,other): #按length越小越优先出队7 returnself.length<other.length优先队列式分支限界法求解。队列结点类型声明如下：解50/96初始化dist数组所有元素为∞，定义元素类型为QNode的优先队列pqu。先将根结点进队，队不空时循环，出队一个结点，对相应顶点的所有出边做松驰操作，直到队列为空，最后的dist[i]就是源点到顶点i的最短路径长度。51/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出发的最短路径52/963 defbfs(s): #优先队列式分支限界算法4 globalA,n,dist,prev,sum5 dist=[INF]*n #dist初始化为∞6 prev=[-1]*n #prev初始化为-17 dist[s]=08 pqu=[]

#定义一个优先队列pqu9 heapq.heappush(pqu,QNode(0,s,0)) #源点结点进队53/9610 whilepqu: #队列不空循环11 e=heapq.heappop(pqu) #出队结点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]) #建立相邻点的结点e119 prev[v]=u20 heapq.heappush(pqu,e1) #顶点v进队54/96上述算法中理论上所有边都需要做一次松驰操作。最坏时间复杂度为O(e)，其中e为图的边数。算法分析55/96问题描述：有一个m×n的二维数组height表示地图，height[i][j]表示(i，j)位置的高度。

设计一个算法求从左上角(0，0)走到右下角(m-1，n-1)的最小体力消耗值，每次可以往上、下、左、右

四个方向之一移动，一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值。

要求设计如下方法：

def

minimumEffortPath(self,

heights)

->

int:6.4.3实战—最小体力消耗路径（LeetCode1631★★）56/96例如，heights=[[1，2，2]，[3，8，2]，[5，3，5]]，最优行走路径如下，该路径的高度是[1，3，5，3，5]，连续格子的差值绝对值最大为2，所以结果为2。222212238253557/96本问题不同于常规的路径问题。地图中位置用一个顶点表示，一条边(x，y)→(nx，ny)，其权值为abs(heights[nx][ny]-heights[x][y])，这里的路径长度不是路径中所有边的权值和，而是最大的权值。现在要求顶点(0，0)到顶点(m-1，n-1)的最小路径长度。解222212238253558/961 class

QNode:

#优先队列结点类2

def

__init__(self,x,y,length):

#构造方法3

self.x,self.y=x,y

#位置4

self.length=length

#路径长度5

def

__lt__(self,other):

#length越小越优先出队6

return

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

#定义一个优先队列pqu16

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

#源点结点进队17

dist[0][0]=060/9618

while

pqu:

#队列不空循环19

e=heapq.heappop(pqu)

#出队结点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)

#创建子结点e129

heapq.heappush(pqu,e1)

#结点e1进队30

return

-161/96上述程序提交结果为通过，执行用时为808ms，内存消耗为16.7MB。62/966.4.4实战—完成所有工作的最短时间（LeetCode1723）问题描述：给你一个整数数组

jobs

，其中jobs[i]是完成第i项工作要花费的时间。将这些工作分配给k位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化，返回分配方案中尽可能最小的最大工作时间。

例如，jobs={1，2，4，7，8}，k=2，结果为11，对应的一种分配方案是1号工人分配时间为1、2、8的任务（工作时间=1+2+8=11），2号工人分配时间为4、7的任务（工作时间=4+7=11），最大工作时间是11。自学63/96有n个编号为0～n-1的物品，重量为w={w0，w1，…，wn-1}，价值为v={v0，v1，…，vn-1}，给定一个容量为W的背包。从这些物品中选取全部或者部分物品装入该背包中，每个物品要么选中要么不选中，即物品不能被分割，找到选中物品不仅能够放到背包中而且价值最大的方案。W=6物品编号重量w价值v0541342233116.4.50/1背包问题64/96采用优先队列式分支限界法求解0/1背包问题时，按结点的限界函数值ub越大越优先出队，所以每个结点都有ub值。解1 classQNode: #优先队列中结点类型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越大越优先出队9 returnself.ub>other.ub65/96W=6序号i物品编号no重量w价值vv/w02231.511341.32311130540.8bestv=80,0,8015××0174,5,6.6×012,3,80,0,6.61015,7,82,3,6.42016,8,85,7,7.8310×6,8,840163,4,6.6×01××8019×3,4,6.401××10end66/966 defEnQueue(e,pqu): #结点e进队操作7 globaln,bestv,bestx,bestw8 ife.i==n: #到达叶子结点9 ife.cv>bestv:

#比较更新最优解10 bestv=e.cv11 bestx=copy.deepcopy(e.x)12 bestw=e.cw13 else:heapq.heappush(pqu,e) #非叶子结点进队67/9615 defbfs(): #优先队列式分支限界法求0/1背包问题16 globalg,n,W,bextx,bestw,sum17 pqu=[]

#定义一个优先队列pqu18 e=QNode()19 e.i,e.cw,e.cv=0,0,0 #根结点层次为020 e.x=[-1]*n21 bound(e)22 heapq.heappush(pqu,e) #源点结点进队68/9623 whilepqu: #队不空循环24 e=heapq.heappop(pqu) #出队结点e26 ife.cw+g[e.i].w<=W:

#左剪支27 e1=QNode()28 e1.cw=e.cw+g[e.i].w #选择物品e.i29 e1.cv=e.cv+g[e.i].v30 e1.x=copy.deepcopy(e.x);e1.x[e.i]=131 e1.i=e.i+1 #左孩子结点的层次加132 bound(e1)33 EnQueue(e1,pqu)34 e2=QNode()35 e2.cw,e2.cv=e.cw,e.cv #不选择物品e.i36 e2.x=copy.deepcopy(e.x);e2.x[e.i]=037 e2.i=e.i+1 #右孩子结点的层次加138 bound(e2) #求出不选择物品i的价值上界39 ife2.ub>bestv: #右剪支40 EnQueue(e2,pqu)69/9642 defknap(g,n,W): #求0/1背包问题43 globalbestx,bestv,bestw,sum44 g.sort() #按v/w递减排序45 bestx=[-1]*n #存放最优解向量46 bestv=0 #存放最大价值,初始为047 bestw=0 #最优解总重量48 sum=0 #累计搜索的结点个数49 bfs() #i从0开始50 print("求解结果")51 foriinrange(0,n):52 ifbestx[i]==1:print("选取第%d个物品"%(g[i].no))53 print("总重量=%d,总价值=%d"%(bestw,bestv))54 print("sum=",sum)70/96无论采用队列式分支限界法还是优先队列式分支限界法求解0/1背包问题，最坏情况下要搜索整个解空间树，所以最坏时间复杂度均为O(n×2n)。算法分析71/96问题描述：有n（n≥1）个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务。第i个人执行第j个任务的成本是c[i][j]（0≤i，j≤n-1）。求出总成本最小的一种分配方案。人员任务0任务1任务2任务3092781643725818376946.4.6任务分配问题72/96解优先队列结点类型：1 classQNode: #优先队列结点类2 def__init__(self):3 self.i=0 #人员编号(层次)4 self.cost=0 #已经分配任务所需要的成本5 self.x=[] #当前解向量6 self.used=[] #used[i]为真表示任务i已经分配7 self.lb=0 #下界8 def__lt__(self,other): #按lb越小越优先出队9 returnself.lb<other.lb73/96lb为当前结点对应分配方案的成本下界。对于第i层的某个结点e，当搜索到该结点时表示已经为人员0～i-1分配好了任务（人员i尚未分配任务），余下分配的成本下界是c数组中第i行～第n-1行各行的最小元素和minsum，显然这样的分配方案的最小成本为e.cost+minsum。74/96第i层第i+1层xi=jee1minsume1.lb=e1.cost+minsum求结点e的最小成本的限界函数如下（同回溯法）。1 defbound(e): #求结点e的下界值3 minsum=04 fori1inrange(e.i,n): #求c[e.i..n-1]行中最小元素和5 minc=INF6 forj1inrange(0,n):7 ifnote.used[j1]andc[i1][j1]<minc:minc=c[i1][j1]8minsum+=minc9 e.lb=e.cost+minsum人员任务0任务1任务2任务309278164372581837694例如：e.i=2人员0已分配任务1人员1已分配任务0minsum=1+4=575/96用bestx数组存放最优分配方案，bestc（初始值为∞）存放最优成本。若一个结点的lb满足lb≥bestc则该路径走下去不可能找到最优解，将其剪支，也就是仅仅扩展满足lb<bestc的结点。76/96i=0，cost=0lb=10x[]={0,0,0,0}798561i=1，cost=9lb=17x[]={0,0,0,0}i=1，cost=2lb=10x[]={1,0,0,0}i=1，cost=7lb=20x[]={2,0,0,0}i=1，cost=8lb=18x[]={3,0,0,0}j=0c[0][0]=9j=1c[0][1]=2j=2c[0][2]=7j=3c[0][3]=82i=2，cost=8lb=13x[]={1,0,0,0}i=2，cost=5lb=14x[]={1,2,0,0}i=2，cost=9lb=17x[]={1,3,0,0}j=0c[1][0]=6j=2c[1][2]=3j=3c[1][3]=7103i=3，cost=9lb=13x[]={1,0,2,0}i=3，cost=16lb=25x[]={1,0,3,0}j=2c[2][2]=1j=3c[2][3]=84i=4，cost=13lb=13x[]={1,0,2,3}j=3c[3][3]=4bestc=1377/961 defEnQueue(e,pqu): #结点e进队操作2globaln,bestx,bestc3ife.i==n: #到达叶子结点4 ife.cost<bestc: #比较更新最优解5 bestc=e.cost6 bestx=copy.deepcopy(e.x)7 else:heapq.heappush(pqu,e) #非叶子结点进队78/969 defbfs(): #优先队列式分支限界算法10 globalc,n,bextx,bestc,sum11 pqu=[]

#定义一个优先队列pqu12 e=QNode()13 e.i,e.cost=0,0 #根结点层次为014 e.x=[-1]*n15 e.used=[False]*n16 bound(e)17 heapq.heappush(pqu,e) #源点结点进队79/9618 whilepqu: #队不空循环19 e=heapq.heappop(pqu) #出队结点e20 sum+=121 forjinrange(0,n): #共n个任务22 ife.used[j]:continue #任务j已分配时跳过23 e1=QNode()24 e1.i=e.i+1 #子结点的层次加125 e1.cost=e.cost+c[e.i][j]26 e1.x=copy.deepcopy(e.x);e1.x[e.i]=j #人e.i分任务j27 e1.used=copy.deepcopy(e.used);e1.used[j]=True28 bound(e1) #求e1的lb29 ife1.lb<bestc: #剪支30 EnQueue(e1,pqu)80/9632 defallocate(c,n): #求解任务分配问题33 globalbestx,bestc,sum34 sum=0 #累计搜索结点个数35 bestx=[-1]*n #最优解向量36 bestc=INF #最优解的成本37 bfs()38 print("求解结果")39 forkinrange(0,n):40 print("人员%d分配任务%d"%(k,bestx[k]))41 print("总成本=%d"%(bestc))42 print("sum=",sum)81/96程序验证人员任务0任务1任务2任务30927816437258183769482/96算法的解空间是排列树，最坏的时间复杂度为O(n×n!)。算法分析83/96问题描述：假设有一个货郎担要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，要求路径长度最短的路径。89736858602135875路径1：0→1→2→3→0：28路径2：0→1→3→2→0：29路径3：0→2→1→3→0：26路径4：0→2→3→1→0：23路径5：0→3→2→1→0：59路径6：0→3→1→2→0：596.4.7货郎担问题84/96解85/96仅仅求以s为起点经过图中所有其他顶点回到起点s的最短路径长度（TSP路径长度）。先不考虑回边，设置bestd数组，bestd[i]表示s经过所有其他顶点到顶点i的最短路径长度。当bestd数组求出后，