矿大算法第6章 分支限界法

1、学习要点学习要点理解分支限界法的剪枝搜索策略。理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架掌握分支限界法的算法框架 （1）队列式）队列式(FIFO)分支限界法分支限界法 （2）优先队列式分支限界法）优先队列式分支限界法 第第6 6章章 分支限界法分支限界法通过应用范例学习分支限界法的设计策略。通过应用范例学习分支限界法的设计策略。 （1）单源最短路径问题）单源最短路径问题 （2）装载问题；）装载问题； （3）布线问题）布线问题 （4）0-1背包问题；背包问题；（5）最大团问题；）最大团问题；（6）旅行售货员问题）旅行售货员问题（7）电路板排列问题）电路板排列问题（8）批处理作业调度问

2、题）批处理作业调度问题2022年5月25日星期三第6章 分支限界分支限界法法26.1 分支限界法的基本思想分支限界法的基本思想n类似于回溯法，分支限界法在搜索解空间时，也类似于回溯法，分支限界法在搜索解空间时，也使用树形结构来组织解空间（子集树和排列树）。使用树形结构来组织解空间（子集树和排列树）。与回溯法不同的是，回溯算法使用深度优先方法与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分支限界法用宽度优先或最小耗搜索树结构，而分支限界法用宽度优先或最小耗费方法来搜索这些树。费方法来搜索这些树。n分支限界（分支限界（branch and bound）是另一种系统地）是另一种系统地搜索解

3、空间的方法，它与回溯法的主要区别在于搜索解空间的方法，它与回溯法的主要区别在于对对E结点的扩充方式。结点的扩充方式。2022年5月25日星期三第6章 分支限界分支限界法法3n每个活结点有且仅有一次机会变成每个活结点有且仅有一次机会变成E结点。当一个结点。当一个结点变为结点变为E结点时，则生成从该结点移动一步即可结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不到达的所有新结点。在生成的结点中，抛弃那些不可能导出（最优）可行解的结点，其余结点加入活可能导出（最优）可行解的结点，其余结点加入活结点表，然后从表中选择一个结点作为下一个结点表，然后从表中选择一个结点作为下一

4、个E结结点。从活结点表中取出所选择的结点并进行扩充，点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充过程才结束。直到找到解或活动表为空，扩充过程才结束。n相对而言，分支限界法的解空间比回溯法大得多，相对而言，分支限界法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。因此当内存容量有限时，回溯法成功的可能性更大。2022年5月25日星期三第6章 分支限界分支限界法法4n选择选择E结点的两种常用方法：结点的两种常用方法：队列式（队列式（FIFO)：将活结点表组织成队列，按先：将活结点表组织成队列，按先进先出原则选取下一个结点作为当前扩展结点。进先出原则

5、选取下一个结点作为当前扩展结点。优先队列式：每个结点都有一个对应的耗费或收优先队列式：每个结点都有一个对应的耗费或收益。按优先级选取下一个结点作为当前扩展结点。益。按优先级选取下一个结点作为当前扩展结点。n如果求解最小耗费的解，则活结点表可用最小堆如果求解最小耗费的解，则活结点表可用最小堆来建立，下一个来建立，下一个E结点就是具有最小耗费的活结点；结点就是具有最小耗费的活结点；如果求解最大收益的解，则可用最大堆来构造活如果求解最大收益的解，则可用最大堆来构造活结点表，下一个结点表，下一个E结点是具有最大收益的活结点。结点是具有最大收益的活结点。2022年5月25日星期三第6章 分支限界分支限界

6、法法5n例例 0/1背包问题背包问题 n=3, w=20,15,15, p=45,25,25, c= 30。n 下面分别利用两种方法来解决背包问题。下面分别利用两种方法来解决背包问题。1）FIFO分支限界法分支限界法 结点将按照结点将按照FIFO顺序从队列中取出；顺序从队列中取出；2）优先队列式：）优先队列式： 使用一个最大堆，其中的使用一个最大堆，其中的E结点按照每个活结点收结点按照每个活结点收益值的降序，或是按照活结点任意子树的叶结点所益值的降序，或是按照活结点任意子树的叶结点所能获得的收益估计值的降序从队列中取出。能获得的收益估计值的降序从队列中取出。2022年5月25日星期三第6章 分

7、支限界分支限界法法61）FIFO分支限界法：初始时活结点队列为空，以分支限界法：初始时活结点队列为空，以 A作为作为E结点，结点，生成的两个子结点生成的两个子结点B和和C都是可行的，因此加入活结点队列中，都是可行的，因此加入活结点队列中，结点结点A被删除。下一个扩展结点是被删除。下一个扩展结点是B，扩展得到结点，扩展得到结点D和和E，D是不可行的，被删除，而是不可行的，被删除，而E被加入队列中。下一步结点被加入队列中。下一步结点C成为成为扩展结点，扩展得到结点扩展结点，扩展得到结点F和和G，两者都是可行结点，加入队，两者都是可行结点，加入队列中。扩展列中。扩展E得到得到J和和K，J不可行而被删

