算法设计与分析-分支界限法.ppt

1、,第一章 算法概述,第二章 递归与分治策略,第三章 动态规划,第四章 贪心算法,第五章 回朔法,第六章 分支限界法,第七章 概率算法,算法设计与分析 目录,1,1,6.1分支限界法的基本思想,算法设计与分析 分支限界法,2,分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法求解目标：分支限界法找出满足条件的一个解，或某种意义下的最优解分支限界法搜索方式：广度优先或最小耗费优先,2,算法设计与分析 分支限界法,支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一

2、次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点(最有利的)成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,3,3,常见的两种分支限界法,4,算法设计与分析 分支限界法,队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：最大堆，体现最大效益优先最小优先队列：最小堆，体现最小费用优先,从活结点表中选择下一扩展结点的不同

3、方式,4,5,算法设计与分析 分支限界法,6.50-1背包问题,采用优先级队列式分支限界法使用最大堆，堆空算法中止。优先级为价值上界,class HeapNode /堆结点定义 public: double uprofit; /结点的价值上界 double profit; /结点所相应的价值V double weight; /结点所相应的重量w int level; /活结点在子集树中所处的层序号 bbnode *ptr; /指向活结点在子集树中相应结点 /的指针;,算法设计与分析 分支限界法,bbnode /子集树结点定义bbnode *parent; /指向父结点的指针Bool Lchil

4、d; /左儿子结点标志 ,6,算法设计与分析 分支限界法,class Knap private: bbnode *E; /指向扩展结点的指针 double c; /背包容量C int n; /物品总数N double *w; /物品重量W数组 double *p; /物品价值V数组 double cw; /当前装包重量 double cp; /当前装包价值 int *bestx; /最优解，从树根的遍历路径 MaxHeap *H; void AddLiveNode(double up,double cp,double cw,bool ch,int level); double Bound (i

5、nt i);,7,8,优先级的定义：（价值上界）首先将剩余物品依其单位重量价值排序然后依次装入物品，直至无法装入为止再装入该物品的一部分而装满背包例如：n=4,c=7,p=9,10,7,4,w=3,5,2,1这四个物品的单位价值3,2,3.5,4，先装入物品4，然后依次装入3，1，剩余背包容量1，装入0.2个物品2，得到最大价值22，可以证明其价值是最优值上界,算法设计与分析 分支限界法,算法设计与分析 分支限界法,活结点的优先级的定义上界Bound方法：double Bound(int i) double cleft=c-cw; /剩余容量，初始值为当前背包剩余容量 double b=cp;

6、 /价值上界，初始值为当前背包价值 /以物品单位重量价值递减装填剩余容量 while(i分支限界法,将一个新的活结点插入到子集树和优先队列中AddLiveNode(Typep up, Typep cp, Typew cw, boolch, intlev)bbnode*b=newbbnode; /创建新结点,插入子集树b-parent=E;b-LChild=ch;HeapNodeN; /建立堆结点,插入堆中N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H-Insert(N);,算法设计与分析 分支限界法,分支限界搜索函数MaxK

7、napsack，需要使用与回溯法相似的剪枝函数加速搜索过程：左子树判断（可行性约束）：当前背包重量应当小于背包容量， wt = bestp,11,12,MaxKnapsack while (i != n+1) / 非叶结点/ 检查当前扩展结点的左儿子结点 Typew 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) / 右子树可能含最优解 AddLiveNode(up

8、, cp, cw, false, i+1);/ 取下一个扩展节点（略）,算法设计与分析 分支限界法,cw:当前装包重量cp: 当前装包价值bestp:当前最优解,将一个新的活结点插入到子集树和优先队列中i+1: 层数,12,6.2单源最短路径问题,13,算法设计与分析 分支限界法,问题描述有向图G中，每一边都有一个非负权，要求图G的从源顶点s到目标顶点t之间的最短路径。,13,算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,开始：算法从图G的源顶点s和空优先队列开始。遍历:结点s被扩展后，它的儿子结点被依次插入堆中。,14,算法设计与

9、分析 分支限界法,14,15,算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。终止:结点扩展过程一直继续到活结点优先队列为空时为止,算法设计与分析 分支限界法,15,剪枝策略,扩展结点过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。利用结点间的控制关系进行剪枝。若从源顶点s出发，有2条不同路径到达图G的同一顶点。可将路长长的路径所对应的树中的结点为根的子树剪去。,16

