第6章_分支限界法

1、第第6章章 分支限界法分支限界法2022-6-27算法设计与分析2第第6章章 分支限界法分支限界法学习要点学习要点 理解分支限界法的理解分支限界法的剪枝搜索剪枝搜索策略策略 掌握分支限界法的算法框架掌握分支限界法的算法框架 队列式（队列式（FIFO）分支限界法）分支限界法 优先队列式分支限界法优先队列式分支限界法 通过应用范例学习分支限界法的设计策略通过应用范例学习分支限界法的设计策略 0-1背包问题背包问题2022-6-27算法设计与分析36.1 分支限界法的基本思想分支限界法的基本思想 分支限界法与回溯法的不同分支限界法与回溯法的不同求解目标求解目标： 回溯法回溯法的求解目标：的求解目标：

2、找出找出T（解空间状态树）（解空间状态树）中满足约束条件的所有解；中满足约束条件的所有解； 分支限界法分支限界法的求解目标：的求解目标：找出满足约束条件找出满足约束条件的一个解，或是在满足约束条件的解中找出的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，使用某一目标函数值达到极大或极小的解，即在某种意义下的即在某种意义下的最优解最优解。 2022-6-27算法设计与分析4分支限界法与回溯法的不同搜索方式分支限界法与回溯法的不同搜索方式 回溯法以回溯法以深度优先深度优先的方式搜索解空间树的方式搜索解空间树T，而分支限界法，而分支限界法则以则以广度优先广度优先或以或以最

3、小耗费优先最小耗费优先的方式搜索解空间树的方式搜索解空间树T。 分支限界法的搜索策略：在扩展结点处，先生成其所有的分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的儿子结点（分支），然后再从当前的活结点表活结点表中选择下一中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个的进程，在每一活结点处，计算一个函数值（限界）函数值（限界），并，并根据这些已计算出的函数值，从当前活结点表中选择一个根据这些已计算出的函数值，从当前活结点表中选择一个最有利的最有利的结点作为扩展结点，使

4、搜索朝着解空间树上有最结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个优解的分支推进，以便尽快地找出一个最优解最优解。2022-6-27算法设计与分析5分支限界法的基本思想分支限界法的基本思想 分支限界法通常以分支限界法通常以广度优先广度优先或以或以最小耗费（最最小耗费（最大效益）优先大效益）优先的方式搜索问题的解空间树。的方式搜索问题的解空间树。 问题的解空间树是表示问题解空间的一棵有序问题的解空间树是表示问题解空间的一棵有序树，常见的有树，常见的有子集树子集树和和排列树排列树。2022-6-27算法设计与分析6回顾回顾：两种典型的解空间树两种典型的解空间树 子集

5、树（子集树（Subset Trees）：）：当所给问题是从当所给问题是从n个元素的集合个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，树。在子集树中，|S0|=|S1|=|Sn-1|=c，即每个结点有相同，即每个结点有相同数目的子树，通常情况下数目的子树，通常情况下c=2，所以，子集树中共有，所以，子集树中共有2n个叶个叶子结点，因此，遍历子集树需要子结点，因此，遍历子集树需要O(2n)时间。时间。 排列树（排列树（Permutation Trees）：）：当所给问题是确定当所给问题是确定n个元个元素满足某种性质的

6、排列时，相应的解空间树称为排列树。素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，在排列树中，通常情况下，|S0|=n，|S1|=n-1，|Sn-1|=1，所以，排列树中共有所以，排列树中共有n!个叶子结点，因此，遍历排列树需个叶子结点，因此，遍历排列树需要要O(n!)时间。时间。2022-6-27算法设计与分析7分支限界法的基本思想分支限界法的基本思想 每一个活结点每一个活结点只有一次机会只有一次机会成为扩展结点成为扩展结点 活结点一旦成为扩展结点，就一次性产生其所有儿子活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致结点