8、除，不可行而被删除，K是一个可行的是一个可行的叶结点，并产生一个到目前为止可行的解，它的收益值为叶结点，并产生一个到目前为止可行的解，它的收益值为45。W=(16,15,15)P=(45,25,25)C=30101116/45 30/5000112022年5月25日星期三第6章 分支限界分支限界法法7n下一个扩展结点是下一个扩展结点是F，它产生两个孩子，它产生两个孩子L、M，L代代表一个可行的解且其收益值为表一个可行的解且其收益值为50，M代表另一个收代表另一个收益值为益值为25的可行解。的可行解。G是最后一个扩展结点，它的是最后一个扩展结点，它的孩子孩子N和和O都是可行的。由于活结点队列变为

9、空，都是可行的。由于活结点队列变为空，因此搜索过程终止，最佳解的收益值为因此搜索过程终止，最佳解的收益值为50。n本例中，结点扩展次序为本例中，结点扩展次序为: A; B; C; E; F; G。n可见，可见，FIFO分支限界法与从根结点出发的广度优先分支限界法与从根结点出发的广度优先搜索非常类似，区别是在搜索非常类似，区别是在FIFO分枝定界中不可行的分枝定界中不可行的结点不会被搜索。结点不会被搜索。2022年5月25日星期三第6章 分支限界分支限界法法82）优先队列式：）优先队列式： （按物品价值优先次序）（按物品价值优先次序）n以以A作为初始结点。扩展得到结点作为初始结点。扩展得到结点B

10、和和C，两者都是，两者都是可行的并被插入堆中，结点可行的并被插入堆中，结点B获得的收益值是获得的收益值是45，而结点而结点C得到的收益值为得到的收益值为0。A被删除，被删除，B成为下一成为下一个扩展结点。扩展个扩展结点。扩展B得到结点得到结点D和和E，D是不可行的是不可行的而被删除，而被删除，E加入堆中。由于加入堆中。由于E具有收益值具有收益值45，而，而C为为0，因为，因为E成为下一个扩展结点。成为下一个扩展结点。n扩展扩展E时生成结点时生成结点J和和K，J不可行而被删除，不可行而被删除，K是一是一个可行的解，因此个可行的解，因此K为作为目前能找到的最优解而为作为目前能找到的最优解而记录下来

11、，然后记录下来，然后K被删除。被删除。2022年5月25日星期三第6章 分支限界分支限界法法9n由于只剩下一个活结点由于只剩下一个活结点C在堆中，因此在堆中，因此C作为扩展作为扩展结点被展开，生成结点被展开，生成F、G两个结点插入堆中。两个结点插入堆中。F的收的收益值为益值为25，因此成为下一个扩展结点，展开后得到，因此成为下一个扩展结点，展开后得到结点结点L和和M，但，但L、M都被删除，因为它们是叶结点，都被删除，因为它们是叶结点，同时同时L所对应的解被作为当前最优解记录下来。最所对应的解被作为当前最优解记录下来。最终，终，G成为扩展结点，生成的结点为成为扩展结点，生成的结点为N和和O，两者

12、，两者都是叶结点而被删除，两者所对应的解都比当前最都是叶结点而被删除，两者所对应的解都比当前最优解还差，因此最优解保持不变。此时堆变为空，优解还差，因此最优解保持不变。此时堆变为空，搜索过程终止。最优解为搜索过程终止。最优解为A到到L的路径（的路径（0,1,1）,价价值值50。n本例中，结点扩展次序为本例中，结点扩展次序为: A; B; E; C; F; G。2022年5月25日星期三第6章 分支限界分支限界法法10n利用一个限界函数能加速最优解的搜索过程。限界利用一个限界函数能加速最优解的搜索过程。限界函数为最大收益设置了一个上限，通过展开一个特函数为最大收益设置了一个上限，通过展开一个特殊

13、的结点可能获得这个最大收益。如果一个结点的殊的结点可能获得这个最大收益。如果一个结点的限界函数值不大于目前最优解的收益值，则此结点限界函数值不大于目前最优解的收益值，则此结点会被删除而不作展开，更进一步，在优先队列分支会被删除而不作展开，更进一步，在优先队列分支限界法中，可以使结点按照它们收益的限界函数值限界法中，可以使结点按照它们收益的限界函数值的非升序从堆中取出，而不是按照结点的实际收益的非升序从堆中取出，而不是按照结点的实际收益值来取出。这种策略从可能到达一个好的叶结点的值来取出。这种策略从可能到达一个好的叶结点的活结点出发，而不是从目前具有较大收益值的结点活结点出发，而不是从目前具有较

