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

第6章 分支限界法 Branch and Bound 1主要内容n6.1 分支限界法的基本思想分支限界法的基本思想n6.2 单源最短路径问题单源最短路径问题n6.3 装载问题装载问题n6.4 0-1背包问题背包问题26.1 分支限界法的基本思想分支限界法的基本思想nBreadth-first search n分支限界法与回溯法分支限界法与回溯法n（1）求解目标：回溯法的求解目标是找出）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的全部解，而分解空间树中满足约束条件的全部解，而分支限界法的求解目标则是找出满足约束条支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。找出在某种意义下的最优解。n（2）搜寻方式的不同：回溯法以深度优先）搜寻方式的不同：回溯法以深度优先的方式搜寻解空间树，而分支限界法则以的方式搜寻解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜寻解广度优先或以最小耗费优先的方式搜寻解空间树。空间树。6.1分支限界法的基本思想分支限界法的基本思想3分支限界法的搜寻策略分支限界法的搜寻策略在扩展结点处，先生成其全部的儿子结点（分支），在扩展结点处，先生成其全部的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。然后再从当前的活结点表中选择下一个扩展结点。为了有效的选择下一扩展结点，以加速搜寻的进程，为了有效的选择下一扩展结点，以加速搜寻的进程，在每一活结点处，计算一个函数值，并依据这些已在每一活结点处，计算一个函数值，并依据这些已计算出的函数值，从当前活结点表中选择一个最有计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜寻朝着解空间树上有利的结点作为扩展结点，使搜寻朝着解空间树上有最优解的分支推动，以便尽快地找出一个最优解最优解的分支推动，以便尽快地找出一个最优解。6.1分支限界法的基本思想分支限界法的基本思想4w=16,15,15,v=45,25,25,c=306.1分支限界法的基本思想分支限界法的基本思想5分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜寻问题的解空间树。优先的方式搜寻问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程始终持点，并重复上述结点扩展过程。这个过程始终持续到找到所需的解或活结点表为空时为止。续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次为扩展结点。活结点一旦成为扩展结点，就一次性产生其全部儿子结点。在这些儿子结点中，导性产生其全部儿子结点。在这些儿子结点中，导致不行行解或导致非最优解的儿子结点被舍弃，致不行行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。其余儿子结点被加入活结点表中。6.1分支限界法的基本思想分支限界法的基本思想6常见的两种分支限界法常见的两种分支限界法n队列式队列式(FIFO)分支限界法分支限界法n 依据队列先进先出（依据队列先进先出（FIFO）原则选取下）原则选取下一个节点为扩展节点。一个节点为扩展节点。n优先队列式优先队列式(priority queue)分支限界法分支限界法n 依据优先队列中规定的优先级选取优先依据优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。级最高的节点成为当前扩展节点。n 6.1分支限界法的基本思想分支限界法的基本思想7n例：考虑例：考虑n=3 时时0-1背包问题的一个实例如下：背包问题的一个实例如下：w=16,15,15,p=45,25,25,c=30。其子集树。其子集树6.1分支限界法的基本思想分支限界法的基本思想8用用队列式队列式分支限界法解此问题分支限界法解此问题n队列式分支限界法搜寻解空间树的方式与队列式分支限界法搜寻解空间树的方式与解空间树的广度优先遍历算法极为相像，解空间树的广度优先遍历算法极为相像，唯一的不同之处是队列式分支限界法不搜唯一的不同之处是队列式分支限界法不搜寻以不行行结点为根的子树。寻以不行行结点为根的子树。6.1分支限界法的基本思想分支限界法的基本思想9队列式队列式0活结点队列活结点队列B，C160C，E16F，G1504516G30501525152500E，F，G6.1分支限界法的基本思想分支限界法的基本思想w=16,15,15,p=45,25,25,c=3010用优先队列式分支限界法解此问题用优先队列式分支限界法解此问题n也是从根结点也是从根结点A起先搜寻解空间树，用一个起先搜寻解空间树，用一个极大堆来表示活结点表的优先队列，该优先极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结点所获得的价值。队列的优先级定义为活结点所获得的价值。初始时堆为空。初始时堆为空。0450452504550252500454545025502502506.1分支限界法的基本思想分支限界法的基本思想w=16,15,15,p=45,25,25,c=3011n优先队列中规定的结点优先级常用一个与优先队列中规定的结点优先级常用一个与该结点相关的数值该结点相关的数值p来表示，结点优先级来表示，结点优先级的凹凸与的凹凸与p值的大小相关，最大优先队列值的大小相关，最大优先队列规定规定p值较大的结点优先级较高，用大堆值较大的结点优先级较高，用大堆来实现。来实现。n 小优先队列规定小优先队列规定p值较小的结点优先级值较小的结点优先级较高，用小堆来实现。较高，用小堆来实现。6.1分支限界法的基本思想分支限界法的基本思想12n当寻求问题的一个最优解时，可以用剪枝函数来当寻求问题的一个最优解时，可以用剪枝函数来加速搜寻，该函数给出每一个可行结点相应的子加速搜寻，该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。假如这个上界不树可能获得的最大价值的上界。假如这个上界不会比当前最优值更大，则说明相应的子树中不含会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去，问题的最优解，因而可以剪去，n另一方面，我们也可以将上界函数确定的每个结另一方面，我们也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点，这种策略有时可以更快速地找取当前扩展结点，这种策略有时可以更快速地找到最优解。到最优解。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分支限界法的基本思想分支限界法的基本思想156.2 单源最短路径 算法思想算法思想 解单源最短路径问题的优先队列式分支限界法用一解单源最短路径问题的优先队列式分支限界法用一微小堆来存储活结点表。其优先级是结点所对应的当前微小堆来存储活结点表。其优先级是结点所对应的当前路长。路长。算法从图算法从图G G的源顶点的源顶点s s和空优先队列起先。结点和空优先队列起先。结点s s被扩展后，被扩展后，它的儿子结点被依次插入堆中。它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的全部顶点。前扩展结点，并依次检查与当前扩展结点相邻的全部顶点。假如从当前扩展结点假如从当前扩展结点i i到顶点到顶点j j有边可达，且从源动身，有边可达，且从源动身，途经顶点途经顶点i i再到顶点再到顶点j j的所相应的路径的长度小于当前最优路的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一干脆着到活结点优先队列为空时这个结点的扩展过程一干脆着到活结点优先队列为空时为止。为止。6.2单源最短路径单源最短路径16剪枝策略在在算算法法扩扩展展结结点点的的过过程程中中，一一旦旦发发觉觉一一个个结结点点的的下下界界不不小小于于当当前前找找到到的的最最短短路路长长，则则算算法法剪剪去去以以该该结结点点为为根的子树。根的子树。在在算算法法中中，利利用用结结点点间间的的限限制制关关系系进进行行剪剪枝枝。从从源源顶顶点点s s动动身身，2 2条条不不同同路路径径到到达达图图G G的的同同一一顶顶点点。由由于于两两条条路路径径的的路路长长不不同同，因因此此可可以以将将路路长长长长的的路路径径所所对对应应的树中的结点为根的子树剪去。的树中的结点为根的子树剪去。6.2单源最短路径单源最短路径176.2单源最短路径单源最短路径18templateclass Graph friend void main(void);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)/单单源最短路径源最短路径问题问题的的优优先先队队列式分支限界法列式分支限界法 /定定义义最小堆的容量最小堆的容量为为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可达，且可达，且满满足限制足限制约约束束 distj=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的全部相应的路径长度小于当前最优路径长度，则将点j插入到活结点优先队列中。226.2装载问题装载问题1.问题描述问题描述有有一一批批共共n n个个集集装装箱箱要要装装上上2 2艘艘载载重重量量分分别别为为c1c1和和c2c2的的轮轮船，其中集装箱船，其中集装箱i i的重量为的重量为W Wi i，且且装载问题要求确定是否有一个合理的装载方案可将这些装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这集装箱装上这2 2艘轮船。假如有，找出一种装载方案。艘轮船。假如有，找出一种装载方案。简简洁洁证证明明：假假如如一一个个给给定定装装载载问问题题有有解解，则则接接受受下下面面的的策略可得到最优装载方案。策略可得到最优装载方案。(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上其次艘轮船。将剩余的集装箱装上其次艘轮船。6.3装载问题装载问题2301631163116015300151506.3装载问题装载问题2411116011601631163116015300151501501601116150活结点队列活结点队列扩展结点扩展结点2.队列式分支限界法队列式分支限界法6.3装载问题装载问题25算法思想算法思想 用一个队列Q来存放活结点表，Q中weight表示每个活结点所相应的当前载重量。当weight1时，表示队列已达到解空间树同一层结点的尾部。算法首先检测当前扩展结点的左儿子结点是否为可行结点。假如是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点确定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列确定不空。当取出的元素是-1时，再推断当前队列是否为空。假如队列非空，则将尾部标记-1加入活结点队列，算法起先处理下一层的活结点。6.3装载问题装载问题26n该算法包含两个函数该算法包含两个函数nMaxLoading函数具体实施对解空间的分支限界函数具体实施对解空间的分支限界搜寻。搜寻。nEnQueue用于将活结点加入到活结点队列中，该用于将活结点加入到活结点队列中，该函数首先检查函数首先检查i是否等于是否等于n，假如，假如i=n，则表示当前，则表示当前活结点为一个叶结点，由于叶结点不会被进一步活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，假如该叶结点表扩展，因此不必加入到活结点，假如该叶结点表示的可行解优于当前最优解，更新最优解。当示的可行解优于当前最优解，更新最优解。当in时，当前活结点是一个内部结点，加入到活结点时，当前活结点是一个内部结点，加入到活结点队列中。队列中。6.3装载问题装载问题27templateT MaxLoading(T w,T c,int n)/返回最优装载值返回最优装载值 /为层次为层次1 初始化初始化 Queue Q;/活结点队列活结点队列 Q.Add(-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.Add(-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.算法的改进算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设此集装箱装上船。设bestw是当前最优解；是当前最优解；Ew是当前扩是当前扩展结点所相应的重量；展结点所相应的重量；r是剩余集装箱的重量。则当是剩余集装箱的重量。则当Ew+rbestw时，可将其右子树剪去，因为此时若要船时，可将其右子树剪去，因为此时若要船装最多集装箱，就应当把此箱装上船。装最多集装箱，就应当把此箱装上船。算法算法MaxLoading初始时将初始时将bestw置为置为0，直到搜寻到第，直到搜寻到第一个叶结点时才更新一个叶结点时才更新bestw。因此在算法搜寻到第一个叶。因此在算法搜寻到第一个叶结点之前，总有结点之前，总有bestw0，r0，故，故Ew+rbestw总是成总是成立，也就是说，此时右子树测试不起作用。立，也就是说，此时右子树测试不起作用。算法中结点相应的重量仅在搜寻进入左子树时增加，因算法中结点相应的重量仅在搜寻进入左子树时增加，因此，可以在算法每一次进入左子树时更新此，可以在算法每一次进入左子树时更新bestw的值。的值。6.2装载问题装载问题301116011601631163116015300151501516011161516.3装载问题装载问题31n运用限界函数进行改进运用限界函数进行改进nT MaxLoading(T w,T c,int n)n Queue Q;/活节点队列活节点队列n Q.Add(-1);/标记本层的尾部标记本层的尾部n int i=1;/当前扩展节点的层当前扩展节点的层n T Ew=0,/当前扩展节点的重量当前扩展节点的重量n bestw=0;/目前的最优值目前的最优值n r=0;/当前扩展节点中余下的重量当前扩展节点中余下的重量n for(int j=2;j=n;j+)n r+=wi;n 6.3装载问题装载问题32while(true)/检查扩展结点的左孩子检查扩展结点的左孩子 T wt=Ew+wi;/左孩子的权值左孩子的权值 if(wt bestw)bestw=wt;/若不是叶子，则添加到队列若不是叶子，则添加到队列 if(i bestw&i n)Q.Add(Ew);/可能含最优解可能含最优解 Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点 if(Ew=-1)/到达层的尾部到达层的尾部 if(Q.IsEmpty()return bestw;Q.Add(-1);/添加尾部标记添加尾部标记 Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点 i+;r-=wi;6.3装载问题装载问题34 为了在算法结束后能便利地构造出与最优值相应的最优解，算法必需存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标记。templateclass QNode QNode*parent;/指向父结点的指针指向父结点的指针 bool LChild;/左儿子标记左儿子标记 Type weight;/结点所相应的载重量结点所相应的载重量;4.构造最优解构造最优解6.3装载问题装载问题35016311631160153001515000false16false015true016true6.3装载问题装载问题36优先队列式分支限界法优先队列式分支限界法存储活结点的方式存储活结点的方式:最大优先队列存储活结点表。最大优先队列存储活结点表。活结点活结点x在优先队列中的优先级定义在优先队列中的优先级定义:从根结点到结点从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。的路径所相应的载重量再加上剩余集装箱的重量之和。扩展结点的选择：扩展结点的选择：优先队列中优先级最大的活结点成优先队列中优先级最大的活结点成为下一个扩展结点。以结点为下一个扩展结点。以结点x为根的子树中全部结点相为根的子树中全部结点相应的路径的载重量不超过它的优先级应的路径的载重量不超过它的优先级x.uweight。子集。子集树中叶结点所相应的载重量与其优先级相同。树中叶结点所相应的载重量与其优先级相同。算法终止条件：算法终止条件：子集树中叶结点所相应的载重量与其子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止可以断言该叶结点所相应的解即为最优解。此时可终止算法。算法。6.3装载问题装载问题如何证明？如何证明？37可以用两种不同方式来实现n在结点优先队列的每一个活结点中保存从解空间树的在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。的叶结点时，就在该叶结点处同时得到相应的最优解。n在算法的搜寻进程中保存当前已构造出的部分解空间在算法的搜寻进程中保存当前已构造出的部分解空间树，这样在算法确定了达到最优值的叶结点时，就可树，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点起先向根结点回溯，构造以在解空间树中从该叶结点起先向根结点回溯，构造出相应的最优解。出相应的最优解。6.2装载问题装载问题38优先队列优先队列解空间树解空间树w=16,15,15 r3=0,r2=15,r1=30两种结构：子集树结点结构，大堆结点结构两种结构：子集树结点结构，大堆结点结构462i=1E=0truefalse302i=2Ew=16Efalse313i=3Ew=16Efalse164Ei=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 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,int*);public:operator Type()const return uweight;private:bbnode*ptr /指向活结点在子集树中相应结点的指针指向活结点在子集树中相应结点的指针 Type uweight;/活结点优先级（上界）活结点优先级（上界）int level;/活结点在子集树中所处的层序号活结点在子集树中所处的层序号 ；41函数函数AddLiveNode以结点元素类型以结点元素类型bbnode将一个新产生的活结将一个新产生的活结点加入到子集树中，并以结点元素类型点加入到子集树中，并以结点元素类型HeapNode将这个新结将这个新结点插入到表示活结点优先队列的最大堆中。点插入到表示活结点优先队列的最大堆中。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函数函数MaxLoading具体实施对解空间的优先队列式分具体实施对解空间的优先队列式分支限界搜寻，在函数中，定义最大堆的容量为支限界搜寻，在函数中，定义最大堆的容量为1000，即在运行期间，最多容纳，即在运行期间，最多容纳1000个结点。个结点。n第第i+1层结点的剩余重量层结点的剩余重量ri定义为第定义为第i+1到第到第n个物品个物品重量的和。重量的和。n变量变量E指向子集树中当前扩展结点，指向子集树中当前扩展结点，Ew是相应的重是相应的重量。算法起先时，量。算法起先时，i=1,Ew=0，子集树的根结点为扩，子集树的根结点为扩展结点。展结点。6.2装载问题装载问题43templateType MaxLoading(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;/扩展结点所相应的载重量扩展结点所相应的载重量 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+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);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-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:对整个问题的初始化及调用其它函数解决问题对整个问题的初始化及调用其它函数解决问题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 operator=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()const 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:Typep 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-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;/当前最优值当前最优值 Typep 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 while 循环内部，算法首先检查循环内部，算法首先检查当前扩展结点的左儿子结点的可当前扩展结点的左儿子结点的可行性。假如可行，则加入子集树行性。假如可行，则加入子集树和活结点优先队列中。和活结点优先队列中。当前扩展结点的右儿子确定可行，仅当前扩展结点的右儿子确定可行，仅当右儿子满足上界约束时才将它加入当右儿子满足上界约束时才将它加入子集树和活结点优先队列。子集树和活结点优先队列。55/取下一扩展结点取下一扩展结点 HeapNode N;H-DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit;i =N.level;/构造当前最优解构造当前最优解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+;/装填剩余容量装满背包装填剩余容量装满背包 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.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H-Insert(N);58