算法分析与设计第6章

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

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

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

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

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

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

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

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

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

10、，以该优先级的非增序抽取当前扩展结点，这种策略有时可以更迅速地找取当前扩展结点，这种策略有时可以更迅速地找到最优解。到最优解。6.1分支限界法的基本思想分支限界法的基本思想141234306102054ABCDEFGHIJKLMNOPQ1234344324422332B 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分支限界法的基本思想分支限界法的基本思想151234306102054ABCDEFGHIJKLMNOPQ1234344324422332B，0C,30D,6优先队列E,4J,14K,24H,1

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

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

13、法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为不小于当前找到的最短路长，则算法剪去以该结点为根的子树。根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶在算法中，利用结点间的控制关系进行剪枝。从源顶点点s s出发，出发，2 2条不同路径到达图条不同路径到达图G G的同一顶点。由于两的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。的树中的结点为根的子树剪去。 6.2单源最短路径单源最短路径186.2单源最短路径单源最短路径19templateclass Gra

14、ph 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单源最短路径单源最短路径20templ

15、atevoid Graph: ShortestPaths( int v ) /单源最短路径问题的优先队列式分支限界法单源最短路径问题的优先队列式分支限界法 /定义最小堆的容量为定义最小堆的容量为1000 MinHeap MinHeapNode H(1000); /定义源为初始扩展结点定义源为初始扩展结点 MinHeapNode E; E.i = v; E.length = 0; dist v =0; /搜索问题的解空间搜索问题的解空间6.2单源最短路径单源最短路径21 while (true) for (int j = 1; j = n; j+) /寻找寻找E的下一个结点的下一个结点 if (

16、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单源最短路径单源最短路径22while 循环体完成对解空间内部结

17、点的扩展，对于当前节结点，算法依次检查与当前扩展节点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到j的所有相应的路径长度小于当前最优路径长度，则将点j插入到活结点优先队列中。236.2装载问题装载问题1. 问题描述问题描述有一批共有一批共n n个集装箱要装上个集装箱要装上2 2艘载重量分别为艘载重量分别为c1c1和和c2c2的轮的轮船，其中集装箱船，其中集装箱i i的重量为的重量为W Wi i，且，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这些装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这集装箱装上这2 2艘轮船。如果有，找

18、出一种装载方案。艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。策略可得到最优装载方案。 (1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。 6.3装载问题装载问题2401631163116015300151506.3装载问题装载问题2511116011601631163116015300151501501601116150活结点队列活结点队列扩展结点扩展结点2. 队列式分支限界法队列式分支限界法6

19、.3装载问题装载问题26算法思想算法思想 用一个队列用一个队列Q来存放活结点表，来存放活结点表，Q中中weight表示每个活结表示每个活结点所相应的当前载重量。当点所相应的当前载重量。当weight1时，表示队列已达时，表示队列已达到解空间树到解空间树同一层结点的尾部同一层结点的尾部。 算法首先检测当前扩展结点的左儿子结点是否为可行结点。算法首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中加入到活结点队列中(右儿子结点一定是可行结点右儿子结点一定是可行结点)。2个儿个儿子结点都

20、产生后，当前扩展结点被舍弃。子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记于队列中每一层结点之后都有一个尾部标记-1，故在取队首，故在取队首元素时，活结点队列一定不空。当取出的元素是元素时，活结点队列一定不空。当取出的元素是-1时，再判时，再判断当前队列是否为空。如果队列非空，则将尾部标记断当前队列是否为空。如果队列非空，则将尾部标记-1加入加入活结点队列，算法开始处理下一层的活结点。活结点队列，算法开始处理下一层的活结点。6.3装载问题装载问题27n该算法包含两个函数

21、该算法包含两个函数MaxLoading函数具体实施对解空间的分支限函数具体实施对解空间的分支限界搜索。界搜索。EnQueue用于将活结点加入到活结点队列中，用于将活结点加入到活结点队列中，该函数首先检查该函数首先检查i是否等于是否等于n，如果，如果i=n，则表示，则表示当前活结点为一个叶结点，由于叶结点不会被当前活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，如果该进一步扩展，因此不必加入到活结点，如果该叶结点表示的可行解优于当前最优解，更新最叶结点表示的可行解优于当前最优解，更新最优解。当优解。当in时，当前活结点是一个内部结点，时，当前活结点是一个内部结点，加入到活结

22、点队列中。加入到活结点队列中。6.3装载问题装载问题28templateT 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(

23、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+; / 进入下一层进入下一层 29templatevoid EnQueue( Queue &Q, T wt,T&

24、 bestw, int i, int n) /该函数负责加入活结点该函数负责加入活结点 / 如果不是叶结点，则将结点权值如果不是叶结点，则将结点权值w t加入队列加入队列Q if (i = n) / 叶子叶子 if (wt bestw) bestw = wt; else Q.Add(wt); / 不是叶子不是叶子6.3装载问题装载问题303. 算法的改进算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设此集装箱装上船。设bestw是当前最优解；是当前最优解；Ew是当前扩是当前扩展结点所相应的重量；展结点所相应的重量；r是

25、剩余集装箱的重量。则当是剩余集装箱的重量。则当Ew+r bestw时，可将其右子树剪去，因为此时若要船装时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船最多集装箱，就应该把此箱装上船。算法算法MaxLoading初始时将初始时将bestw置为置为0，直到搜索到第，直到搜索到第一个叶结点时才更新一个叶结点时才更新bestw。因此在算法搜索到第一个。因此在算法搜索到第一个叶结点之前，总有叶结点之前，总有bestw0，r0，故，故Ew+rbestw总是总是成立，也就是说，此时右子树测试不起作用。成立，也就是说，此时右子树测试不起作用。算法中结点相应的重量仅在搜索进入左子树时增加，

26、因算法中结点相应的重量仅在搜索进入左子树时增加，因此，可以在算法每一次进入左子树时更新此，可以在算法每一次进入左子树时更新bestw的值。的值。6.2装载问题装载问题311116011601631163116015300151501516011161516.3装载问题装载问题32n使用限界函数进行改进使用限界函数进行改进T MaxLoading( T w , T c, int n ) Queue Q; / 活节点队列活节点队列 Q.Add (-1) ; /标记本层的尾部标记本层的尾部 int i = 1; / 当前扩展节点的层当前扩展节点的层 T Ew = 0, /当前扩展节点的重量当前扩展节

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

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

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

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

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

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

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

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

35、pe, bool, int); friend Type MaxLoading (Type *, Type, int , int *); public: operator Type() const return uweight; private: bbnode *ptr /指向活结点在子集树中相应结点的指针指向活结点在子集树中相应结点的指针 Type uweight; /活结点优先级（上界）活结点优先级（上界） int level; /活结点在子集树中所处的层序号活结点在子集树中所处的层序号 ；42函数函数AddLiveNode以结点元素类型以结点元素类型bbnode将一个新产生的活结将一个新产

36、生的活结点加入到子集树中，并以结点元素类型点加入到子集树中，并以结点元素类型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.uw

37、eight = wt; N.level = lev; N.ptr = b; H.Insert(N);向子集树中向子集树中添加结点添加结点向活结点优向活结点优先队列插入先队列插入新结点新结点43n函数函数MaxLoading具体实施对解空间的优先队列式分具体实施对解空间的优先队列式分支限界搜索，在函数中，定义最大堆的容量为支限界搜索，在函数中，定义最大堆的容量为1000，即在运行期间，最多容纳即在运行期间，最多容纳1000个结点。个结点。n第第i+1层结点的剩余重量层结点的剩余重量ri定义为第定义为第i+1到第到第n个物品个物品重量的和。重量的和。n变量变量E指向子集树中当前扩展结点，指向子集树

38、中当前扩展结点，Ew是相应的重是相应的重量。算法开始时，量。算法开始时，i=1, Ew =0，子集树的根结点为扩，子集树的根结点为扩展结点。展结点。6.2装载问题装载问题44templateType MaxLoading(Type w , Type c, int n, int bestx ) /优先队列式分支限界法，返回最优载重量，优先队列式分支限界法，返回最优载重量，bestx返回最优解返回最优解 /定义最大堆的容量为定义最大堆的容量为1000 MaxHeap HeapNode H( 1000 ); /定义剩余重量数组定义剩余重量数组r Type * r = new Type n + 1 ;

39、 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; /扩展结点所相应的载重量扩展结点所相应的载重量 45 while( i ! = n + 1 ) /非叶结点非叶结点 /检查当前扩展结点的儿子结点检查当前扩展结点的儿子结点 if( Ew + w i = c ) /左儿子结点为可行结点左儿子结点为可行结点 AddLiveNode( H, E, Ew +

40、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 -

41、parent; /end for return Ew; 46优先队列优先队列解空间树解空间树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.p

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

43、eEE6.3装载问题装载问题480-1背包问题背包问题6.4 0-1背包问题背包问题49采用优先队列式分支限界采用优先队列式分支限界n活结点优先队列中结点元素活结点优先队列中结点元素N的优先级由该的优先级由该结点的上界函数结点的上界函数Bound计算出的值计算出的值uprofit给给出。出。n以结点以结点N为根的子树中任一结点的价值不超为根的子树中任一结点的价值不超过过N.profit。6.4 0-1背包问题背包问题50nclass Object : 描述物品描述物品nclass bbnode: 子集树结点子集树结点 nclass HeapNode: 优先队列结点优先队列结点nclass Kn

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

45、nt *, 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背包问题背包问题

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

47、 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背包问题背包问题54函数函数MaxKnapsack实施对于子集树的优先队列式实施对于子集树的优先队列式分支限界搜索分支限界搜索templateTypep Knap: MaxKnapsack() /优先队列式分支限界法，返回最大价值，优先队列式分支限界法，返回最大价值，bestx返回最优解返回最优解 /