《分支限界法》(1)ppt课件

1、.分支限界法类似于回溯法，也是在问题的解空间上搜分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。普通情况下，分支限界法与回溯索问题解的算法。普通情况下，分支限界法与回溯法的求解目的不同。回溯法的求解目的是找出解空法的求解目的不同。回溯法的求解目的是找出解空间中满足约束条件的一切解，而分支限界法的求解间中满足约束条件的一切解，而分支限界法的求解目的那么是找出满足约束条件的一个解，或是在满目的那么是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目的函数值到达极大足约束条件的解中找出使某一目的函数值到达极大或极小的解，即在某种意义下的最优解。或极小的解，即在某种意义下的最

2、优解。.由于求解目的不同，导致分支限界法与回溯法对解空由于求解目的不同，导致分支限界法与回溯法对解空间的搜索方式也不一样。回溯法以深度优先的方式间的搜索方式也不一样。回溯法以深度优先的方式搜索解空间，而分支限界法那么以广度优先或以最搜索解空间，而分支限界法那么以广度优先或以最小耗费优先的方式搜索解空间。小耗费优先的方式搜索解空间。分支限界法的搜索战略是：在扩展结点处，先生成其分支限界法的搜索战略是：在扩展结点处，先生成其一切的儿子结点分支，然后再从当前的活结点一切的儿子结点分支，然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩表中选择下一个扩展结点。为了有效地选择下一扩展结点，

3、加速搜索的进程，在每一活结点处，计算展结点，加速搜索的进程，在每一活结点处，计算一个函数值限界，并根据函数值，从当前活结一个函数值限界，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方法称为分支限界法。找出一个最优解。这种方法称为分支限界法。. 分支限界法常以广度优先或以最小耗费最大效益分支限界法常以广度优先或以最小耗费最大效益优先的方式搜索问题的解空间树。在搜索问题的解优先的方式搜索问题的解空间树。在搜索问题的解空间树时

4、，分支限界法与回溯法的主要区别在于它空间树时，分支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在分支们对当前扩展结点所采用的扩展方式不同。在分支限界法中，每一个活结点只需一次时机成为扩展结限界法中，每一个活结点只需一次时机成为扩展结点。活结点一旦成为扩展结点，就一次性产生其一点。活结点一旦成为扩展结点，就一次性产生其一切儿子结点。在这些儿子结点中，导致不可行解或切儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其他儿子结点被导致非最优解的儿子结点被舍弃，其他儿子结点被参与活结点表中。以后，从活结点表中取下一结点参与活结点表中。以后，从活结点表中取

5、下一结点成为当前扩展结点，并反复上述结点扩展过程。这成为当前扩展结点，并反复上述结点扩展过程。这个过程不断继续到找到所需的解或活结点表为空时。个过程不断继续到找到所需的解或活结点表为空时。.从活结点表中选择下一扩展结点的不同方式导致不同从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有两种方式。的分支限界法。最常见的有两种方式。 1队列式队列式FIFO分支限界法分支限界法 队列式分支限界法将活结点表组织成一个队列，并队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原那么选取下一个结点为当前扩按队列的先进先出原那么选取下一个结点为当前扩展结点。展结点。 2优先队列

6、式分支限界法优先队列式分支限界法 优先队列式的分支限界法将活结点表组织成一个优优先队列式的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。先级最高的下一个结点成为当前扩展结点。.优先队列中规定的结点优先级常用一个与该结点相关优先队列中规定的结点优先级常用一个与该结点相关的数值的数值P来表示。结点优先级的高低与来表示。结点优先级的高低与P值的大小相值的大小相关。最大优先队列规定关。最大优先队列规定P值较大的结点优先级较高。值较大的结点优先级较高。在算法实现时通常用最大堆来实现最大优先队列

7、，在算法实现时通常用最大堆来实现最大优先队列，用最大堆的用最大堆的 Deletemax运算抽取堆中下一个结点成运算抽取堆中下一个结点成为当前扩展结点，表达最大效益优先的原那么。为当前扩展结点，表达最大效益优先的原那么。类似地，最小优先队列规定类似地，最小优先队列规定P值较小的结点优先级较高。值较小的结点优先级较高。在算法实现时通常用最小堆来实现最小优先队列，在算法实现时通常用最小堆来实现最小优先队列，用最小堆的用最小堆的Deletemin运算抽取堆中下一个结点成为运算抽取堆中下一个结点成为当前扩展结点，表达最小费用优先的原那么。当前扩展结点，表达最小费用优先的原那么。 用优先队列式分支限界法解

