算法分析与设计第6章详解.ppt

《算法分析与设计第6章详解.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计第6章详解.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 分支限界法 Branch and Bound 1主要内容n6.1 分支限界法的基本思想分支限界法的基本思想n6.2 单源最短路径问题单源最短路径问题n6.3 装载问题装载问题n6.4 0-1背包问题背包问题26.1 分支限界法的基本思想分支限界法的基本思想nBreadth-first search n分支限界法与回溯法分支限界法与回溯法（1）求解目标求解目标：回溯法的求解目标是找出解空间树：回溯法的求解目标是找出解空间树中满足约束条件的中满足约束条件的所有解所有解，而分支限界法的求解，而分支限界法的求解目标则是找出满足约束条件的目标则是找出满足约束条件的一个解一个解，或是在满，或是在满

2、足约束条件的解中找出在某种意义下的足约束条件的解中找出在某种意义下的最优解最优解。（2）搜索方式的不同搜索方式的不同：回溯法以：回溯法以深度优先的方式深度优先的方式搜搜索解空间树，而分支限界法则以索解空间树，而分支限界法则以广度优先或以最广度优先或以最小耗费优先的方式小耗费优先的方式搜索解空间树。搜索解空间树。6.1分支限界法的基本思想分支限界法的基本思想3分支限界法的搜索策略分支限界法的搜索策略在扩展结点处，先生成其所有的儿子结点（分支），在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。然后再从当前的活结点表中选择下一个扩展结点。为了有效的选择下一扩

3、展结点，以加速搜索的进程，为了有效的选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值，并根据这些已在每一活结点处，计算一个函数值，并根据这些已计算出的函数值，从当前活结点表中选择一个最有计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解最优解的分支推进，以便尽快地找出一个最优解。6.1分支限界法的基本思想分支限界法的基本思想4w=16,15,15,v=45,25,25,c=306.1分支限界法的基本思想分支限界法的基本思想5分支限界法的基本思想分支限界法

4、的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。优先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或续到找到所需的解或活结点表为空时为止活结点表为空时为止。在分支限界法中，每一个活结点在分支限界法中，每一个活结点只有一次机会只有一次机会成成为扩展结点。活结点一旦成为扩展结点，就为扩展结点。活结点一旦成为扩展结点，就一次一次性产生其所有儿子结点性产生

