1、分支限界法分支限界法第六章学习要点理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式（FIFO）分支限界法优先队列式分支限界法通过应用范例学习分支限界法的设计策略0-1背包问题图的广度优先遍历对于图G=(V,E), 从任意一点r开始，依次检查所有与r有关联的边(r,a1),(r, a2),(r,ak),当上面k条边检查完毕后，再依次检查所有与a1,a2,ak相关联的(a1,a11),(a1,a12),(a1,a1m),(a2,a21),(a2,a22),(a2,a2m)，(ak,ak1),(ak,ak2),(ak,akm)。依次类推，直到所有的边被检查，即所有顶点均被访问为止。图的广度
2、优先遍历 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树 广度优先遍历序列：ABCDEFGHI图的广度优先遍历 广度优先搜索是一种广度优先搜索是一种分层分层的搜索过程，每向前走一步可能访问的搜索过程，每向前走一步可能访问一批顶点。因此，广度优先搜索不是一个递归的过程，其算法一批顶点。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。也不是递归的。 为了实现逐层访问，算法中使用了一个队列，以记忆正在访问为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。的这一层和上一层的顶点，以便于向下一层访问。 为避免重复访问，需要一个辅助
3、数组为避免重复访问，需要一个辅助数组 visited ，给被访问过的，给被访问过的顶点加标记。顶点加标记。分支限界法引言分支限界法与回溯法的不同求解目标： 回溯法的求解目标：找出解空间树中满足约束条件的所有解； 分支限界法的求解目标：找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 分支限界法引言分支限界法与回溯法的不同搜索方式： 回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一
4、个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法的基本思想 分支限界法通常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。分支限界法的基本思想两种典型的解空间树： 子集树（子集树（Subset Trees）：）：当所给问题是从当所给问题是从n个元素的集合中找出满足某种性个元素的集合中找出满足某种性质的子集时，
5、相应的解空间树称为子集树。在子集树中，质的子集时，相应的解空间树称为子集树。在子集树中，|S0|=|S1|=|Sn-1|=c，即每个结点有相同数目的子树，通常情况下，即每个结点有相同数目的子树，通常情况下c=2，所以，子集树中共有，所以，子集树中共有2n个叶子结点，因此，遍历子集树需要个叶子结点，因此，遍历子集树需要O(2n)时间。时间。 排列树（排列树（Permutation Trees）：）：当所给问题是确定当所给问题是确定n个元素满足某种性质的排个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S0|=
6、n，|S1|=n-1，|Sn-1|=1，所以，排列树中共有，所以，排列树中共有n!个叶子结点，因此，遍历排个叶子结点，因此，遍历排列树需要列树需要O(n!)时间。时间。分支限界法的基本思想 在分支限界法中，每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程 这个过程一直持续到找到所求的解或活结点表为空时为止。活结点表：具有先进先出的性质，是队列。两个重要机制：产生分支（解空间树）两个重要机制：产生分
7、支（解空间树） 产生一个界限，能够终止许多分支（剪枝）产生一个界限，能够终止许多分支（剪枝） 分支限界法的基本思想分支限界法的适用范围： 分支限界法类似于回溯法，有一些问题其实无论用回溯法还是分支限界法都分支限界法类似于回溯法，有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。可以得到很好的解决，但是另外一些则不然。 下表列出了回溯法和分支限界法的一些区别：下表列出了回溯法和分支限界法的一些区别：方法方法对解空间树的对解空间树的搜索方式搜索方式存储结点的常用存储结点的常用数据结构数据结构结点存储特性结点存储特性常用应用常用应用回溯法回溯法深度优先搜索深度优先搜索
8、栈栈活结点的所有可行子活结点的所有可行子结点被遍历后才被从结点被遍历后才被从栈中弹出栈中弹出找出满足约束条件的所找出满足约束条件的所有解有解分支限分支限界法界法广度优先或最广度优先或最小消耗优先搜小消耗优先搜索索队列、优先队列队列、优先队列每个结点只有一每个结点只有一次成次成为扩展结点为扩展结点的机会的机会找出满足约束条件的一找出满足约束条件的一个解或特定意义下的最个解或特定意义下的最优解优解分支限界法的基本思想适合采用回溯法解决的问题 n后问题 问题定义：问题定义：在在nn的国际象棋棋盘上摆下的国际象棋棋盘上摆下n个皇后，使所有的皇后都不能攻击个皇后，使所有的皇后都不能攻击到对方，找出所有符
9、合要求的情况。到对方，找出所有符合要求的情况。 分析：分析：n后问题的解空间树是一棵后问题的解空间树是一棵排列树排列树，解与解之间不存在优劣的分别。直到搜，解与解之间不存在优劣的分别。直到搜索到叶结点时才能确定出一组解。索到叶结点时才能确定出一组解。采用回溯法可以系统地搜索问题的全部解。采用回溯法可以系统地搜索问题的全部解。考虑使用分支限界法？考虑使用分支限界法？分支限界法的基本思想既可以采用回溯法也可以采用分支限界法解决的问题 0-1背包问题 问题定义：问题定义：给定若干物品的重量和价值，以及一个背包的容量给定若干物品的重量和价值，以及一个背包的容量上限。求出一种方案使得背包中存放物品的价值
10、最高。上限。求出一种方案使得背包中存放物品的价值最高。 分析：分析：0-1背包问题的解空间树是一棵子集树，所要求的解具有背包问题的解空间树是一棵子集树，所要求的解具有最优性质最优性质。分支限界法的基本思想采用回溯法解决0-1背包问题的搜索策略 只要一个结点的左孩子结点是一个可行结点就搜索其只要一个结点的左孩子结点是一个可行结点就搜索其左子树左子树； 而对于而对于右子树右子树，需要构造一个，需要构造一个上界函数上界函数，只在这个上界函数的值超过当前最，只在这个上界函数的值超过当前最优解时才进入搜索。优解时才进入搜索。 随着搜索进程的推进，最优解不断得到加强，对搜索的限制就越来越严格。随着搜索进程
11、的推进，最优解不断得到加强，对搜索的限制就越来越严格。ABCDEFGHIJKLMNO11100100110010分支限界法的基本思想分支限界法两种方式： 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。 最常见的有以下两种方式：最常见的有以下两种方式：队列式（队列式（FIFO）分支限界法：）分支限界法：队列式分支限界法将活结点表组织成一个队列式分支限界法将活结点表组织成一个队列，并按队列的队列，并按队列的先进先出原则先进先出原则选取下一个结点为当前扩展结点。选取下一个结点为当前扩展结点。优先队列式分支限界法：优先队列式分支
12、限界法：优先队列式分支限界法将活结点表组织成一个优先队列式分支限界法将活结点表组织成一个优先队列优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。点成为当前扩展结点。常用堆来实现优先队列常用堆来实现优先队列分支限界法的基本思想 算法实现时，通常用极大（小）堆来实现最大（小）优先队列 极大堆满足一个节点必定不小于其子节点，极小堆正好相反。 极大堆中最大的元素必定是其根节点，堆排序算法正是根据这个特性而产生的：对一个序列，将其构造为极大堆，然后将根节点（数组首元素）和数组的尾元素交换，之后对除了尾元素之外的序列继
13、续以上过程，直到排序完成。 举例：0-1背包问题n=3时0-1背包问题的一个实例：w=16, 15, 15，p=45, 25, 25，c=30，其解空间是子集树。ABCDEFGHIJKLMNO11100100110010 用队列式分支限界法解此问题时，用一个队列来存储活结点表。 算法从根结点A开始。初始时活结点队列为空，结点A是当前扩展结点。结点A的2个儿子结点B和C均为可行结点，所以将这2个儿子结点按从左到右的顺序加入活结点队列，并且舍弃当前扩展结点A。ABCDEFGHIJKLMNO11100100110010活结点队列：ABC 依先进先出原则，下一个扩展结点是活结点队列的队首结点B。扩展结
14、点B得到其儿子结点D和E。 由于D是不可行结点，被舍去。 E是可行结点，被加入活结点队列。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30活结点队列：BCE 接下来，C成为当前扩展结点，它的2个儿子结点F和G均为可行结点，因此被加入到活结点队列中。 扩展下一个结点E得到结点J和K。J是不可行结点，被舍去。K是一个可行的叶结点，表示所求问题的一个可行解可行解，其价值为45。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30活结点队列：FEG活结点队列：FG 当
15、前活结点队列的队首结点F成为下一个扩展结点。它的2个儿子结点L和M均为叶结点。 L表示获得价值为50的可行解；M表示获得价值为25的可行解。 G是最后的一个扩展结点，其儿子结点N和O均为可行叶结点。最后，活结点队列已空，算法终止。 算法搜索得到最优值为50。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 优先队列式分支限界法也是从根结点A开始搜索解空间树的。 用一个极大堆极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结活结点所拥有的点所拥有的价值价值。ABCDEFGHIJKLMNO11100100110010w
16、=16, 15, 15，p=45, 25, 25，c=30ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 初始时堆为空，扩展结点A得到它的2个儿子结点B和C。 这2个结点均为可行结点，因此被加入到堆中，结点A被舍弃。结点B获得的当前价值是45，而结点C的当前价值为0。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 由于结点B的价值大于结点C的价值，所以结点B是堆中最大元素，从而成为下一个扩展结点。 扩展结点B得到结点D和E。D不是可行结点，被舍去。E是
17、可行结点被加入到堆中。E的价值为45，成为当前堆中最大元素，从而成为下一个扩展结点。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 扩展结点E得到2个叶结点J和K。J是不可行结点，被舍弃。K是一个可行叶结点，表示所求问题的一个可行解，其价值为45。 此时，堆中仅剩下一个活结点C。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 此时，堆中仅剩下一个活结点C，它成为当前扩展结点。它的2个儿子结点F和G均为可行结点，因此被插入到当前堆中。 结点F的价值为25
18、，是堆中最大元素，成为下一个扩展结点。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 结点F的2个儿子结点L和M均为叶结点。叶结点L相应于价值为50的可行解。 叶结点M相应于价值为25的可行解。叶结点L所相应的解成为当前最优解。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30 最后，结点G成为扩展结点，其儿子结点N和O均为叶结点，它们的价值分别为25和0。 接下来，存储活结点的堆已空，算法终止。算法搜索得到最优值为50。相应的最优解是从根结点A到结点L的
19、路径(0,1,1)。 当要寻求问题的一个最优解时，与回溯法时类似地可以用剪枝函数剪枝函数来加速搜索。该函数给出每一个可行结点相应的子树可能获得的最大价值的最大价值的上界上界。 如果这个上界不会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去。 另一方面，也可以将上界函数确定的每个结点的上界值作为优先级，以该优以该优先级的先级的非增序非增序抽取当前扩展结点抽取当前扩展结点。这种策略有时可以更迅速地找到最优解。分析解空间树的动态搜索过程（最小消耗优先） 分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down, up。 然后，按照广度优先策略遍历问题的解空间树
20、，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（表PT）中。 依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。解空间树的动态搜索过程（最小消耗优先） 随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。 当搜索到一个叶结点时：如果该结点的目标函数值是表PT中的极值，则该叶子结点对应的解就是问题的最优解。否则，根据这个叶结点调整目标函数的界，
21、依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。举例：0-1背包问题假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品物品重量重量 w价值价值 v价值价值/重量重量 v/w144010274263525543124举例：0-1背包问题 应用贪心法求得近似解为(1, 0, 0, 0)，获得的价值为40，这可以作为0/1背包问题的下界。 如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个
22、物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界40, 100。 限界函数为： )()(11iiwvwWvub已装入价值已装入价值剩余容量剩余容量剩下物品最大单位价值剩下物品最大单位价值w=0, v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11无效解无效解w=4, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12无效解无效解w=9, v=65ub=65234567891分支限界法求解0-1背包问题W=10, n=4 wi=(4, 7, 5, 3)vi
23、=(40, 42, 25, 12)()(11iiwvwWvub分支限界法求解0-1背包问题分支限界法求解分支限界法求解0-1背包问题，具体的搜索过程如下：背包问题，具体的搜索过程如下：（1）在根结点）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值，没有将任何物品装入背包，因此，背包的重量和获得的价值均为均为0，根据限界函数计算结点，根据限界函数计算结点1的目标函数值为的目标函数值为1010=100；（2）在结点）在结点2，将，将物品物品1装入背包装入背包，因此，背包的重量为，因此，背包的重量为4，获得的价值为，获得的价值为40，目标函数值为目标函数值为40 + (10-4)6
24、=76，将结点将结点2加入待处理结点表加入待处理结点表PT中中；在结点；在结点3，没有将物品没有将物品1装入背包，因此，背包的重量和获得的价值仍为装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为，目标函数值为10660，将结点将结点3加入表加入表PT中中；（3）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进行搜索；优先进行搜索； )()(11iiwvwWvub分支限界法求解0-1背包问题)()(11iiwvwWvub（4）在结点）在结点4，将物品，将物品2装入背包，因此，背包的重量为装入背包，因此，背包的重量为11，不满足约束条件，不满足约束条件，
25、将结点将结点4丢弃丢弃；在结点；在结点5，没有将物品，没有将物品2装入背包，因此，背包的重量和获得的价装入背包，因此，背包的重量和获得的价值与结点值与结点2相同，目标函数值为相同，目标函数值为40 + (10-4)5=70，将结点将结点5加入表加入表PT中中；（5）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5优先进行搜索；优先进行搜索；（6）在结点）在结点6，将物品，将物品3装入背包，因此，背包的重量为装入背包，因此，背包的重量为9，获得的价值为，获得的价值为65，目，目标函数值为标函数值为65 + (10-9)4=69，将结点，将结点6加入表加入表PT中；在结
26、点中；在结点7，没有将物品，没有将物品3装入装入背包，因此，背包的重量和获得的价值与结点背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为相同，目标函数值为40 + (10-4)464，将结点将结点6加入表加入表PT中中；分支限界法求解0-1背包问题)()(11iiwvwWvub（7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行搜索；优先进行搜索；（8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，背包的重量为12，不满足约束条件，不满足约束条件，将结点将结点8丢弃丢弃；在结点；在结点9，没有将物品，没有将物品4
27、装入背包，因此，背包的重量和获得的价装入背包，因此，背包的重量和获得的价值与结点值与结点6相同，目标函数值为相同，目标函数值为65；（9）由于结点）由于结点9是叶子结点，同时结点是叶子结点，同时结点9的目标函数值是表的目标函数值是表PT中的极大值，所以，中的极大值，所以，结点结点9对应的解即是问题的最优解，搜索结束。对应的解即是问题的最优解，搜索结束。分支限界法的设计思路 假设假设求解最大化问题求解最大化问题，解向量为，解向量为X=(x1, x2, , xn)，其中，其中，xi的取值范围为某个的取值范围为某个有穷集合有穷集合Si，|Si|=ri（1in）。）。 在使用分支限界法搜索问题的解空间
28、树时，首先在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数根据限界函数估算目标函数的界的界down, up，然后，然后从根结点出发从根结点出发，扩展根结点的，扩展根结点的r1个孩子结点，从而构成个孩子结点，从而构成分量分量x1的的r1种可能的取值方式。种可能的取值方式。 对这对这r1个孩子结点分别估算可能取得的个孩子结点分别估算可能取得的目标函数值目标函数值bound(x1)，其含义是以该孩，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于子结点为根的子树所可能取得的目标函数值不大于bound(x1)，也就是部分解，也就是部分解应满足：应满足：bound(x1)bo
29、und(x1, x2) bound(x1, x2, , xk) bound(x1, x2, , xn)分支限界法的设计思路 若某孩子结点的若某孩子结点的目标函数值目标函数值超出目标函数的界超出目标函数的界，则将该，则将该孩子结点丢弃孩子结点丢弃；否则，；否则，将该孩子结点保存在待处理结点表将该孩子结点保存在待处理结点表PT中。中。 从表从表PT中选取使中选取使目标函数取得极大值的结点目标函数取得极大值的结点作为作为下一次扩展的根结点下一次扩展的根结点，重复，重复上述过程，当到达一个叶子结点时，就得到了一个可行解上述过程，当到达一个叶子结点时，就得到了一个可行解X=(x1, x2, , xn)及
30、及其目标函数值其目标函数值bound(x1, x2, , xn)。分支限界法的设计思路 如果如果bound(x1, x2, , xn)是是表表PT中目标函数值最大中目标函数值最大的结点，则的结点，则bound(x1, x2, , xn)就是所求就是所求问题的最大值问题的最大值，(x1, x2, , xn)就是就是问题的最优解问题的最优解； 如果如果bound(x1, x2, , xn)不是表不是表PT中目标函数值最大的结点，说明还存在某个中目标函数值最大的结点，说明还存在某个部分解对应的结点，其上界大于部分解对应的结点，其上界大于bound(x1, x2, , xn)。于是，用。于是，用bou
31、nd(x1, x2, , xn)调整目标函数的下界，即令调整目标函数的下界，即令down=bound(x1, x2, , xn)，并将，并将表表PT中超出目中超出目标函数下界标函数下界down的结点删除的结点删除，然后选取目标函数值取得极大值的结点作为下，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表某个叶子结点的目标函数值在表PT中最中最大大。 分支限界法求解最大化问题的一般过程1根据根据限界函数限界函数确定确定目标函数目标函数的界的界down, up；2将将待处理结点表待处理结点表PT初始化为空；初始化为
32、空；3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的目标函数值value; 3.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大 4.1 i=表表PT中值最大的结点；中值最大的结点； 4.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作 4.2.1 估算结点估算结点x的目标函数值的目标函数值value; 4.2.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中
33、； 4.2.3 若若(结点结点x是叶子结点且结点是叶子结点且结点x的的value值在表值在表PT中中最大最大)， 则则将结点将结点x对应的解输出对应的解输出，算法结束算法结束； 4.2.4 若若(结点结点x是叶子结点但结点是叶子结点但结点x的的value值在表值在表PT中中不是最大不是最大)， 则令则令down=value，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除；分支限界法解题步骤 在问题的边带权的解空间树中进行广度优先搜索 找一个叶结点使其对应路径的权最小(最大) 当搜索到达一个扩展结点时,一次性扩展它的所有儿子 将满足约束条件且最小耗费函数目标函数限界的
34、儿子,插入活结点表中 从活结点表中取下一结点同样扩展 直到找到所需的解或活动结点表为空为止应用分支限界法的关键问题（1 1）如何确定合适的）如何确定合适的限界函数限界函数（2 2）如何组织）如何组织待处理结点表待处理结点表（3 3）如何确定最优解中的）如何确定最优解中的各个分量各个分量如何确定最优解中的各个分量分支限界法对问题的解空间树中结点的处理是分支限界法对问题的解空间树中结点的处理是跳跃式的跳跃式的，回溯也不是单纯地，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表点的目
35、标函数值在表PT中最大时（假设求解最大化问题），求得了问题的最中最大时（假设求解最大化问题），求得了问题的最优值，但是，优值，但是，却无法求得该叶子结点对应的最优解中的各个分量却无法求得该叶子结点对应的最优解中的各个分量。这个问题。这个问题可以用如下方法解决：可以用如下方法解决： 对每个扩展结点保存该结点到根结点的路径对每个扩展结点保存该结点到根结点的路径；在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。回溯到根结点，以确定最优解中的各个分量。如何确定最优解中的各个分量例如前
36、面的例如前面的0-1背包问题，为了对每个扩展结点保存该结点到根结点的路径，背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解将部分解(x1, , xi)和该部分解的目标函数值都存储在待处理结点表和该部分解的目标函数值都存储在待处理结点表PT中，在中，在搜索过程中表搜索过程中表PT的状态如图所示：的状态如图所示：(0)60 (1,0,0)64 (1,0,1,0)65(a) 扩展根结点后表扩展根结点后表PT状态状态 (b) 扩展结点扩展结点2后表后表PT状态状态(c) 扩展结点扩展结点5后表后表PT状态状态 (d) 扩展结点扩展结点6后表后表PT状态，最优解为状态，最优解为(1,0,1
37、,0)65确定确定0/1背包问题最优解的各分量背包问题最优解的各分量(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 0-1背包问题算法思想: 先对输入数据进行预处理，将物品依其单位重量价值从大到小进行排列。 在优先队列分支限界法中，结点优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值。 用一个最大堆来实现活结点优先队列0-1背包问题u算法首先检查当前扩展结点的左儿子结点的可行性。u如果左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。u当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时,才
38、将它加入子集树和活结点优先队列。u当扩展到叶节点时为问题的最优值。0-1背包问题上界函数while (i = n & wi = cleft) / n表示物品总数，cleft为剩余空间 cleft -= wi; /wi表示i所占空间 b += pi; /pi表示i的价值 i+; if (i = n) b += pi/wi*cleft; / 装填剩余容量装满背包return b; /b为上界函数0-1背包问题 while (i != n+1) / 非叶结点非叶结点 / 检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt = cw + wi; if (wt bestp) be
39、stp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1); / 检查当前扩展结点的右儿子结点检查当前扩展结点的右儿子结点 if (up = bestp) / 右子树可能含最优解右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); / 取下一个扩展节点取下一个扩展节点 分支限界搜索过程分支限界搜索过程分支限界法的时间性能 分支限界法和回溯法实际上都属于蛮力穷举法蛮力穷举法，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶指数阶。 与回溯法不同的是，分支限
40、界法首先扩展解空间树中的上层结点，并采用限界函数，有利于实行大范围剪枝。同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。分支限界法的时间性能 分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。法设计的复杂性。 首先，首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且而且对于具体的问题实例，通常需
41、要进行大量实验，才能确定一个好的限界对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数函数； 其次，其次，由于分支限界法对解空间树中结点的处理是跳跃式的由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，个分量，需要对每个扩展结点保存该结点到根结点的路径需要对每个扩展结点保存该结点到根结点的路径，或者，或者在搜索过程在搜索过程中构建搜索经过的树结构中构建搜索经过的树结构，这使得算法的设计较为复杂；，这使得算法的设计较为复杂；