14、大收益值的结点出发。出发。2022年5月25日星期三第6章 分支限界分支限界法法11n例例 旅行商问题旅行商问题 对于如下图的四城市旅行商问题，对于如下图的四城市旅行商问题，其对应的解空间为一棵由结点其对应的解空间为一棵由结点A到结点到结点Q的排列树。的排列树。 对于此问题，有两种搜索解空间树方式：对于此问题，有两种搜索解空间树方式：1）使用）使用FIFO分支限界法；分支限界法； 扩展结点顺序：扩展结点顺序：B C D E F G H (I) J K2）优先队列式分支限界法：）优先队列式分支限界法： 使用最小耗费方法，即用一个最小堆来存储活结使用最小耗费方法，即用一个最小堆来存储活结点。点。n

15、扩展结点顺序：扩展结点顺序：B E D H J K (I) (C)2022年5月25日星期三第6章 分支限界分支限界法法1232活结点：活结点：B CDE DEFG EFGHI FGHIJK GHIJK HIJK IJK JK K(n-1)!个叶结点个叶结点 TSP问题的解空间树问题的解空间树143230201065443413ABEDCKJIHGFQPONML2434242559662632最优解：最优解：1 3 2 4 1 (结点结点N) 1 4 2 3 1 (结点结点K)E结点：结点： B C D E F G H I J K2022年5月25日星期三第6章 分支限界分支限界法法13n设计

16、限界函数的主要目是利用最少的时间，在内存设计限界函数的主要目是利用最少的时间，在内存允许的范围内去解决问题。允许的范围内去解决问题。n不要片面追求能产生具有最少数目的解空间结点，不要片面追求能产生具有最少数目的解空间结点，减少结点并不是根本的目标。因此，我们需要的是减少结点并不是根本的目标。因此，我们需要的是一个能够有效地减少计算时间并因此而使产生的结一个能够有效地减少计算时间并因此而使产生的结点数目也减少的限界函数。点数目也减少的限界函数。n回溯法与分支限界法在空间方面的比较回溯法与分支限界法在空间方面的比较 回溯法比分支限界法在占用内存方面具有优势。回溯法比分支限界法在占用内存方面具有优势

17、。n回溯法：回溯法：O(解空间的最大路径长度解空间的最大路径长度)n分支限界法：分支限界法：O(解空间大小解空间大小)。2022年5月25日星期三第6章 分支限界分支限界法法14n对于一个子集空间：对于一个子集空间： 回溯法回溯法O(n) 分支限界法：分支限界法：O(2n) 。n对于排列空间：对于排列空间： 回溯法：回溯法：O(n) 分支限界法：分支限界法：O(n!) 。n虽然最大收益（或最小耗费）分支限界法在直觉上虽然最大收益（或最小耗费）分支限界法在直觉上要好于回溯法，并且在许多情况下可能会比回溯法要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中，它可能会在回检查

18、更少的结点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。溯法超出允许的时间限制之前就超出了内存的限制。2022年5月25日星期三第6章 分支限界分支限界法法156.3 6.3 装载问题装载问题问题描述问题描述: :n n个集装箱装到个集装箱装到2 2艘载重量分别为艘载重量分别为c1,c2c1,c2的的货轮货轮, ,其中集装箱其中集装箱i i的重量为的重量为wiwi且且 问题要求找到一个合理的装载方案可将这问题要求找到一个合理的装载方案可将这n个个货货箱箱装上这装上这2艘轮船。艘轮船。211ccwnii当当 时问题等价于子集和问题时问题等价于子集和问题; ; 当当c

19、1=c2c1=c2且且 时时问题等价于划分问题问题等价于划分问题. .211ccwnii112cwnii若装载问题有解若装载问题有解, 采用如下策略可得一个最优装载方案采用如下策略可得一个最优装载方案:(1)将第一艘轮船尽可能装满将第一艘轮船尽可能装满; (2)将剩余的将剩余的货货箱装到第二艘轮船上。箱装到第二艘轮船上。将第一艘船尽可能装满等价于如下将第一艘船尽可能装满等价于如下0-l背包问题背包问题:niiixw1m axm ax12cxwniii2022年5月25日星期三第6章 分支限界分支限界法法166.3 装载问题装载问题1）队列式分支限界法：）队列式分支限界法：ntemplatevo

20、id EnQueue(Queue &Q, T wt, T& bestw, int i, int n)/ 若不是叶结点，则将结点权值若不是叶结点，则将结点权值wt加入加入Qif (i = n) / 叶结点不必加入叶结点不必加入Q中中 if (wt bestw) bestw = wt;/检查并更新最优解检查并更新最优解 else Q.Add(wt); / 不是叶子，应加入不是叶子，应加入Q中中/ EnQueue将活结点加入活结点队列将活结点加入活结点队列Q中。中。Q中用中用wt表示每个活结点对应的当前载重量，表示每个活结点对应的当前载重量，wt=-1表示到表示到达解空间树的同一层结点的尾部。达解空