5、其所有儿子结点。在这些儿子结点中，导。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。其余儿子结点被加入活结点表中。6.1分支限界法的基本思想分支限界法的基本思想6常见的两种分支限界法常见的两种分支限界法n队列式队列式(FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFO）原则选取下一原则选取下一个节点为扩展节点。个节点为扩展节点。n优先队列式优先队列式(priority queue)分支限界法分支限界法 按照优先队列中规定的优先级选取优先级按照优先队列中规定的优先级选取优先级最高的节

6、点成为当前扩展节点。最高的节点成为当前扩展节点。6.1分支限界法的基本思想分支限界法的基本思想7n例：考虑例：考虑n=3 时时0-1背包问题的一个实例如下：背包问题的一个实例如下：w=16,15,15,p=45,25,25,c=30。其子集树。其子集树6.1分支限界法的基本思想分支限界法的基本思想8用用队列式队列式分支限界法解此问题分支限界法解此问题n队列式分支限界法搜索解空间树的方式与队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为相似，解空间树的广度优先遍历算法极为相似，唯一的不同之处是队列式分支限界法不搜唯一的不同之处是队列式分支限界法不搜索以不可行结点为根的子树。索以

7、不可行结点为根的子树。6.1分支限界法的基本思想分支限界法的基本思想9队列式队列式0活结点队列活结点队列B，C160C，E16F，G1504516G30501525152500E，F，G6.1分支限界法的基本思想分支限界法的基本思想w=16,15,15,p=45,25,25,c=3010用优先队列式分支限界法解此问题用优先队列式分支限界法解此问题n也是从根结点也是从根结点A开始搜索解空间树，用一个开始搜索解空间树，用一个极大堆来表示活结点表的优先队列，该优先极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结点所获得的价值。队列的优先级定义为活结点所获得的价值。初始时堆为空。初始时堆为

8、空。0450452504550252500454545025502502506.1分支限界法的基本思想分支限界法的基本思想w=16,15,15,p=45,25,25,c=3011n优先队列中规定的结点优先级常用一个与优先队列中规定的结点优先级常用一个与该结点相关的数值该结点相关的数值p来表示，结点优先级来表示，结点优先级的高低与的高低与p值的大小相关，最大优先队列值的大小相关，最大优先队列规定规定p值较大的结点优先级较高，用值较大的结点优先级较高，用大堆大堆来实现。来实现。小优先队列规定小优先队列规定p值较小的结点优先级较值较小的结点优先级较高，用高，用小堆小堆来实现。来实现。6.1分支限界法

9、的基本思想分支限界法的基本思想12n当寻求问题的一个最优解时，可以用剪枝函数来当寻求问题的一个最优解时，可以用剪枝函数来加速搜索，该函数给出每一个可行结点相应的子加速搜索，该函数给出每一个可行结点相应的子树可能获得的树可能获得的最大价值的上界最大价值的上界。如果这个上界不。如果这个上界不会比当前最优值更大，则说明相应的子树中不含会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去，问题的最优解，因而可以剪去，n另一方面，我们也可以将上界函数确定的每个结另一方面，我们也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽点的上界值作为优先级，以该优先级的非增序抽取

10、当前扩展结点，这种策略有时可以更迅速地找取当前扩展结点，这种策略有时可以更迅速地找到最优解。到最优解。6.1分支限界法的基本思想分支限界法的基本思想131234306102054ABCDEFGHIJKLMNOPQ1234344324422332B C,D,ED,E,F,GE,F,G,H,IF,G,H,I,J,KG,H,I,J,K59H,I,J,K66I,J,K25J,KK队列6.1分支限界法的基本思想分支限界法的基本思想141234306102054ABCDEFGHIJKLMNOPQ1234344324422332B，0C,30D,6优先队列E,4J,14K,24H,11I,26256.1分支

11、限界法的基本思想分支限界法的基本思想156.2 单源最短路径 算法思想算法思想 解单源最短路径问题的解单源最短路径问题的优先队列式分支限界法优先队列式分支限界法用一用一极小堆来存储活结点表。其优先级是结点所对应的当前极小堆来存储活结点表。其优先级是结点所对应的当前路长。路长。算法从图算法从图G G的源顶点的源顶点s s和空优先队列开始。结点和空优先队列开始。结点s s被扩展后，被扩展后，它的儿子结点被依次插入堆中。它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。前扩展

12、结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点如果从当前扩展结点i i到顶点到顶点j j有边可达，且从源出发，有边可达，且从源出发，途经顶点途经顶点i i再到顶点再到顶点j j的所相应的路径的的所相应的路径的长度小于长度小于当前最优路当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时这个结点的扩展过程一直继续到活结点优先队列为空时为止。为止。6.2单源最短路径单源最短路径16剪枝策略在在算算法法扩扩展展结结点点的的过过程程中中，一一旦旦发发现现一一个个结结点点的的下

13、下界界不不小小于于当当前前找找到到的的最最短短路路长长，则则算算法法剪剪去去以以该该结结点点为为根的子树。根的子树。在在算算法法中中，利利用用结结点点间间的的控控制制关关系系进进行行剪剪枝枝。从从源源顶顶点点s s出出发发，2 2条条不不同同路路径径到到达达图图G G的的同同一一顶顶点点。由由于于两两条条路路径径的的路路长长不不同同，因因此此可可以以将将路路长长长长的的路路径径所所对对应应的树中的结点为根的子树剪去。的树中的结点为根的子树剪去。6.2单源最短路径单源最短路径176.2单源最短路径单源最短路径18templateclass Graph friend void main(void)

14、;public:void ShortestPaths(int);private:int n,*prev;/前驱顶点数组前驱顶点数组 Type*c,/图图G的邻接矩阵的邻接矩阵 *dist;/最短距离数组最短距离数组;templateclass MinHeapNode friend Graph;public:operator int()const return length;private:int i;/顶点编号顶点编号 Type length;/当前路长当前路长;6.2单源最短路径单源最短路径19templatevoid Graph:ShortestPaths(int v)/单单源最短路径源最

15、短路径问题问题的的优优先先队队列式分支限界法列式分支限界法 /定定义义最小堆的容量最小堆的容量为为1000 MinHeap MinHeapNode H(1000);/定定义义源源为为初始初始扩扩展展结结点点 MinHeapNode E;E.i=v;E.length=0;dist v =0;/搜索搜索问题问题的解空的解空间间6.2单源最短路径单源最短路径20 while(true)for(int j=1;j=n;j+)/寻找寻找E的下一个结点的下一个结点 if(cE.ijinf)&(E.length+cE.ijdistj)/顶点顶点i到顶点到顶点j可达，且满足控制约束可达，且满足控制约束 dis

16、tj=E.length+cE.ij;prevj=E.i;/加入活结点优先队列加入活结点优先队列 MinHeapNode N;N.i=j;N.length=distj;H.Insert(N);try H.DeleteMin(E);/取下一扩展结点，距源点最近取下一扩展结点，距源点最近 catch(OutOfBounds)break;/优先队列空优先队列空 6.2单源最短路径单源最短路径21while 循环体完成对解空间内部结点的扩展，对于当前节结点，算法依次检查与当前扩展节点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到j的所有相应的路径长度小于当前最优路径长度

17、，则将点j插入到活结点优先队列中。226.2装载问题装载问题1.问题描述问题描述有有一一批批共共n n个个集集装装箱箱要要装装上上2 2艘艘载载重重量量分分别别为为c1c1和和c2c2的的轮轮船，其中集装箱船，其中集装箱i i的重量为的重量为W Wi i，且且装载问题要求确定是否有一个合理的装载方案可将这些装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这集装箱装上这2 2艘轮船。如果有，找出一种装载方案。艘轮船。如果有，找出一种装载方案。容容易易证证明明：如如果果一一个个给给定定装装载载问问题题有有解解，则则采采用用下下面面的的策略可得到最优装载方案。策略可得到最优装载方案。(1)

18、(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。6.3装载问题装载问题2301631163116015300151506.3装载问题装载问题2411116011601631163116015300151501501601116150活结点队列活结点队列扩展结点扩展结点2.队列式分支限界法队列式分支限界法6.3装载问题装载问题25算法思想算法思想 用用一一个个队队列列Q来来存存放放活活结结点点表表，Q中中weight表表示示每每个个活活结结点点所所相相应应的的当当前前载载重重量量。当当weight1时时，表表示

19、示队队列列已已达达到解空间树到解空间树同一层结点的尾部同一层结点的尾部。算算法法首首先先检检测测当当前前扩扩展展结结点点的的左左儿儿子子结结点点是是否否为为可可行行结结点点。如如果果是是则则将将其其加加入入到到活活结结点点队队列列中中。然然后后将将其其右右儿儿子子结结点点加加入入到到活活结结点点队队列列中中(右右儿儿子子结结点点一一定定是是可可行行结结点点)。2个个儿儿子子结点都产生后，当前扩展结点被舍弃。结点都产生后，当前扩展结点被舍弃。活活结结点点队队列列中中的的队队首首元元素素被被取取出出作作为为当当前前扩扩展展结结点点，由由于于队队列列中中每每一一层层结结点点之之后后都都有有一一个个尾

20、尾部部标标记记-1，故故在在取取队队首首元元素素时时，活活结结点点队队列列一一定定不不空空。当当取取出出的的元元素素是是-1时时，再再判判断断当当前前队队列列是是否否为为空空。如如果果队队列列非非空空，则则将将尾尾部部标标记记-1加加入入活活结点队列，算法开始处理下一层的活结点。结点队列，算法开始处理下一层的活结点。6.3装载问题装载问题26n该算法包含两个函数该算法包含两个函数MaxLoading函数具体实施对解空间的分支限函数具体实施对解空间的分支限界搜索。界搜索。EnQueue用于将活结点加入到活结点队列中，用于将活结点加入到活结点队列中，该函数首先检查该函数首先检查i是否等于是否等于n

21、，如果，如果i=n，则表示，则表示当前活结点为一个叶结点，由于叶结点不会被当前活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，如果该进一步扩展，因此不必加入到活结点，如果该叶结点表示的可行解优于当前最优解，更新最叶结点表示的可行解优于当前最优解，更新最优解。当优解。当in时，当前活结点是一个内部结点，时，当前活结点是一个内部结点，加入到活结点队列中。加入到活结点队列中。6.3装载问题装载问题27templateT MaxLoading(T w,T c,int n)/返回最优装载值返回最优装载值 /为层次为层次1 初始化初始化 Queue Q;/活结点队列活结点队列 Q.A

22、dd(-1);/标记本层的尾部标记本层的尾部 int i=1;/当前扩展结点的层当前扩展结点的层 T Ew=0,/当前扩展结点的权当前扩展结点的权值值 bestw=0;/目前的最优值目前的最优值while(true)/检查左孩子结点检查左孩子结点 if(Ew+wi=c)/xi=1 EnQueue(Q,Ew+wi,bestw,i,n);/右孩子总是可行的右孩子总是可行的 EnQueue(Q,Ew,bestw,i,n);/xi=0 Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点 if(Ew=-1)/到达层的尾部到达层的尾部 if(Q.IsEmpty()return bestw;Q.A

23、dd(-1);/同层结点的尾部同层结点的尾部 Q.Delete(Ew);/取下一扩展结点取下一扩展结点 i+;/进入下一层进入下一层 28templatevoid EnQueue(Queue&Q,T wt,T&bestw,int i,int n)/该函数负责加入活结点该函数负责加入活结点/如果不是叶结点，则将结点权值如果不是叶结点，则将结点权值w t加入队列加入队列Q if(i=n)/叶子叶子 if(wt bestw)bestw=wt;else Q.Add(wt);/不是叶子不是叶子6.3装载问题装载问题293.算法的改进算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将节点的左子树表

24、示将此集装箱装上船，右子树表示不将此集装箱装上船。设此集装箱装上船。设bestw是当前最优解；是当前最优解；Ew是当前扩是当前扩展结点所相应的重量；展结点所相应的重量；r是剩余集装箱的重量。则当是剩余集装箱的重量。则当Ew+r bestw时，可将其右子树剪去，因为此时若要船时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船装最多集装箱，就应该把此箱装上船。算法算法MaxLoading初始时将初始时将bestw置为置为0，直到搜索到第，直到搜索到第一个叶结点时才更新一个叶结点时才更新bestw。因此在算法搜索到第一个叶。因此在算法搜索到第一个叶结点之前，总有结点之前，总有bes

25、tw0，r0，故，故Ew+rbestw总是成总是成立，也就是说，此时右子树测试不起作用。立，也就是说，此时右子树测试不起作用。算法中结点相应的重量仅在搜索进入左子树时增加，因算法中结点相应的重量仅在搜索进入左子树时增加，因此，可以在算法每一次进入左子树时更新此，可以在算法每一次进入左子树时更新bestw的值。的值。6.2装载问题装载问题301116011601631163116015300151501516011161516.3装载问题装载问题31n使用限界函数进行改进使用限界函数进行改进T MaxLoading(T w,T c,int n)Queue Q;/活节点队列活节点队列 Q.Add(

26、-1);/标记本层的尾部标记本层的尾部 int i=1;/当前扩展节点的层当前扩展节点的层 T Ew=0,/当前扩展节点的重量当前扩展节点的重量 bestw=0;/目前的最优值目前的最优值 r=0;/当前扩展节点中余下的重量当前扩展节点中余下的重量 for(int j=2;j=n;j+)r+=wi;6.3装载问题装载问题32while(true)/检查扩展结点的左孩子检查扩展结点的左孩子 T wt=Ew+wi;/左孩子的权值左孩子的权值 if(wt bestw)bestw=wt;/若不是叶子，则添加到队列若不是叶子，则添加到队列 if(i bestw&i n)Q.Add(Ew);/可能含最优解

27、可能含最优解 Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点 if(Ew=-1)/到达层的尾部到达层的尾部 if(Q.IsEmpty()return bestw;Q.Add(-1);/添加尾部标记添加尾部标记 Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点 i+;r-=wi;6.3装载问题装载问题34 为了在算法结束后能方便地构造出与最优值相为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置到根结点的路径。为此目的，可在每个结点处设置指向其父结点

28、的指针，并设置左、右儿子标志。指向其父结点的指针，并设置左、右儿子标志。templateclass QNode QNode*parent;/指向父结点的指针指向父结点的指针 bool LChild;/左儿子标志左儿子标志 Type weight;/结点所相应的载重量结点所相应的载重量;4.构造最优解构造最优解6.3装载问题装载问题35016311631160153001515000false16false015true016true6.3装载问题装载问题36优先队列式分支限界法优先队列式分支限界法存储活结点的方式存储活结点的方式:最大优先队列存储活结点表。最大优先队列存储活结点表。活结点活结点

29、x在优先队列中的优先级定义在优先队列中的优先级定义:从根结点到结点从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。的路径所相应的载重量再加上剩余集装箱的重量之和。扩展结点的选择：扩展结点的选择：优先队列中优先级最大的活结点成优先队列中优先级最大的活结点成为下一个扩展结点。以结点为下一个扩展结点。以结点x为根的子树中所有结点相为根的子树中所有结点相应的路径的载重量应的路径的载重量不超过它的优先级不超过它的优先级x.uweight。子集。子集树中树中叶结点叶结点所相应的载重量与其优先级相同。所相应的载重量与其优先级相同。算法终止条件：算法终止条件：子集树中叶结点所相应的载重量与其子

30、集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止可以断言该叶结点所相应的解即为最优解。此时可终止算法。算法。6.3装载问题装载问题如何证明？如何证明？37可以用两种不同方式来实现n在结点优先队列的每一个活结点中保存从解空间树的在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。的叶结点时，就在该叶结点处同时得到相应的最优解。n在算法的搜索

31、进程中保存当前已构造出的在算法的搜索进程中保存当前已构造出的部分解空间部分解空间树树，这样在算法确定了达到最优值的叶结点时，就可，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。出相应的最优解。6.2装载问题装载问题38优先队列优先队列解空间树解空间树w=16,15,15 r3=0,r2=15,r1=30两种结构：子集树结点结构，大堆结点结构两种结构：子集树结点结构，大堆结点结构462i=1E=0truefalse302i=2Ew=16Efalse313i=3Ew=16Efalse164Ei=

32、2Ew=0true303Ei=3Ew=15true304154falsei=4Ew=30E6.3装载问题装载问题找到最优解找到最优解 3039用一个元素类型为用一个元素类型为HeapNode的的最大堆最大堆来表示活结点优先队列。来表示活结点优先队列。解空间树中结点类型为解空间树中结点类型为bbnode。template class HeapNode;class bbnode friend void AddLiveNode(MaxHeap HeapNode&,bbnode*,int,bool,int);friend int MaxLoading(int*,int,int,int*);friend

33、 class AdjacencyGraph;private:bbnode*parent;/指向父结点的指针指向父结点的指针 bool LChild;/左儿子结点标志左儿子结点标志;40用一个元素类型为用一个元素类型为HeapNode的的最大堆最大堆来表示活结点优先队列。来表示活结点优先队列。解空间树中结点类型为解空间树中结点类型为bbnodetemplateclass HeapNode friend void AddLiveNode(MaxHeap HeapNode&,bbnode*,Type,bool,int);friend Type MaxLoading(Type*,Type,int,in

34、t*);public:operator Type()const return uweight;private:bbnode*ptr /指向活结点在子集树中相应结点的指针指向活结点在子集树中相应结点的指针 Type uweight;/活结点优先级（上界）活结点优先级（上界）int level;/活结点在子集树中所处的层序号活结点在子集树中所处的层序号 ；41函数函数AddLiveNode以结点元素类型以结点元素类型bbnode将一个新产生的活结将一个新产生的活结点加入到子集树中，并以结点元素类型点加入到子集树中，并以结点元素类型HeapNode将这个新结将这个新结点插入到表示活结点优先队列的最大

35、堆中。点插入到表示活结点优先队列的最大堆中。templatevoid AddLiveNode(MaxHeap HeapNode&H,bbnode*E,Type wt,bool ch,int lev)/将活结点加入到表示活结点优先队列的最大堆将活结点加入到表示活结点优先队列的最大堆H中中 bbnode*b=new bbnode;b-parent=E;b-LChild=ch;HeapNode N;N.uweight=wt;N.level=lev;N.ptr=b;H.Insert(N);向子集树中向子集树中添加结点添加结点向活结点优向活结点优先队列插入先队列插入新结点新结点42n函数函数MaxLoa

36、ding具体实施对解空间的优先队列式分具体实施对解空间的优先队列式分支限界搜索，在函数中，定义最大堆的容量为支限界搜索，在函数中，定义最大堆的容量为1000，即在运行期间，最多容纳，即在运行期间，最多容纳1000个结点。个结点。n第第i+1层结点的剩余重量层结点的剩余重量ri定义为第定义为第i+1到第到第n个物品个物品重量的和。重量的和。n变量变量E指向子集树中当前扩展结点，指向子集树中当前扩展结点，Ew是相应的重是相应的重量。算法开始时，量。算法开始时，i=1,Ew=0，子集树的根结点为扩，子集树的根结点为扩展结点。展结点。6.2装载问题装载问题43templateType MaxLoadi

37、ng(Type w,Type c,int n,int bestx)/优先队列式分支限界法，返回最优载重量，优先队列式分支限界法，返回最优载重量，bestx返回最优解返回最优解 /定义最大堆的容量为定义最大堆的容量为1000 MaxHeap HeapNode H(1000);/定义剩余重量数组定义剩余重量数组r Type*r=new Type n+1;r n =0;for(int j=n-1;j 0;j-)r j=r j+1 +w j+1;/初始化初始化 int i=1;/当前扩展结点所处的层当前扩展结点所处的层 bbnode*E=0;/当前扩展结点当前扩展结点 Type Ew=0;/扩展结点所

38、相应的载重量扩展结点所相应的载重量 44 while(i!=n+1)/非叶结点非叶结点 /检查当前扩展结点的儿子结点检查当前扩展结点的儿子结点 if(Ew+w i =c)/左儿子结点为可行结点左儿子结点为可行结点 AddLiveNode(H,E,Ew+w i +r i,true,i+1);/end if AddLiveNode(H,E,Ew+r i,false,i+1);/右儿子结点右儿子结点/取下一扩展结点取下一扩展结点 HeapNode N;H.DeletMax(N);/非空非空 i=N.level;E=N.ptr;Ew=N.uweight r i-1;/优先权优先权uweight=Ew+

39、r i-1;/end while for(int j=n;j 0;j-)/构造当前最优解构造当前最优解 bestx j =E-LChild;E=E-parent;/end for return Ew;45优先队列优先队列解空间树解空间树w=16,15,15 r n =0;for(int j=n-1;j 0;j-)r j=r j+1 +w j+1;r3=0,r2=15,r1=30if(Ew+w i =c)AddLiveNode(H,E,Ew+w i +r i,true,i+1);AddLiveNode(H,E,Ew+r i,false,i+1);HeapNode N;H.DeletMax(N);

40、i=N.level;E=N.ptr;Ew=N.uweight r i-1;462i=1E=0truefalse302i=2Ew=16Efalse313i=3Ew=16Efalse164Ei=2Ew=0true303Ei=3Ew=15true304154falsei=4Ew=30E6.2装载问题装载问题46truefalsefalsefalsetruetruefalseEfor(int j=n;j 0;j-)/构造当前最优解构造当前最优解 bestx j =E-LChild;E=E-parent;bestx3=truebestx2=truebestx1=falseEE6.3装载问题装载问题470

41、-1背包问题背包问题6.4 0-1背包问题背包问题48采用优先队列式分支限界采用优先队列式分支限界n活结点优先队列中结点元素活结点优先队列中结点元素N的优先级由该的优先级由该结点的上界函数结点的上界函数Bound计算出的值计算出的值uprofit给给出。出。n以结点以结点N为根的子树中任一结点的价值不超为根的子树中任一结点的价值不超过过N.profit。6.4 0-1背包问题背包问题49nclass Object :描述物品描述物品nclass bbnode:子集树结点子集树结点 nclass HeapNode:优先队列结点优先队列结点nclass Knap:对整个问题的初始化及调用其它函数解

42、决问题对整个问题的初始化及调用其它函数解决问题nKnap:Bound(i):计算第计算第i层结点相应价值的上界层结点相应价值的上界nKnap:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int level);)将一个新的活结点插入到子集树和最大堆将一个新的活结点插入到子集树和最大堆H中中nKnap:MaxKnapsack():优先队列式分支限界法优先队列式分支限界法6.4 0-1背包问题背包问题50class Object friend int Knapsack(int*,int*,int,int,int*);public:int operat

43、or=a.d);private:int ID;float d;/单位重量价值单位重量价值template class Knap;class bbnode /子集空间树中结点类型子集空间树中结点类型 friend Knap;friend int Knapsack(int*,int*,int,int,int*);private:bbnode*parent;/指向父结点的指针指向父结点的指针 bool LChild;/左儿子结点标志左儿子结点标志;6.4 0-1背包问题背包问题51templateclass HeapNode friend Knap;public:operator Typep()co

44、nst return uprofit;private:Typep uprofit,/结点的价值上界结点的价值上界 profit;/结点所相应的价值结点所相应的价值 Typew weight;/结点所相应的重量结点所相应的重量 int level;/活结点在子集树中所处的层序号活结点在子集树中所处的层序号 bbnode*ptr;/指向活结点在子集树中相应结点的指针指向活结点在子集树中相应结点的指针;6.4 0-1背包问题背包问题52template class Knap friend Typep Knapsack(Typep*,Typew*,Typew,int,int*);public:Type

45、p MaxKnapsack();private:MaxHeapHeapNode*H;Typep Bound(int i);void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int level);bbnode*E;/指向扩展结点的指针指向扩展结点的指针 Typew c;/背包容量背包容量 int n;/物品总数物品总数 Typew*w;/物品重量数组物品重量数组 Typep*p;/物品价值数组物品价值数组 Typew cw;/当前装包重量当前装包重量 Typep cp;/当前装包价值当前装包价值 int*bestx;/最优解最优解；6.4 0