7、。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被非最优解的儿子结点被舍弃舍弃，其余儿子结点被，其余儿子结点被加入加入活活结点表结点表中中 从活结点表中取下一结点成为当前扩展结点，并重复从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程上述结点扩展过程 这个过程一直持续到这个过程一直持续到找到所求的解或活结点表为空找到所求的解或活结点表为空时时为止。为止。活结点表：具有先进先出的性质，是队列。活结点表：具有先进先出的性质，是队列。2022-6-27算法设计与分析8分支限界法的适用范围分支限界法的适用范围 分支限界法类似于回溯法，有一些问题其实无论用回溯分支限界法类似于回

8、溯法，有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一法还是分支限界法都可以得到很好的解决，但是另外一些则不然。些则不然。 下表列出了回溯法和分支限界法的一些区别：下表列出了回溯法和分支限界法的一些区别：方法方法对解空间树的搜对解空间树的搜索方式索方式存储结点的常存储结点的常用数据结构用数据结构结点存储特性结点存储特性常用应用常用应用回溯法回溯法深度优先搜索深度优先搜索栈栈活结点的所有活结点的所有可行子结点被可行子结点被遍历后才被从遍历后才被从栈中弹出栈中弹出找出满足约束找出满足约束条件的所有解条件的所有解分支限界分支限界法法广度优先或最小广度优先或最小消耗优先搜索消耗

9、优先搜索队列、优先队队列、优先队列列每个结点只有每个结点只有一一次成为扩展次成为扩展结点结点的机会的机会找出满足约束找出满足约束条件的一个解条件的一个解或特定意义下或特定意义下的最优解的最优解2022-6-27算法设计与分析9A、适合采用回溯法解决的问题、适合采用回溯法解决的问题 n后问题后问题 问题定义：问题定义：在在nn的国际象棋棋盘上摆下的国际象棋棋盘上摆下n个皇后，使所个皇后，使所有的皇后都不能攻击到对方，找出所有符合要求的情况。有的皇后都不能攻击到对方，找出所有符合要求的情况。 分析：分析： n后问题的解空间树是一棵后问题的解空间树是一棵排列树排列树，解与解之间不存在，解与解之间不存

10、在优劣的分别。直到搜索到叶结点时才能确定出一组解。优劣的分别。直到搜索到叶结点时才能确定出一组解。 采用回溯法可以系统地搜索问题的全部解。采用回溯法可以系统地搜索问题的全部解。 考虑使用分支限界法？考虑使用分支限界法？2022-6-27算法设计与分析10B、既可以采用回溯法也可以采用分支限、既可以采用回溯法也可以采用分支限界法解决的问题界法解决的问题 0-1背包问题背包问题 问题定义：问题定义：给定若干物品的重量和价值，以及给定若干物品的重量和价值，以及一个背包的容量上限。求出一种方案使得背包一个背包的容量上限。求出一种方案使得背包中存放物品的价值最高。中存放物品的价值最高。 分析：分析：0-

11、1背包问题的解空间树是一棵子集树，背包问题的解空间树是一棵子集树，所要求的解具有所要求的解具有最优性质最优性质。2022-6-27算法设计与分析11采用采用回溯法回溯法解决解决0-1背包问题的搜索策略背包问题的搜索策略 只要一个结点的左孩子结点是一个可行结点就搜索其只要一个结点的左孩子结点是一个可行结点就搜索其左子左子树树； 而对于而对于右子树右子树，需要用，需要用贪心算法贪心算法构造一个构造一个上界函数上界函数，只在，只在这个上界函数的值超过当前最优解时才进入搜索。这个上界函数的值超过当前最优解时才进入搜索。 随着搜索进程的推进，最优解不断得到加强，对搜索的限随着搜索进程的推进，最优解不断得

12、到加强，对搜索的限制就越来越严格。制就越来越严格。ABCDEFGHIJKLMNO111001001100102022-6-27算法设计与分析12分支限界法两种方式分支限界法两种方式 从活结点表中选择下一扩展结点的不同方式导致不同的从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。分支限界法。 最常见的有以下两种方式：最常见的有以下两种方式： 队列式（队列式（FIFO）分支限界法：）分支限界法：队列式分支限界法将队列式分支限界法将活结点表组织成一个队列，并按队列的活结点表组织成一个队列，并按队列的先进先出原先进先出原则则选取下一个结点为当前扩展结点。选取下一个结点为当前扩展结点。 优先