8、详细问题时，应根据详用优先队列式分支限界法解详细问题时，应根据详细问题的特点确定选用最大优先队列或最小优先队细问题的特点确定选用最大优先队列或最小优先队列来表示解空间的活结点表。列来表示解空间的活结点表。.ABCDEFGHIJKLMNO10例如，思索例如，思索n=3时时0-l背包问题如背包问题如下：下： w=16，15，15， P= 45，25，25, C=30。.ABCDEFGHIJKLMNO10例如，思索例如，思索n=3时时0-l背包问题如背包问题如下：下： w=16，15，15， P= 45，25，25, C=30。.用队列式分支限界法解此问题时，算法从根结点用队列式分支限界法解此问题时

9、，算法从根结点A开场。开场。初始时活结点队列为空，结点初始时活结点队列为空，结点A是当前扩展结点。结是当前扩展结点。结点点A的的2个儿子结点个儿子结点B和和C均为可行结点，故将这均为可行结点，故将这2个个儿子结点按从左到右的顺序参与活结点队列，并且儿子结点按从左到右的顺序参与活结点队列，并且舍弃当前扩展结点舍弃当前扩展结点A。依先进先出原那么，下一个扩。依先进先出原那么，下一个扩展结点是活结点队列的队首结点展结点是活结点队列的队首结点B。扩展结点。扩展结点B得到得到其儿子结点其儿子结点D和和E。由于。由于D是不可行结点，故被舍去。是不可行结点，故被舍去。E是可行结点，被参与活结点队列。接下来，

10、是可行结点，被参与活结点队列。接下来，C成为成为当前扩展结点，它的当前扩展结点，它的2个儿子结点个儿子结点F和和G均为可行结均为可行结点，因此被参与到活结点队列中。扩展下一个结点点，因此被参与到活结点队列中。扩展下一个结点E得到结点得到结点J和和K。J是不可行结点，因此被舍去。是不可行结点，因此被舍去。K是是可行的叶结点，表示所求问题的一个可行解，其价可行的叶结点，表示所求问题的一个可行解，其价值为值为45。.当前活结点队列的队首结点当前活结点队列的队首结点F成为下一个扩展结点。它成为下一个扩展结点。它的的2个儿子结点个儿子结点L和和M均为叶结点。均为叶结点。L表示获得价值为表示获得价值为50

11、的可行解；的可行解；M表示获得价值为表示获得价值为25的可行解。的可行解。G是最是最后的一个扩展结点，其儿子结点后的一个扩展结点，其儿子结点N和和O均为可行叶结均为可行叶结点。最后，活结点队列已空，算法终止。算法搜索点。最后，活结点队列已空，算法终止。算法搜索得到最优值为得到最优值为50。.优先队列式分支限界法从根结点优先队列式分支限界法从根结点A开场搜索解空间树。开场搜索解空间树。用一个极大堆表示活结点表的优先队列。初始时堆用一个极大堆表示活结点表的优先队列。初始时堆为空，扩展结点为空，扩展结点A得到它的得到它的2个儿子结点个儿子结点B和和C。这。这2个结点均为可行结点，因此被参与到堆中，结

12、点个结点均为可行结点，因此被参与到堆中，结点A被被舍弃。结点舍弃。结点B获得的当前价值是获得的当前价值是45，而结点，而结点C的当前的当前价值为价值为0。由于结点。由于结点B的价值大于结点的价值大于结点C的价值，所的价值，所以结点以结点B是堆中最大元素，从而成为下一个扩展结点是堆中最大元素，从而成为下一个扩展结点扩展结点扩展结点B得到结点得到结点D和和E。D不是可行结点，因此不是可行结点，因此被舍去。被舍去。E是可行结点被参与到堆中。是可行结点被参与到堆中。E的价值为的价值为45，成为当前堆中最大元素，从而成为下一个扩展结点。成为当前堆中最大元素，从而成为下一个扩展结点。扩展结点扩展结点E得到

13、得到2个叶结点个叶结点J和和 K。J是不可行结点，是不可行结点，被舍弃。被舍弃。K是可行叶结点，表示所求问题的一个可行是可行叶结点，表示所求问题的一个可行解，其价值为解，其价值为 45。.此时，堆中仅剩下一个活结点此时，堆中仅剩下一个活结点C，它成为当前扩展结点。，它成为当前扩展结点。它的它的2个儿子结点个儿子结点F和和G均为可行结点，因此被插入均为可行结点，因此被插入到当前堆中。结点到当前堆中。结点F的价值为的价值为25，是堆中最大元素，是堆中最大元素，成为下一个扩展结点。结点成为下一个扩展结点。结点F的的2个儿子结点个儿子结点L和和M均均为叶结点。叶结点为叶结点。叶结点L相应于价值为相应于