21、间树的同一层结点的尾部。2022年5月25日星期三第6章 分支限界分支限界法法17n注意：注意：EnQueue可能会失败，因为可能没有足够的内可能会失败，因为可能没有足够的内存来给队列增加结点。存来给队列增加结点。 EnQueue并没有去捕获并没有去捕获Q.Add中的中的NoMem异常。异常。ntemplateT MaxLoading(T w , T c, int n) / 返回最优装载值返回最优装载值/初始化初始化Queue Q; / 活结点队列活结点队列Q.Add(-1); /标记本层活结点的尾部标记本层活结点的尾部int i = 1; / 当前当前E结点的层位于根结点结点的层位于根结点T

22、 Ew = 0, / E结点的权值（载重量）结点的权值（载重量）bestw = 0; / 目前的最优载重量目前的最优载重量/ 搜索子集空间树搜索子集空间树2022年5月25日星期三第6章 分支限界分支限界法法18 while (true) if (Ew+wi=bestw)时，才选择右孩子。时，才选择右孩子。n而在前面程序中，在而在前面程序中，在i变为变为n之前，之前，bestw的值一直保的值一直保持不变（直到搜索到第一个叶结点时才更新持不变（直到搜索到第一个叶结点时才更新bestw ），），因此在因此在i等于等于n之前对右孩子的测试总为真，因为之前对右孩子的测试总为真，因为bestw=0且且r

23、0。即此时对右子树的测试不起作用。即此时对右子树的测试不起作用。n为使对右子树的测试尽早生效，应尽早更新为使对右子树的测试尽早生效，应尽早更新bestw的的值。值。2022年5月25日星期三第6章 分支限界分支限界法法21n因为最优装载的重量是子集树中可行结点的重量因为最优装载的重量是子集树中可行结点的重量的最大值，所以只有在向左子树移动时这些重量的最大值，所以只有在向左子树移动时这些重量才会增大，因此可以在每次进行这种移动时改变才会增大，因此可以在每次进行这种移动时改变bestw的值。的值。n根据以上思想，改进的算法如下。根据以上思想，改进的算法如下。n当活结点加入队列时，当活结点加入队列时

24、，wt不会超过不会超过bestw，故，故bestw不用更新。因此在不用更新。因此在MaxLoading中直接用一中直接用一条简单语句条简单语句Q.Add(wt)取代了函数取代了函数EnQueue。2022年5月25日星期三第6章 分支限界分支限界法法22ntemplateT MaxLoading(T w , T c, int n) / 返回最优装载值。首先初始化返回最优装载值。首先初始化 Queue Q; / 活结点队列活结点队列 Q.Add(-1); /标记本层的尾部标记本层的尾部 int i = 1; / E结点的所在的层结点的所在的层 T Ew = 0, / E结点的重量结点的重量 be

25、stw=0; / 目前的最优装载量目前的最优装载量 r = 0; for (int j = 2; j = n; j+) r += wi; / E结点处目前余下的集装箱重量结点处目前余下的集装箱重量 / 开始搜索子集空间树开始搜索子集空间树2022年5月25日星期三第6章 分支限界分支限界法法23while (true) / 检查检查E结点的左孩子结点的左孩子T wt = Ew + wi; / 左孩子的重量左孩子的重量if (wt bestw) bestw = wt; /更新更新bestw if (i bestw & i n) / 检查右孩子检查右孩子 Q.Add(Ew); / 可能含最优解可能

26、含最优解Q.Delete(Ew); / 取下一个取下一个E-结点结点2022年5月25日星期三第6章 分支限界分支限界法法24 if (Ew = -1) / 到达同一层的尾部到达同一层的尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); /添加尾部标记添加尾部标记 Q.Delete(Ew); / 取下一个取下一个E-结点结点 i+; / 进入下一层进入下一层 r -= wi; / E结点中余下的重量结点中余下的重量 2022年5月25日星期三第6章 分支限界分支限界法法253. 寻找最优解：需记录从每个活结点到达根的路径，寻找最优解：需记录从每个活结点到达根

27、的路径，因此对每个结点设置指向其父结点得指针。活结因此对每个结点设置指向其父结点得指针。活结点队列中元素的类型是点队列中元素的类型是QNode。template class QNode friend void EnQueue(9个参数个参数); friend T MaxLoadig(T *, T, int, int *);private: QNode *parent; / 父结点指针父结点指针 bool LChild; / 是否为父结点的左孩子是否为父结点的左孩子 T weight; / 到达本结点的路径对应的载重量到达本结点的路径对应的载重量 ;2022年5月25日星期三第6章 分支限界分支