13、队列式分支限界法：优先队列式分支限界法：优先队列式分支限界法将优先队列式分支限界法将活结点表组织成一个活结点表组织成一个优先队列优先队列，按优先队列中规定，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当的结点优先级选取优先级最高的下一个结点成为当前扩展结点。前扩展结点。2022-6-27算法设计与分析13举例举例：0-1背包问题背包问题 n=3时时0-1背包问题的一个实例：背包问题的一个实例：w=16, 15, 15，p=45, 25, 25，c=30，其解空间是子集树。，其解空间是子集树。ABCDEFGHIJKLMNO111001001100102022-6-27算法设计与分析

14、14 用用队列式分支限界法队列式分支限界法解此问题时，用一个解此问题时，用一个队列队列来存储活结点来存储活结点表。表。 算法从根结点算法从根结点A开始。初始时活结点队列为空，结点开始。初始时活结点队列为空，结点A是当是当前扩展结点。结点前扩展结点。结点A的的2个儿子结点个儿子结点B和和C均为可行结点，所均为可行结点，所以将这以将这2个儿子结点按个儿子结点按从左到右从左到右的顺序加入活结点队列，并的顺序加入活结点队列，并且且舍弃舍弃当前扩展结点当前扩展结点A。ABCDEFGHIJKLMNO11100100110010活结点队列：活结点队列：ABC2022-6-27算法设计与分析15 依依先进先出

15、先进先出原则，下一个扩展结点是活结点队列的队首结点原则，下一个扩展结点是活结点队列的队首结点B。扩展结点。扩展结点B得到其儿子结点得到其儿子结点D和和E。 由于由于D是是不可行结点不可行结点，被舍去。，被舍去。 E是可行结点，被加入活结点队列。是可行结点，被加入活结点队列。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30活结点队列：活结点队列：BCE2022-6-27算法设计与分析16 接下来，接下来，C成为当前扩展结点，它的成为当前扩展结点，它的2个儿子结点个儿子结点F和和G均为均为可行结点，因此被加入到活结点队列中。可行

16、结点，因此被加入到活结点队列中。 扩展下一个结点扩展下一个结点E得到结点得到结点J和和K。J是不可行结点，被舍去。是不可行结点，被舍去。K是一个可行的叶结点，表示所求问题的一个是一个可行的叶结点，表示所求问题的一个可行解可行解，其价，其价值为值为45。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30活结点队列：活结点队列：FEG活结点队列：活结点队列：FG2022-6-27算法设计与分析17当前活结点队列的队首结点当前活结点队列的队首结点F成为下一个扩展结点。它的成为下一个扩展结点。它的2个儿子结点个儿子结点L和和M均为叶结

17、点。均为叶结点。L表示获得价值为表示获得价值为50的可行解；的可行解；M表示获得价值为表示获得价值为25的可行解。的可行解。G是最后的一个扩展结点，其儿子结点是最后的一个扩展结点，其儿子结点N和和O均为可行叶结点。最后，均为可行叶结点。最后，活结点队列已空，算法终止活结点队列已空，算法终止。算法搜索得到最优值为算法搜索得到最优值为50。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析18 优先队列式分支限界法优先队列式分支限界法也是从根结点也是从根结点A开始搜索解空间开始搜索解空间树的。树的。

18、 用一个用一个极大堆极大堆来表示活结点表的优先队列，该优先队列来表示活结点表的优先队列，该优先队列的优先级定义为的优先级定义为活结点所拥有的活结点所拥有的价值价值。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析19 初始时堆为空，扩展结点初始时堆为空，扩展结点A得到它的得到它的2个儿子结点个儿子结点B和和C。 这这2个结点均为个结点均为可行结点可行结点，因此被加入到堆中，结点，因此被加入到堆中，结点A被被舍弃。结点舍弃。结点B获得的当前价值是获得的当前价值是45，而结点，而结点C的当前价值的

