第六部分分支限界法.ppt

1、第六章 分支限界法(Branch and Bound),什么是分支限界法？,8-puzzle problem,an 8-puzzle initial arrangement,the goal state of the 8-puzzle problem,3,3,3,4,4,2,4,1,0,2,Greedy method: the number of misplaced tiles,分支限界法的搜索策略,分支限界法以广度优先或最小耗费/最大效益优先的方式搜索解空间树。 在扩展结点处，先生成其所有的儿子结点（分支），在每一个活结点处，估算目标函数的界（限界），并根据这些已计算出的函数值，从当前活结点

2、表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进。当一个叶结点成为扩展结点时(此时活结点表中其他结点的函数值均不超过该叶结点的函数值)，该叶结点相应的解即为问题的最优解。,在使用分支限界法解具体问题时，可以采用下面两种典型方式实现活结点表 队列式分支限界（先进先出） 优先队列式分支限界,队列式： 活结点表L=(2,3,4),优先队列式： 活结点表L=(2,3,4按限界函数值确定优先级)，即哪个分支能够花最小代价找到最优解？,TSP问题,某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的

3、路程(或总旅费)最小。 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。,队列式 优先队列式：确定活结点优先队列的优先级 子树的下界 已确定的边的费用之和+未确定的边的费用之和的下界 即当前费用+未确定的每个顶点的最小出边费用之和,能否预判这棵子树无法获得最优解？,/初始化。s：结点在排列树中的层次，cc：当前费用，rcost：xs:n-1中顶点最小出边费用和， bestc：当前最优值 s=0;x0=1;x1:n-1=(2,3,n);cc=0;rcost=Minout1+Minout2+Minoutn

4、 bestc=NoEdge /搜索排列树 While 当前扩展结点非叶结点 if 当前扩展结点是叶结点的父结点 if 叶结点存在一条可行回路且费用小于当前最优解 bestc = 该回路的费用 else 舍弃扩展结点 else 产生当前扩展结点的儿子结点 for i=s+1 to n do 更新可行儿子结点的状态：cc, rcost b = cc + rcost /子树的下界 if b bestc /子树可能含最优解 将结点插入活结点优先队列（最小堆） / 取下一扩展结点,A,B,C,D,E,H,I,F,G,x0=1,初始化：bestc=NoEdge，产生第一个叶结点后更新,x1=2,x1=3,

5、x1=4,活结点优先队列,x2=2,x2=3,x2=2,x2=4,C,J,bestc=cc=25,C,x3=3 cc=25 bestc=25,x3=4,叶结点的父结点作判断：回路？最优？,cc=0 rcost=18,cc=30 rcost=14,cc=4 rcost=14,cc=6 rcost=14,cc=11 rcost=9,cc=26 rcost=9,cc=24 rcost=10,cc=14 rcost=10,0-1背包问题,n=3, w=16,15,15, v=45,25,25, c=30 优先队列式：优先级定义为活结点所获得的价值,0,1,2,3,5,6,45,4,7,8,9,10,4

6、5,50,25,25,0,0,45,25,0,进一步改进 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 节点的优先级由上界函数来决定，即已装袋的物品价值+剩下的最大单位重量价值的物品装满剩余容量的价值和。 解空间树的搜索 首先检查当前扩展结点的左儿子结点(xi=1)的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。 当前扩展结点的右儿子结点(xi=0)一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。 当扩展到叶结点时为问题的最优值。,Bound (i) /计算结点的价值上界 cleft = c - cw / 剩

7、余容量 bound = cp /以物品单位重量价值递减序装入物品 while i cleft时装满背包 if i = n bound = bound + pi / wi * cleft return bound,/初始化 cw=cp=0; bestp=0 up=bound(1) /搜索子集树 while i != n + 1 do /非叶结点 wt = cw + wi if wt bestp bestp = cp + pi addLiveNode(up, cp + pi, cw + wi, true, i + 1) up = bound(i + 1) if up = bestp /右儿子结点满