28、限界法法261)QueueQnode *& Q 队列队列Q2)T wt 从根到当前结点所对应得装载量从根到当前结点所对应得装载量3)int i 当前结点所在的层次当前结点所在的层次4)int n 集装箱数目集装箱数目5)T bestw 当前最优装载量当前最优装载量6)Qnode *E 当前扩展结点（当前扩展结点（E结点）结点）7)Qnode *bestE 当前最优当前最优E结点结点8)int * bestx 最优解最优解9)Bool ch 左儿子：左儿子：ch=1 ； 右儿子：右儿子：ch=0 ACB 1 30 0 15ABC2022年5月25日星期三第6章 分支限界分支限界法法27ntemp

29、latevoid EnQueue(QueueQNode* &Q , T wt, int i, int n, T bestw, QNode *E, QNode *&bestE, int bestx , bool ch) / 如果不是叶结点，则向队列如果不是叶结点，则向队列Q中添加一个中添加一个i 层、层、重量为重量为wt的活结点；的活结点； 新结点是新结点是E的一个孩子。当新结的一个孩子。当新结点是左孩子时，点是左孩子时， ch为为true。 / 若是叶子，则若是叶子，则ch的值就是的值就是bestxn。if (i = n) / 叶结点叶结点2022年5月25日星期三第6章 分支限界分支限界法法

30、28nif (wt = bestw) /wt至多等于至多等于bestw / 目前的最优解目前的最优解bestE = E;bestxn = ch;return; / 不是叶子不是叶子, 则添加到队列则添加到队列Q中中QNode *b;b = new QNode;b-weight = wt;b-parent = E;b-LChild = ch;Q.Add(b);2022年5月25日星期三第6章 分支限界分支限界法法29ntemplateT MaxLoading(T w , T c, int n, int bestx ) / 返回最优装载值，并在返回最优装载值，并在bestx中返回最优解中返回最优解

31、/ 使用使用F I F O分枝定界算法；分枝定界算法； 初始化初始化QueueQNode* Q; / 活结点队列活结点队列Q.Add(0); / 0 代表本层的尾部代表本层的尾部int i = 1; / E结点的层结点的层T Ew = 0, / E结点的重量结点的重量 bestw = 0; / 迄今得到的最优值迄今得到的最优值 r=0; / E结点中余下的重量（剩余集装箱重量）结点中余下的重量（剩余集装箱重量）for (int j = 2; j = n; j+) r += wi;QNode *E = 0, / 当前的当前的E-结点结点 * b e s t E ; / 目前最优的目前最优的E结点

32、结点2022年5月25日星期三第6章 分支限界分支限界法法30n/ 搜索子集空间树搜索子集空间树while (true) T wt = Ew + wi; if (wt bestw) bestw = wt; EnQueue(Q, wt, i, n, bestw, E, bestE, bestx, true);/ 检查右孩子检查右孩子if (Ew+rbestw)EnQueue(Q, Ew, i, n, bestw, E, bestE, bestx, false);Q. Delete(E) ; / 取下一个取下一个E结点结点2022年5月25日星期三第6章 分支限界分支限界法法31nif (! E)

33、 / 同层结点的尾部同层结点的尾部 if (Q.IsEmpty() break; Q.Add(0); / 添加层结点尾部标志添加层结点尾部标志 Q.Delete(E) ; / 从队列从队列Q中取下一个中取下一个E结点结点 i+ ; / E-结点的层次结点的层次 r -= wi; / E结点中余下的重量结点中余下的重量Ew=E- weight ; / 新的新的E结点的重量结点的重量/end of while/ 沿着从沿着从bestE到根的路径构造到根的路径构造xn-1,x1, 而而xn已经在函数已经在函数EnQueue中赋值。中赋值。for (j = n - 1; j 0; j-) bestxj

34、 = bestE-LChild; / bool型型int型型 bestE = bestE-parent;return bestw;2022年5月25日星期三第6章 分支限界分支限界法法324）优先队列式分支限界法）优先队列式分支限界法 在对子集树进行最大收益分支限界搜索时，活结点在对子集树进行最大收益分支限界搜索时，活结点列表是一个最大优先级队列，其中每个活结点列表是一个最大优先级队列，其中每个活结点x都都有一个相应的重量上限（最大收益）。这个重量上有一个相应的重量上限（最大收益）。这个重量上限是结点限是结点x 相应的重量加上剩余货箱的总重量，所相应的重量加上剩余货箱的总重量，所有的活结点按其

35、重量上限的递减顺序变为有的活结点按其重量上限的递减顺序变为E结点。结点。 注意：如果结点注意：如果结点x的重量上限是的重量上限是x.uweight，则在子，则在子树中不可能存在重量超过树中不可能存在重量超过x.uweight 的结点。另外，的结点。另外，当叶结点对应的重量等于它的重量上限时，可以得当叶结点对应的重量等于它的重量上限时，可以得出结论：该叶结点所对应的解就是最优解，其他任出结论：该叶结点所对应的解就是最优解，其他任何活结点都不会有更优的解，搜索终止。何活结点都不会有更优的解，搜索终止。2022年5月25日星期三第6章 分支限界分支限界法法33n上述策略可以用两种方法来实现：上述策略

36、可以用两种方法来实现：1)最大优先级队列中的活结点都是互相独立的，最大优先级队列中的活结点都是互相独立的，因此每个活结点内部必须记录从子集树的根到因此每个活结点内部必须记录从子集树的根到此结点的路径。一旦找到了最优装载所对应的此结点的路径。一旦找到了最优装载所对应的叶结点，就利用这些路径信息来计算叶结点，就利用这些路径信息来计算x 值。值。2)除了把结点加入最大优先队列之外，结点还必除了把结点加入最大优先队列之外，结点还必须放在另一个独立的树结构中，这个树结构用须放在另一个独立的树结构中，这个树结构用来表示所生成的子集树的一部分。当找到最大来表示所生成的子集树的一部分。当找到最大装载之后，就可