19、当前价值为为0。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析20 由于结点由于结点B的价值大于结点的价值大于结点C的价值，所以结点的价值，所以结点B是堆中最是堆中最大元素，从而成为下一个扩展结点。大元素，从而成为下一个扩展结点。 扩展结点扩展结点B得到结点得到结点D和和E。D不是可行结点，被舍去。不是可行结点，被舍去。E是是可行结点被加入到堆中。可行结点被加入到堆中。E的价值为的价值为45，成为当前堆中最大，成为当前堆中最大元素，从而成为下一个扩展结点。元素，从而成为下一个扩展结点。ABC

20、DEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析21 扩展结点扩展结点E得到得到2个叶结点个叶结点J和和K。J是不可行结点，被舍是不可行结点，被舍弃。弃。K是一个可行叶结点，表示所求问题的一个可行解，是一个可行叶结点，表示所求问题的一个可行解，其价值为其价值为45。 此时，堆中仅剩下一个活结点此时，堆中仅剩下一个活结点C。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析22 此时，堆中仅剩下一个活结

21、点此时，堆中仅剩下一个活结点C，它成为当前扩展结点。，它成为当前扩展结点。它的它的2个儿子结点个儿子结点F和和G均为可行结点，因此被插入到当前均为可行结点，因此被插入到当前堆中。堆中。 结点结点F的价值为的价值为25，是堆中最大元素，成为下一个扩展结点。，是堆中最大元素，成为下一个扩展结点。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析23 结点结点F的的2个儿子结点个儿子结点L和和M均为叶结点。叶结点均为叶结点。叶结点L相应相应于价值为于价值为50的可行解。的可行解。 叶结点叶结点M相应于

22、价值为相应于价值为25的可行解。叶结点的可行解。叶结点L所相应的所相应的解成为解成为当前最优解当前最优解。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析24 最后，结点最后，结点G成为扩展结点，其儿子结点成为扩展结点，其儿子结点N和和O均为叶结均为叶结点，它们的价值分别为点，它们的价值分别为25和和0。 接下来，接下来，存储活结点的堆已空，算法存储活结点的堆已空，算法终止终止。算法搜索得到。算法搜索得到最优值为最优值为50。相应的最优解是从根结点。相应的最优解是从根结点A到结点到结点L的路径

23、的路径(0,1,1)。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析25分析分析 当要寻求问题的一个最优解时，与回溯法时类似地可以当要寻求问题的一个最优解时，与回溯法时类似地可以用用剪枝函数剪枝函数来加速搜索。该函数给出每一个可行结点相来加速搜索。该函数给出每一个可行结点相应的子树可能获得的应的子树可能获得的最大价值的最大价值的上界上界。 如果这个上界不会比当前最优值更大，则说明相应的子如果这个上界不会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去。树中不含问题的最优解，

24、因而可以剪去。 另一方面，也可以将上界函数确定的每个结点的上界值另一方面，也可以将上界函数确定的每个结点的上界值作为优先级，作为优先级，以该优先级的以该优先级的非增序非增序抽取当前扩展结点抽取当前扩展结点。这种策略有时可以更迅速地找到最优解。这种策略有时可以更迅速地找到最优解。2022-6-27算法设计与分析26解空间树的动态搜索过程解空间树的动态搜索过程（最小消耗优先）（最小消耗优先） 分支限界法首先确定一个合理的分支限界法首先确定一个合理的限界函数限界函数，并根据限界函，并根据限界函数确定数确定目标函数的界目标函数的界down, up。 然后，按照广度优先策略遍历问题的解空间树，在分支结然