10、,算法设计与分析 分支限界法,16,17,17,例如，例中从s出发经边a、e、q（路长5）和经c、h（路长6）的两条路径到达G的同一顶点。,算法设计与分析 分支限界法,18,在解空间树中，这两条路径相应于解空间树的2个不同的结点A和B。由于A的路长较小，故可将以结点B为根的子树剪去。此时称结点A控制了结点B。,算法设计与分析 分支限界法,18,19,while (true) for (int j = 1; j N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) brea

11、k; / 优先队列空,算法设计与分析 分支限界法,顶点i和j间有边，且此路径长小于原先从原点到j的路径,Length: 优先队列的优先级,19,6.3 装载问题,1. 问题描述,有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且,装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。,容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 首先将第一艘轮船尽可能装满；将剩余的集装箱装上第二艘轮船。,20,算法设计与分析 分支限界法,20,21,2. 队列式分支限界法,算法设计与分析 分支限界法,解

12、装载问题仅求出所要求的最优值的队列式分支限界法定义：队列Q存放活结点表，其中元素Ew：表示当前载重量-1：表示队列已到达解空间树同一层结点的尾部方法EnQueue() :将活结点加入到Q队列中方法MaxLoading():对解空间的分支限界搜索,算法设计与分析 分支限界法,private static void enQueue(int wt,int i)/将活结点加入到活结点队列中 if (i=n)/可行叶结点if (wtbestw) bestw=wt;elseQ.Add(wt);,它首先检查i是否等于ni=n：当前活结点为叶结点，则不必加入队列；i分支限界法,算法MaxLoading具体实施