37、以沿着路径从叶结点逐步返回装载之后，就可以沿着路径从叶结点逐步返回到根，从而计算出到根，从而计算出x 值。值。2022年5月25日星期三第6章 分支限界分支限界法法34n采用第二种方案：优先队列用采用第二种方案：优先队列用HeapNode 类型类型的最大堆来表示。的最大堆来表示。ntemplateclass HeapNode public: operator T () const return uweight;private: bbnode *ptr; /指向活结点在子集树中位置指向活结点在子集树中位置 T uweight; / 活结点的重量上限活结点的重量上限 int level; /活结点

38、所在子集树的层活结点所在子集树的层 ;2022年5月25日星期三第6章 分支限界分支限界法法35n子集树中结点的类型是子集树中结点的类型是bbnode。结点按。结点按uweight值值从最大堆中取出。从最大堆中取出。nclass bbnode private: bbnode *parent; / 父结点指针父结点指针 bool LChild; / 当是父结点的左孩子时取当是父结点的左孩子时取true ;n函数函数AddLiveNode用于把用于把bbnode类型的活结点加类型的活结点加到子树中，并把到子树中，并把HeapNode类型的活结点插入最大类型的活结点插入最大堆。堆。AddLiveNo

39、de必须被定义为必须被定义为bbnode和和HeapNode的友元。的友元。2022年5月25日星期三第6章 分支限界分支限界法法36ntemplate void AddLiveNode(MaxHeapHeapNode &H, bbnode *E, T wt, bool ch, int lev) / 向最大堆向最大堆H中增添一个层为中增添一个层为lev，上限重量为，上限重量为wt的活结点，新结点是的活结点，新结点是E的儿子的儿子(左孩子：左孩子：ch=true) bbnode *b = new bbnode; /新结点加入子集树新结点加入子集树 b-parent = E; b-LChild =

40、 ch; HeapNode N; /新结点插入队列中新结点插入队列中 N.uweight = wt; N.level = lev; N.ptr = b; H.Insert(N);2022年5月25日星期三第6章 分支限界分支限界法法37n函数函数MaxLoading的思路的思路1)定义一个容量为定义一个容量为1000的最大堆。可以用它来解决的最大堆。可以用它来解决优先队列中活结点数在任何时候都不超过优先队列中活结点数在任何时候都不超过1000的的装箱问题。对于更大型的问题，需要一个容量更装箱问题。对于更大型的问题，需要一个容量更大的最大堆。如果改用基于指针的优先队列，则大的最大堆。如果改用基于

41、指针的优先队列，则不必预置队列容量。不必预置队列容量。2)初始化剩余重量数组初始化剩余重量数组r。第。第i+1层的结点（即层的结点（即x1 i的值都已确定）对应的剩余总重量为的值都已确定）对应的剩余总重量为ri=wj，j从从i+1到到n。3)变量变量E指向子集树中的当前指向子集树中的当前E结点，结点，Ew 是该结点是该结点对应的重量，对应的重量， i是它所在的层。是它所在的层。2022年5月25日星期三第6章 分支限界分支限界法法38n起初，根结点是起初，根结点是E结点，因此取结点，因此取i=1, Ew=0。由于。由于没有明确地存储根结点，因此没有明确地存储根结点，因此E的初始值取为的初始值取

42、为0。while 循环用于产生当前循环用于产生当前E结点的左、右孩子。如结点的左、右孩子。如果左孩子是可行的（即没有超出容量），则将它果左孩子是可行的（即没有超出容量），则将它加入到子集树中并作为一个第加入到子集树中并作为一个第i+1层结点加入最大层结点加入最大堆中。可行结点的右孩子总是可行的，它总被加堆中。可行结点的右孩子总是可行的，它总被加入子树及最大堆中。在完成添加操作后，接着从入子树及最大堆中。在完成添加操作后，接着从最大堆中取出下一个最大堆中取出下一个E结点。如果没有下一个结点。如果没有下一个E结结点，则不存在可行的解。如果下一个点，则不存在可行的解。如果下一个E结点是叶结点是叶结点