25、后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果子结点的目标函数的可能取值，如果某孩子结点的目标函某孩子结点的目标函数可能取得的值超出目标函数的界，则将其数可能取得的值超出目标函数的界，则将其丢弃丢弃，因为从，因为从这个结点生成的解不会比目前已经得到的解更好；否则，这个结点生成的解不会比目前已经得到的解更好；否则，将其加入将其加入待处理结点表待处理结点表（表表PT）中。）中。 依次从表依次从表PT中选取使目标函数的值取得中选取使目标函数的值取得极值极值的结点成为的

26、结点成为当前扩展结点，重复上述过程，直到找到最优解。当前扩展结点，重复上述过程，直到找到最优解。2022-6-27算法设计与分析27 随着这个遍历过程的不断深入，表随着这个遍历过程的不断深入，表PT中所估算的目标函中所估算的目标函数的界越来越接近问题的最优解。数的界越来越接近问题的最优解。 当搜索到一个当搜索到一个叶结点叶结点时：时： 如果该结点的目标函数值是表如果该结点的目标函数值是表PT中的中的极值极值，则该叶则该叶子结点对应的解就是问题的最优解。子结点对应的解就是问题的最优解。 否则，根据这个叶结点调整目标函数的界否则，根据这个叶结点调整目标函数的界，依次考察依次考察表表PT中的结点，将

27、超出目标函数界的结点丢弃，然中的结点，将超出目标函数界的结点丢弃，然后从表后从表PT中选取使目标函数取得极值的结点继续进中选取使目标函数取得极值的结点继续进行扩展。行扩展。2022-6-27算法设计与分析28 加入限界的优先队列式分支限界法加入限界的优先队列式分支限界法也是从根结点也是从根结点A开始开始搜索解空间树的。搜索解空间树的。 用一个用一个极大堆极大堆来表示活结点表的优先队列，该优先队列来表示活结点表的优先队列，该优先队列的优先级定义为的优先级定义为活结点所拥有的活结点所拥有的价值价值。用。用BOUND来计来计算其上界，将上界算其上界，将上界当前最优解的结点剪枝。当前最优解的结点剪枝。

28、ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析29 初始时堆为空，扩展结点初始时堆为空，扩展结点A得到它的得到它的2个儿子结点个儿子结点B和和C。 这这2个结点均为个结点均为可行结点可行结点，因此被加入到堆中，结点，因此被加入到堆中，结点A被被舍弃。结点舍弃。结点B获得的当前价值是获得的当前价值是45，而结点，而结点C的当前价值的当前价值为为0。Bestp = 0，C.up = 50。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25

29、，c=302022-6-27算法设计与分析30 由于结点由于结点B的价值大于结点的价值大于结点C的价值，所以结点的价值，所以结点B是堆中最是堆中最大元素，从而成为下一个扩展结点。大元素，从而成为下一个扩展结点。 扩展结点扩展结点B得到结点得到结点D和和E。D不是可行结点，被舍去。不是可行结点，被舍去。E是是可行结点被加入到堆中。可行结点被加入到堆中。E的价值为的价值为45，成为当前堆中最大，成为当前堆中最大元素，从而成为下一个扩展结点。元素，从而成为下一个扩展结点。 Bestp = 0，E.up = 68。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=

30、45, 25, 25，c=302022-6-27算法设计与分析31 扩展结点扩展结点E得到得到2个叶结点个叶结点J和和K。J是不可行结点，被舍是不可行结点，被舍弃。弃。K是一个可行叶结点，表示所求问题的一个可行解，是一个可行叶结点，表示所求问题的一个可行解，其价值为其价值为45。 Bestp = 45。 此时，堆中仅剩下一个活结点此时，堆中仅剩下一个活结点C。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析32 此时，堆中仅剩下一个活结点此时，堆中仅剩下一个活结点C，它成为当前扩展结点。，它成为当前扩展结点。它的它的2个儿子结点个儿子结点F和和G均为可行结点。均为可行结点。 Bestp = 45，G.up = 25 bestp，结点，结点G被剪枝。被剪枝。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-6-27算法设计与分析33结点结点F的的2个儿子结点个儿子结点L和和M均为叶结点。均为叶结点。 Bestp = 45，M.up = 25 b