13、对解空间的分支限界搜索过程。初始化的活结点队列为空，增加尾部标志,23,24,while循环搜索子集空间树：检测当前扩展结点的左儿子结点是否为可行结点，如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。(2个儿子结点都产生后，当前扩展结点被舍弃)活结点队列中队首元素取出作为当前扩展结点，如果取出元素为-1，判断当前队列是否为空，如果非空，将尾部标记-1加入活结点队列，处理下一层活结点；否则程序结束。,算法设计与分析 分支限界法,while (true) / 检查左儿子结点 if (Ew + wi 分支限界法,25,3. 算法的改进,剪枝函数定义：

14、bestw是当前最优解；ew是扩展结点所相应的载重量；r是剩余集装箱的重量。当ew+r分支限界法,26,27,改进：为确保右子树成功剪枝，应该在算法每一次进入左子树时更新bestw的值。,问题:算法MaxLoading设置初始时bestw=0，直到搜索到第一个叶结点才更新bestw。在搜索到第一个叶结点前，总有Ew+rbestw, 此时右子树测试不起作用。,算法设计与分析 分支限界法,27,其他改进,算法,/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw / 取下一扩展

15、结点,右儿子剪枝,28,算法设计与分析 分支限界法,28,4. 构造最优解,为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。,class QNode QNode *parent; / 指向父结点的指针 bool LChild; / 左儿子标志 Type weight; / 结点所相应的载重量,29,算法设计与分析 分支限界法,29,找到最优值后，可以根据parent回溯到根节点，找到最优解。,/ 构造当前最优解for (int j = n - 1; j 0; j-) bestxj =

16、bestE-LChild; /bestx存储最优解路径 bestE = bestE-parent; /回溯构造最优解,30,算法设计与分析 分支限界法,30,5. 优先队列式分支限界法,31,算法设计与分析 分支限界法,优先队列表示：最大优先队列优先级：从根结点到当前结点x的路径所对应的载重量加上剩余集装箱的重量之和记为x.uweight特性：结点x为根的子树中所有结点的载重量不超过x.uweight叶结点的载重量即为叶结点的优先级所以只要有一个叶结点成为当前扩展结点，则该结点所对应的解必为最优解。此时可终止算法。,31,32,6.4 布线问题,1、问题描述,算法设计与分析 分支限界法,印刷电

17、路板将布线区域划分为nm个方格阵列。布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。,要求：布线时电路只能沿直线或直角布线。已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。,32,算法思想队列式分支限界法,初始情况从起始位置a开始，作为第一个扩展结点。与该扩展结点相邻并可达的方格，作为可行结点加入到活结点队列中，且将这些方格标记为1，即从起始方格a到这些方格的距离为1。算法从活结点队列中,取出队首结点作为下一个扩展结点，将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。重复步骤，直到算法搜索到目标方格b，或活结点队列为空时为止。,33,算法设计与分析 分支限

18、界法,33,数据表示方格位置类：Position成员row和col：表示行和列定义offset4，表示移动方向,算法设计与分析 分支限界法,34,34,35,算法设计与分析 分支限界法,方格阵列数组：grid记录距离0表示允许布线，1表示封锁。边界通过四周的封锁方格表示，增设方阵的围墙如下：for(int i=0;i分支限界法,36,其他成员变量的定义：,37,算法设计与分析 分支限界法,算法实现,将当前扩展结点按照相邻方格顺序遍历，标记可达相邻方格如果该方格未被标记，更改标记距离；判断该方格是否为目标位置，是则退出循环将方格插入队列判断是否到达目标位置，布线完成判断队列是否为空，如果为空表示

19、无解，算法终止。依次循环取出下一扩展结点,Dofor (int i=0;i分支限界法,38,39,为了构造最短布线路径，需要从目标方格开始向起始方格回溯，逐步构造出最优解。每次向标记距离比当前方格距离少1的相邻方格移动，直至到达起始方格时为止。 初始化：pathLen=gridfinish.rowfinish.col-2; path = new PositionpathLen;/从目标位置开始向起始位置回溯here = finish;,算法设计与分析 分支限界法,构造最优解,for (int j=pathLen-1;j=0;j-) pathj = here; /找前驱结点，从当前位置向4个方向

20、移动 for (int i=0;i分支限界法,40,6.6 最大团问题,1. 问题描述,41,算法设计与分析 分支限界法,完全子图：给定无向图G=(V,E)。如果UV，且对任意u，vU有(u,v)E，则称U是G的完全子图团：当且仅当G的完全子图U不包含在G的更大的完全子图中则U是G的团。最大团:G的最大团是指G中所含顶点数最多的团。,41,2.算法设计解空间：子集树。最大团可看作G的顶点V的子集选取问题。可行性约束函数：顶点i与已选入的顶点集中每一个顶点都有边相连。上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。解决方案：优先级队列式分支限界法,42,算法设计与分析 分支限

21、界法,42,优先级定义,变量定义：cn：当前团的顶点数；level：结点在子集空间树中所处的层次；优先级定义：un=cn+n-level+1表示该结点为根的子树中最大顶点数的上界。,43,算法设计与分析 分支限界法,43,3. 算法思想,初始化：根结点是初始扩展结点，cn=0,算法while循环扩展内部结点，首先考察其左儿子结点。检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。,44,算法设计与分析 分支限界法,44,/搜索子集空间树,非叶子结点while (i!=

22、n+1)/检查顶点i与当前团中其他顶点之间是否有边相连boolean ok = true;BBnode *B =E;for (int j=i-1;j0;B=B-parent,j-)if (B-LChild ,算法设计与分析 分支限界法,45,45,对于子集树中的叶结点，有uncn。（ un是当前团最大顶点数的上界， cn表示当前团的顶点数。 ）此时活结点优先队列中，剩余结点的un值均不超过当前扩展结点的un值。,继续考察当前扩展结点的右儿子结点。当unbestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中,并插入到活结点优先队列中。while循环的终止条件是: 遇到子集树中的一个

23、叶结点(即n+1层结点)成为当前扩展结点。,46,算法设计与分析 分支限界法,46,if (cn+n-i=bestn) /右子树可能含最优解addLiveNode(H,cn+n-i,cn,i+1,E,false);/取一下扩展结点H.DeleteMax(N);E=N.ptr;cn=N.cn;i=node.level; /构造当前最优解for (int j=n;j0;j-)bestxj=E.-LchildE=E-parent;return bestn;,算法设计与分析 分支限界法,47,47,6.7 旅行售货员问题,1. 问题描述,售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。选

24、定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。,48,算法设计与分析 分支限界法,48,49,旅行售货员问题的解空间为一棵排列树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。,算法设计与分析 分支限界法,旅行售货员问题是在图G中找出费用最小的周游路线。,50,实现对排列树搜索的优先队列式分支限界法可以有两种不同的实现方式：（1）用优先队列来存储活结点。优先队列中每个活结点都存储从根到该活结点的相应路径。（

25、2）用优先队列来存储活结点+当前已构造出的部分排列树。优先队列中的活结点不必存储从根到该活结点的相应路径，该路径必要时从存储的部分排列树中获得。,算法设计与分析 分支限界法,50,2. 算法描述,51,算法设计与分析 分支限界法,算法开始时创建一个最小堆，用于表示活结点优先队列。定义：x:当前解s：结点在排列树中的层次，根结点到当前结点的路径为x0:s;进一步搜索的顶点xs+1:n-1cc:当前费用lcost:子树费用的下界（优先级）rcost: 是xs:n-1中顶点最小出边费用和,51,52,算法设计与分析 分支限界法,优先级定义(子树费用的下界) 当前费用+剩余结点的最小出边费用和lcos

26、t=cc+rcostcc=0Rcost=MinSum初始情况循环找出每个顶点的最小出边费用，遍历过程中依次减去当前扩展结点的最小出边费用,static class MinHeapNode implements Comparablefloat lcost,/子树费用的下界cc,/当前费用rcost;/xs:n-1中顶点最小出边费用和int s;/根结点到当前结点的路径为x0:sint *x;/需要进一步搜索的顶点是xs+1,n-1,算法设计与分析 分支限界法,53,class Traveling private: int n; float *a; float NoEdge; float cc;

27、float bestc;public : float BBTSP(int v);,53,54,算法设计与分析 分支限界法,初始化：判断如果图中每个顶点有出边，计算出图中顶点的最小出边费用，用minout记录否则，如果图中某个顶点没有出边，图无回路算法结束。,/计算各顶点的最小出边费用和所有顶点最小出边费用和for(int i=1;i=n;i+) float min=NoEdge; /NoEdge=Float.MAX_VALUEfor(int j=1;j分支限界法,55,MinHeapNode E;E.x=new intn;For(int i=0;i分支限界法,搜索排列空间树，利用while循环

28、完成对排列树内部结点的扩展。当前扩展结点是叶结点的父结点，树层次s=n-2的情形如果该叶结点相应一条可行回路，且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。其他情况，即当排列树层次s分支限界法,57,While(E.s分支限界法,其他情况，即当排列树层次sn-2时，算法依次产生当前扩展结点的所有儿子结点。当前扩展结点所相应的路径是x0: s，其可行儿子结点是从剩余顶点xs+1: n-1中选取的顶点xi，且(xs,xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcost分支限界法,

29、else /产生当前扩展结点的儿子结点for(int i=E.s+1;i分支限界法,if(b N;N.x=new intn;for(int j=0;j分支限界法,61,算法描述,算法用一个最小堆表示活结点优先队列，优先级为当前密度cd开始时，将排列树的根结点置为当前扩展结点。在do-while循环体内，算法依次从活结点优先队列中，取出具有最小当前密度cd值的结点，作为当前扩展结点，并加以扩展。,解空间为一棵排列树，采用优先队列式分支限界法，找出所给电路板的最小密度布局。,62,算法设计与分析 分支限界法,62,63,算法设计与分析 分支限界法,定义数据结构：最小堆中元素类型是BoradNode

30、，域x，表示节点所相应的电路板排列；s表示该节点已确定的部分电路板排列x1:s；cd表示当前密度；nowj表示x1:s中所含连接块j中的电路板数。totali：连接块中i的电路板数Bij：连接块数组,64,算法将当前扩展结点分为两种情形处理：,（1）s=n-1的情形：此时已排定n-1块电路板，故当前扩展结点是排列树中的一个叶结点的父结点。计算出最后一块电路板的密度(如果电路板i在连接块Nj中 )如果存在更小密度的电路板排列，更新当前最优值（max(当前节点的密度,最后一块电路板的密度)）和相应的当前最优解。,算法设计与分析 分支限界法,64,算法描述,do / 结点扩展 if (E.s = n - 1) / 仅一个儿子结点(还有一块未排定) int ld = 0; / 最后一块电路板的密度 for (int j = 1; j = m; j+) /m为连接块数 ld += BE.xnj; /如果电路板i在连接块Nj中 ,即Bi j=1 if (ld 分支限界法,S=n-1的情况，计算出此时的密度和bestd进行比较。,65,66,（2）当s 0 当N.cd分支限界法,