43、（结点（n+1结点），则它是一个最优装载，可以结点），则它是一个最优装载，可以沿着从叶到根的路径来确定装载方案。沿着从叶到根的路径来确定装载方案。2022年5月25日星期三第6章 分支限界分支限界法法39ntemplateT MaxLoading(T w , T c, int n, int bestx )/ 返回最优装载值，返回最优装载值，bestx保存最优解保存最优解/ 定义一个最多有定义一个最多有1000个活结点的最大堆个活结点的最大堆MaxHeapHeapNode H(1000);/ 定义剩余集装箱重量的数组定义剩余集装箱重量的数组r/ rj 为为wj+1n的重量之和的重量之和T *r

44、= new Tn+1;rn = 0;for (int j = n-1; j 0; j-) rj = rj+1 + wj+1;/ 初始化层初始化层12022年5月25日星期三第6章 分支限界分支限界法法40int i = 1; / E结点的层结点的层bbnode *E = 0; / 当前当前E结点结点T Ew = 0; / E结点的重量结点的重量/ 搜索子集空间树搜索子集空间树while (i != n+1) / 不在叶子上不在叶子上/ 检查检查E结点的孩子结点的孩子 if (Ew + wi = c) / 可行的左孩子可行的左孩子 AddLiveNode(H, E, Ew+wi+ri, true

45、, i+1);/ 右孩子右孩子 AddLiveNode(H, E, Ew+ri, false, i+1);/ 取下一个取下一个E-结点结点2022年5月25日星期三第6章 分支限界分支限界法法41 HeapNode N; H.DeleteMax(N); / 不能为空不能为空 i = N.level; E = N.ptr; Ew = N.uweight - ri-1;/ 沿着从沿着从E结点到根的路径构造结点到根的路径构造bestx for (int j = n; j 0; j-) bestxj = E-LChild; / 从从bool转换为转换为int E = E- parent;return

46、Ew;2022年5月25日星期三第6章 分支限界分支限界法法42n说明：说明：bestw表示当前所有可行结点的重量的最大值，表示当前所有可行结点的重量的最大值，而优先队列中可能有许多其而优先队列中可能有许多其uweight不超过不超过bestw的的活结点，因此这些结点不可能帮助我们找到最优的活结点，因此这些结点不可能帮助我们找到最优的叶结点，这些结点浪费了队列空间及插入叶结点，这些结点浪费了队列空间及插入/删除时间，删除时间，所以应清除这些结点。一种策略是，在插入某个结所以应清除这些结点。一种策略是，在插入某个结点之前检查是否有点之前检查是否有uweight bestw。但由于。但由于best

47、w在在执行过程中不断增大，所以目前插入的结点在以后执行过程中不断增大，所以目前插入的结点在以后并不能保证有效。更好的策略是在每次并不能保证有效。更好的策略是在每次bestw增大时，增大时，删除队列中所有删除队列中所有uweightbesew的结点。这要求删除的结点。这要求删除具有最小具有最小uweight的结点。因此，队列必须支持如下的结点。因此，队列必须支持如下的操作：插入、删除最大结点、删除最小结点。这的操作：插入、删除最大结点、删除最小结点。这种优先队列也被称作双端优先队列。种优先队列也被称作双端优先队列。2022年5月25日星期三第6章 分支限界分支限界法法436.7 旅行商问题旅行商

48、问题n旅行商问题的解空间是一个排列树。与在子集旅行商问题的解空间是一个排列树。与在子集树中进行最大收益和最小耗费分支限界搜索类树中进行最大收益和最小耗费分支限界搜索类似，该问题有两种实现的方法：似，该问题有两种实现的方法：1)只使用一个优先队列，队列中的每个元素中都只使用一个优先队列，队列中的每个元素中都包含到达根的路径。包含到达根的路径。2)保留一个部分解空间树和一个优先队列，优先保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。这里只队列中的元素并不包含到达根的路径。这里只实现方法实现方法(1)。2022年5月25日星期三第6章 分支限界分支限界法法44n用一个最小

49、优先队列来记录活结点，队列中结点的用一个最小优先队列来记录活结点，队列中结点的类型为类型为MinHeapNode。说明：。说明：ns表示结点在排列树中的层次表示结点在排列树中的层次n x：记录当前解。：记录当前解。 x0:s为根结点到当前结点的路径为根结点到当前结点的路径, 而剩余待访问的结点是而剩余待访问的结点是xs+1:n-1）ncc：从根结点到当前结点的耗费：从根结点到当前结点的耗费nLcost：该结点子树中任意叶结点中的最小耗费，表：该结点子树中任意叶结点中的最小耗费，表示子树费用的下界。示子树费用的下界。n rcost：从顶点：从顶点xsxn-1出发的所有边的最小耗费出发的所有边的最

