分枝-限界法-Read.PPTVIP

第7章 分枝-限界法 分支限界法思想的由来 分支限界法类似于回溯法,也是一种在解空间树T上有哪些信誉好的足球投注网站问题解的算法。但分支限界法类和回溯法求解目标不同。回溯法求解目标一般是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数达到极大或极小的解，即在某种意义下的最优解。 分支限界法思想的由来 由于求解目标不同，导致分支限界法和回溯法在解空间树上的有哪些信誉好的足球投注网站方式也不相同。回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树T，而分支限界法则以广度优先或最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 分支限界法的有哪些信誉好的足球投注网站策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。 为了有效地选择下一个扩展结点，以加速有哪些信誉好的足球投注网站进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使有哪些信誉好的足球投注网站朝着解空间树上最优解的分支推进，以尽快地找出一个最优解。这种方法就统称为分支限界法。 分支限界法是在生成当前E结点的全部儿子之后再生成其它活结点的儿子且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。 在生成结点22之后,显然这个结点只要走一步就可到达答案结点,但死板的FIFO规则却要求先扩展已生成的所有其它活结点。 但如果给使结点22得到比其它活结点更高的优先权，则结点22就会在结点11之后成为扩展结点，接着就会生成答案结点。因此，剩下的活结点就不需再成为活结点。 LC检索与宽度优先和D检索的关系 LC检索算法与宽度优先和D检索算法基本相同。如果活结点表作为一个队列来实现，用LEAST(X)和ADD(X)表示从队列中删去和加入元素,则LC算法转换成FIFO,但如果活结点表用一个堆栈来实现,同样用LEAST(X)和ADD(X)表示从堆栈中删去和加入元素,则LC就转换成LIFO检索。 不同之处：活结点的表的构造不同，即得到下一个E结点所使用的规则不同。FIFO和LIFO都进表的顺序，而LC是选成本估计值最小的活结点作为E结点。 7.2 0/1背包问题 为了应用分枝-限界方法来求解0/1背包问题,需要将原来的极大化问题变为极小化问题。 修改后的问题描述： 极小化： 约束条件： 成本函数C和成本估计函数C^以及上界函数的定义 1. C(X)定义: 对于可行的叶结点: 不可行叶结点:C(X)=∞ 非叶结点: 2.成本估计函数C^和U的定义 设X是j级上的一个结点, * 两种特殊的分支限界法 7.1.1 FIFO检索和LIFO检索 检索这两种方法都是对当前扩展节点E的所有儿子进行检测，满足约束条件的儿子，放入活结点表中，该扩展节点E完成其使命，成为死节点，再从活节点表中取出其它节点，作为新的扩展节点。活节点表中的活节点按先进先出取出的方式，称为FIFO检索(First in First Out)，活节点表中的活节点按后进先出取出的方式，称为LIFO检索(Last in First Out)。 FIFO检索的活结点表是一个队列， LIFO检索的活结点表是一个堆栈。 1 2 3 4 L=(2,3,4 ) FIFO取2作为下一个扩展节点 以4-皇后后问题的状态空间树的FIFO有哪些信誉好的足球投注网站为例： 最初扩展结点为1，产生儿子2，3，4，5，放入活节点表。 3 1 2 3 4 5 6 8 20 11 22 31 12 25 15 16 27 1 2 3 4 2 3 3 1 1 2 1 4 3 3 L=(2,3,4,5) L=(3,4,5,7，8) L=( ) 7 9 10 13 14 17 4 1 4 2 4 2 18 19 2 4 21 3 23 24 2 26 2 28 29 1 3 30 3 L=(7,8,11,12,15,16) 利用限界函数,结点3立即被杀死. 6.1.2 最小代价有哪些信誉好的足球投注网站( LC检索) 在LIFO和FIFO分枝—限界法中，对下一个E-结点的选择规则相当死板，而且在某种意义上是“盲目的”。这种选择规则对于有可能快速检索到一个答案结点的结点没有给出任何优先权。对活结点使用一个“有智力的”排序函数c(·)来选取下一个E-结点往往可以加快到达一答案结点的检索速度。 代价函数c(X)：要给可能导致答案结点的活结点赋以优先次序，必然要附加若干计算工作，即要付出代价。对于任一结点X，要付出的代价可以使用以下标准来度量： 在子树X中离X最近的那个答案结点到X的路径长度。 r x a ………. 用c(·)表示“有智力的”排序函数，又称为结点成本函数。它的定义如下：如果X是答案结点，则c(X)是由状态空间树的根结点到X的