14、价值为50的可行解。叶结的可行解。叶结点点M相应于价值为相应于价值为25的可行解。叶结点的可行解。叶结点L所相应的解所相应的解成为当前最优解。最后，结点成为当前最优解。最后，结点G成为扩展结点，其儿成为扩展结点，其儿子结点子结点N和和O均为叶结点，它们的价值分别为均为叶结点，它们的价值分别为25和和0。接下来，存储活结点的堆已空，算法终止。算法搜接下来，存储活结点的堆已空，算法终止。算法搜索得到最优值为索得到最优值为 50。相应的最优解是从根结点。相应的最优解是从根结点 A到到结点结点L的途径的途径0，1，1。.在寻求问题的最优解时，与讨论回溯法时类似，可以在寻求问题的最优解时，与讨论回溯法时

15、类似，可以用剪枝函数加速搜索。该函数给出每一个可行结点用剪枝函数加速搜索。该函数给出每一个可行结点相应的子树能够获得的最大价值的上界。假设这个相应的子树能够获得的最大价值的上界。假设这个上界不会比当前最优值更大，那么阐明相应的子树上界不会比当前最优值更大，那么阐明相应的子树中不含问题的最优解，因此可以剪去。另一方面，中不含问题的最优解，因此可以剪去。另一方面，也可以将上界函数确定的每个结点的上界值作为优也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点。这先级，以该优先级的非增序抽取当前扩展结点。这种战略有时可以更迅速地找到最优解。种战略有时可以更迅速地找到最

16、优解。.1234206305410ABCDEFGHIJKLMNOPQ1234344342232432. 游览售货员问题游览售货员问题 队列式分支限界法：队列式分支限界法： A B, A B,B C, D,EB C, D,EC, D,E F,GC, D,E F,GD, E, F,G H,ID, E, F,G H,IE, F, G, H,I J,KE, F, G, H,I J,KF, G, H, I, J,K L(59) F, G, H, I, J,K L(59) 1,2,3,41,2,3,4G, H, I, J,K M(66)G, H, I, J,K M(66)H, I, J,K N(25) 1