50、小耗费之和。之和。nOperator T ( )const return lcost当类型为当类型为MinHeapNode(T)的数据被转换成为类型的数据被转换成为类型T时，其结时，其结果即为果即为lcost的值。的值。2022年5月25日星期三第6章 分支限界分支限界法法45n首先生成一个容量为首先生成一个容量为1000的最小堆，表示活结点最的最小堆，表示活结点最小优先队列。活结点按其小优先队列。活结点按其lcost值从最小堆中取出。值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中耗费接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费最小的边所具有的耗费MinOut。

51、如果某个顶点没有。如果某个顶点没有出边，则没有旅行路径，搜索终止。否则启动最小出边，则没有旅行路径，搜索终止。否则启动最小耗费分支限界搜索。根的孩子（结点耗费分支限界搜索。根的孩子（结点B）作为第一）作为第一个个E结点，在此结点上，所生成的旅行路径前缀只结点，在此结点上，所生成的旅行路径前缀只有一个顶点有一个顶点1，因此，因此s=0, x0=1, x1:n-1是剩余的顶是剩余的顶点（即顶点点（即顶点2,3, n）。旅行路径前缀）。旅行路径前缀1 的开销为的开销为0 ，即即cc=0 ，并且，并且，rcost=MinOuti。bestc 给出了当给出了当前能找到的最少的耗费值。初始时，由于没有找到

52、前能找到的最少的耗费值。初始时，由于没有找到任何旅行路径，因此任何旅行路径，因此bestc的值被设为的值被设为NoEdge。2022年5月25日星期三第6章 分支限界分支限界法法46ntemplateT Traveling :BBTSP(int v ) / 旅行商问题的最小耗费分枝定界算法旅行商问题的最小耗费分枝定界算法/ 最小堆最多可容纳最小堆最多可容纳1000个活结点个活结点MinHeapMinHeapNode H(1000);T *MinOut = new T n+1;/ 计算计算MinOuti=离开顶点离开顶点i的最小出边耗费的最小出边耗费T MinSum=0; / 离开顶点离开顶点i

53、的最小出边耗费之和的最小出边耗费之和for (int i = 1; i = n; i+) T Min = NoEdge;2022年5月25日星期三第6章 分支限界分支限界法法47nfor (int j = 1; j = n; j+) if (aij != NoEdge & (aij Min | Min = NoEdge) Min = aij; if (Min = NoEdge) return NoEdge; / 无回路无回路 MinOuti = Min; MinSum += Min;/ 把把E-结点初始化为树根结点初始化为树根MinHeapNode E;E.x = new int n;for

54、(i = 0; i n; i+) E.xi = i + 1;2022年5月25日星期三第6章 分支限界分支限界法法48nE.s = 0; / 局部旅行路径为局部旅行路径为x 1 : 0 E.cc = 0; / 其耗费为其耗费为0E.rcost = MinSum;T bestc = NoEdge; / 目前没有找到旅行路径目前没有找到旅行路径n/ 搜索排列树搜索排列树while (E.s n - 1) / 不是叶子不是叶子if (E.s = n - 2) / 叶子的父结点叶子的父结点/ 通过添加两条边来完成旅行通过添加两条边来完成旅行/ 检查新的旅行路径是不是更好检查新的旅行路径是不是更好if

55、(aE.xn-2E.xn-1 != NoEdge & aE.xn-11 != NoEdge & (E.cc +aE.xn-2E.xn-1 + aE.xn-11 bestc | bestc = NoEdge) 2022年5月25日星期三第6章 分支限界分支限界法法49n/ 找到更优的旅行路径找到更优的旅行路径 bestc = E.cc + aE.xn-2E.xn-1 + aE.xn-11; E.cc = bestc; E.lcost = bestc; E.s+; H.Insert(E);else delete E.x;else / 扩展子结点扩展子结点for (int i = E.s + 1;

56、i n; i+) if (aE.xE.sE.xi != NoEdge) / 可行的儿子结点可行的儿子结点2022年5月25日星期三第6章 分支限界分支限界法法50nT cc = E.cc + aE.xE.sE.xi;T rcost = E.rcost - MinOutE.xE.s;T b = cc + rcost; /下限下限if (b bestc | bestc = NoEdge) / 子树可能有更好的叶子子树可能有更好的叶子/ 把根保存到最小堆中把根保存到最小堆中 MinHeapNode N; N.x = new int n; for (int j = 0; j n; j+) N.xj = E.xj; N.xE.s+1 = E.xi; N.xi = E.xE.s+1;2022年5月25日星期三第6章 分支限界分支限界法法51n N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; H . I n s