46、-1背包问题背包问题53函数函数MaxKnapsack实施对于子集树的优先队列式实施对于子集树的优先队列式分支限界搜索分支限界搜索templateTypep Knap:MaxKnapsack()/优先队列式分支限界法，返回最大价值，优先队列式分支限界法，返回最大价值，bestx返回最优解返回最优解 /定义最大堆的容量为定义最大堆的容量为1000 H=new MaxHeap HeapNode(1000);/为为bestx分配存储空间分配存储空间 bestx=new int n+1;/初始化初始化 int i=1;E=0;cw=cp=0;Typep bestp=0;/当前最优值当前最优值 Type

47、p up=Bound(1);/价值上界价值上界54/搜索子集空间树搜索子集空间树 while(i!=n+1)/非叶结点非叶结点 /检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt=cw+wi;if(wt bestp)bestp=cp+p i;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=Bound(i+1);/检查当前扩展结点的右儿子结点检查当前扩展结点的右儿子结点 if(up=bestp)/右子树可能含最优解右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1);6.4 0-1背包问题背包问题while

48、while 循环内部，算法首先检查循环内部，算法首先检查当前扩展结点的左儿子结点的可当前扩展结点的左儿子结点的可行性。如果可行，则加入子集树行性。如果可行，则加入子集树和活结点优先队列中。和活结点优先队列中。当前扩展结点的右儿子一定可行，仅当前扩展结点的右儿子一定可行，仅当右儿子满足上界约束时才将它加入当右儿子满足上界约束时才将它加入子集树和活结点优先队列。子集树和活结点优先队列。55/取下一扩展结点取下一扩展结点 HeapNode N;H-DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit;i =N.level;/构造当前最优解

49、构造当前最优解for(int=n;j0;j-)bestx j =E-LChild;E=E-parent;return cp;6.4 0-1背包问题背包问题56上界函数上界函数Bound计算结点所相应价值的上界计算结点所相应价值的上界 template Typep Knap:Bound(int i)/计算结点所相应价值的上界计算结点所相应价值的上界 Typew cleft=c-cw;/剩余容量剩余容量 Typep b=cp;/价值上界价值上界 /以物品单位重量价值递减序装填剩余容量以物品单位重量价值递减序装填剩余容量 while(i=n&wi=cleft)cleft-=w i;b+=pi;i+;

50、/装填剩余容量装满背包装填剩余容量装满背包 if(i=n)b+=pi/wi*cleft;return b;6.4 0-1背包问题背包问题57函数函数AddLiveNode将一个新的活结点插入到子集树将一个新的活结点插入到子集树和优先队列中和优先队列中 templatevoid Knap:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev)/将一个新的活结点插入到子集树和最大堆将一个新的活结点插入到子集树和最大堆H中中 bbnode*b=new bbnode;b-parent=E;b-LChild=ch;HeapNode N;N.upro