17、, 3, 2, H, I, J,K N(25) 1, 3, 2, 44I, J,K 1-3-4(I, J,K 1-3-4(限界掉限界掉) ) /I(26)/I(26)J,K (J,K (限界掉限界掉) /P(25) /P(25)K (K (限界掉限界掉) /Q(59) /Q(59) 例例 游览售货员问题游览售货员问题1234206305410ABCDEFGHIJKLMNOPQ1234344342322423. 游览售货员问题游览售货员问题 优先队列式分支限界法：优先队列式分支限界法：A BB C, D ,E= C(30), D(6),E(4)E, D, C J,K= D(6),C(30),J(

18、14),K(24)D, J,K,C H,I =J(14),K(24), C(30),H(11),I(26)H,J,K,I,C N = N(25) 1, 3, 2, 4J, K,I,C P(25)限界掉限界掉K,I,C Q(59)限界掉限界掉I,C I(26),C(30)限界掉限界掉1234206305410ABCDEFGHIJKLMNOPQ1234344342322423.解此问题的队列式分支限界法以陈列树中结点解此问题的队列式分支限界法以陈列树中结点B作为初作为初始扩展结点。此时，活结点队列为空。由于从图始扩展结点。此时，活结点队列为空。由于从图G的的顶点顶点1到顶点到顶点2，3和和4均有边

19、相连，所以结点均有边相连，所以结点B的儿子的儿子结点结点C，D，E均为可行结点，它们被参与到活结点均为可行结点，它们被参与到活结点队列中，并舍去当前扩展结点队列中，并舍去当前扩展结点B。当前活结点队列中。当前活结点队列中的队首结点的队首结点C成为下一个扩展结点。由于图成为下一个扩展结点。由于图G的顶点的顶点2到顶点到顶点3和和4有边相连，故结点有边相连，故结点C的的2个儿子结点个儿子结点F和和G均为可行结点，从而被参与到活结点队列中。接下均为可行结点，从而被参与到活结点队列中。接下来，结点来，结点D和结点和结点E相继成为扩展结点而被扩展。此相继成为扩展结点而被扩展。此时，活结点队列中的结点依次

20、为时，活结点队列中的结点依次为F，G，H，I，J，K。.结点结点F成为下一个扩展结点，其儿子结点成为下一个扩展结点，其儿子结点L是叶结点。是叶结点。此时找到了一条游览售货员回路，其费用为此时找到了一条游览售货员回路，其费用为59。从。从下一个扩展结点下一个扩展结点G得到叶结点得到叶结点M，它相应的游览售货，它相应的游览售货员回路的费用为员回路的费用为66。结点。结点H依次成为扩展结点，得依次成为扩展结点，得到结点到结点N相应的游览售货员回路，其费用为相应的游览售货员回路，其费用为25，这，这是当前最好的一条回路。下一个扩展结点是结点是当前最好的一条回路。下一个扩展结点是结点I，由于从根结点到叶

21、结点由于从根结点到叶结点I的费用的费用26已超越了当前最优已超越了当前最优值，故没有必要扩展结点值，故没有必要扩展结点I，以结点，以结点I为根的子树被为根的子树被剪去。最后，结点剪去。最后，结点J和和K被依次扩展，活结点队列成被依次扩展，活结点队列成为空，算法终止。算法搜索得到最优值为为空，算法终止。算法搜索得到最优值为25，相应，相应的最忧解是从根结点到结点的最忧解是从根结点到结点N的途径的途径1，3，2，4，1。.解同一问题的优先队列式分支限界法用一极小堆来存储活结点解同一问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点的当前费用。算法还是从陈列树的结点表。其优先级是结点

22、的当前费用。算法还是从陈列树的结点B和空优先队列开场。结点和空优先队列开场。结点B被扩展后，它的被扩展后，它的3个儿子结点个儿子结点C，D和和E被依次插入堆中。此时，由于被依次插入堆中。此时，由于E是堆中具有最小当前费是堆中具有最小当前费用用4的结点，所以处于堆顶的位置，它自然成为下一个扩的结点，所以处于堆顶的位置，它自然成为下一个扩展结点。结点展结点。结点E被扩展后，其儿子结点被扩展后，其儿子结点J和和K被插入当前堆中，被插入当前堆中，它们的费用分别为它们的费用分别为14和和24。此时，堆顶元素是结点。此时，堆顶元素是结点D，它成为，它成为下一个扩展结点。它的下一个扩展结点。它的2个儿子结点

23、个儿子结点H和和I被插入堆中。此时被插入堆中。此时堆中含有结点堆中含有结点C，H，I，J，K。在这些结点中，结点。在这些结点中，结点H具有具有最小费用，从而它成为下一个扩展结点。扩展结点最小费用，从而它成为下一个扩展结点。扩展结点H后得到后得到一条游览售货员回路一条游览售货员回路l，3，2，4，1，相应的费用为，相应的费用为25。接下来，结点接下来，结点J成为扩展结点，由此得到另一条费用为成为扩展结点，由此得到另一条费用为25的回的回路门，路门，4，2，3，1。以后的。以后的2个扩展结点是结点个扩展结点是结点K和和I。由结。由结点点K得到的可行解费用高于当前最优解，结点得到的可行解费用高于当前

24、最优解，结点I本身的费用已本身的费用已高于当前最优解，从而它们都不能得到更好的解。最后，优高于当前最优解，从而它们都不能得到更好的解。最后，优先队列为空，算法终止。先队列为空，算法终止。.与与0-1背包问题的例子类似，可以用一个限界函数在搜背包问题的例子类似，可以用一个限界函数在搜索过程中裁剪子树，以减少产生的活结点。此时剪索过程中裁剪子树，以减少产生的活结点。此时剪枝函数是当前结点扩展后得到的最小费用的下界。枝函数是当前结点扩展后得到的最小费用的下界。假设在当前扩展结点处，这个下界不比当前最优值假设在当前扩展结点处，这个下界不比当前最优值更小，那么剪去以该结点为根的子树。另一方面，更小，那么剪去以该结点为根的子树。另一方面，也可以把每个结点的下界作为优先级，依非减序从也可以把每个结点的下界作为优先级，依非减序从活结点优先队列中抽取下一个扩展结点。活结点优先队列中抽取下一个扩展结点。 .nixcxwxwiniiiniii1,1 ,0max111. while (true) / 检查左孩子结点检查左孩子结点 if (Ew + wi 0; j - - ) /构造当前最优解构造当前最优解