8、足上界约束(可能含有最优解) addLiveNode(up, cp, cw, false, i + 1) /取下一个扩展节点,E,i,cw, cp, up,xi=1,l,r,xi=0,按up值非递增排列,活结点 优先队列,cw+wi, cp+pi, up,cw, cp, up,/构造最优解 for j=n to 1 do bestxj = E - LChild E = E - parent,b - parent = E / E：当前扩展结点 b - LChild = true / xi = 1,b - parent = E b - LChild = false / xi =0,n=5, c=5

9、0, v=12, 30, 44, 46, 50, w=5, 15, 25, 27, 30, v/w=2.4, 2, 1.76, 1.7, 1.6,0,cw=0,cp=0,94.5,活结点优先队列,8,8,8,初始化：bestp=0 up=bound(1),电路布线,印刷电路板将布线区域划分成nm个方格阵列。精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。 在布线时，电路只能沿直线或直角布线。 为了避免线路相交，已布了线的方格作了封锁标记，其他线路不允许穿过被封锁的方格。,队列式分支限界法 解空间：图 将起始位置a作为第一个扩展结点，与该扩展结点相邻且可达的方格成为可行结点被

10、加入到活结点队列中（右下左上），并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。 接着，从活结点队列中取出对首结点作为下一个扩展结点,算法具体实现 “围墙”，用于处理边界 “0”表示方格开放，“1”表示方格封锁 起始位置的距离标记为2，实际距离为标记距离减2 算法分析 活结点队列中最多只处理O(mn)个活结点。扩展每个结点需O(1)，因此共需O(mn)。构造解需O(L)时间，L是最短路径的长度。,堆,n个元素的序列k1,k2,kn，当且仅当满足下述关系时，称之为堆。,或,i=1,2,n/2,单源最短路经,有向图G中，每一边都有一个非负边权。求图G的从源顶点s到目标顶点t之间的最短路

11、径。,2,3,4,9,4,5,7,6,8,12,124,65,107,87,98,148,53,0,剪枝：结点间的控制关系。从s出发，经过两条不同路径到达同一顶点，这两条路径相应于解空间树的2个不同的结点A和B，如果结点A所相应的路长小于结点B所相应的路长，则可以将结点B为根的子树剪去，称结点A控制了结点B。 优先队列中结点的优先级：结点所对应的当前路长。,/找出从源顶点s到所有其他顶点之间的最短路径 While (true) /搜索问题的解空间，E为当前扩展结点 for j=1 to n do /顶点i到顶点j可达，且满足控制约束 if (cE.ij ) and (E.length + cE

12、.ij distj) distj = E.length + cE.ij prevj = E.i 加入活结点优先队列 取下一扩展结点 直到队列为空,i,j,E.length,cE.ij,j,distj,distj是否更新？,最大团问题,给定一个无向图G=(V,E)。如果U包含于V，且对任意u,v属于U有(u,v)属于E，则称U是G的一个完全子图。G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 例如，子集1,2是G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图1,2,5中。1,2,5、1,4,5和2,3,5都是G的最

13、大团。,解最大团问题与解装载问题是相似的。 图G的顶点集V的子集选取问题 子集树 剪枝 左子树：从顶点i到已选入的顶点集中每一个顶点都有边，否则剪枝 右子树：顶点数上界小于当前最优值时剪枝 （当前扩展结点）顶点数上界=已确定的顶点数+未确定的顶点数的上界 优先队列中结点的优先级 顶点数上界,练习,0,1,2,x1,1,0,1+4,bestn,0+4,3,4,x2,2+3,bestn,1+3,5,x3,2+2,6,7,1+3,0+3,9,1+2,10,2+1,11,12,2+2,1+2,13,2+1,装载问题,实质是求第一艘船的最优装载。该问题是一个子集选取问题，子集树。 剪枝 考察左子树的可行性：是否满足约束条件。 考察右子树的最优性：（当前扩展结点）重量上界当前最优值时，剪