《《分枝-限界法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《分枝-限界法》PPT课件.ppt（34页珍藏版）》请在三一办公上搜索。
1、第七章 分枝-限界法,2,一般方法,分枝-限界法是在生成当前E-结点全部儿子之后，再生成其他活结点的儿子，并且使用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。根据对状态空间树中结点检索次序的不同，可将分枝-限界的设计策略分为：FIFO检索，活结点采用一张先进先出表LIFO检索，活结点采用一张先进后出表,3,例7.1：4-皇后问题,4,本例考察用一个FIFO分支-限界算法检索4-皇后问题的状态空间树的基本过程。起初，只有一个活结点，即结点1。这表示没有皇后被放在棋盘上。扩展这个结点，生成它的儿子结点2,18,34和50。这些结点分别表示皇后1在第1行的1,2,3,4列情况下的棋盘
2、。现在仅有的活结点是2,18,34和50。如果按这样的次序生成这些结点，则下一个E-结点就是结点2。扩展结点2，生成结点3,8和13。利用限界函数，结点3立即被杀死，将结点8和13加到活结点队列。,5,结点18变成下一个E-结点，生成结点19,24和29，限界函数杀死结点19和24，结点29被加到活结点队列。下一个E-结点是34。图中显示了由FIFO分枝-限界检索生成图6.2中的那棵树的一部分。由限界函数杀死的那些结点的下方有一个B字。结点内的数与图6.2所示的结点内的数对应。结点外的数给出了用FIFO分枝-限界法生成结点的次序。在到达答案结点31时，仅剩下活结点38和54。比较图6.6和图7
3、.1可以看出，对于这个问题回溯法占优势。,6,7.1.1 LC-检索,问题：在LIFO和FIFO分枝-限界法中，对下一个E-结点的选择规则相当死板，在某种意义上是盲目的。方法：对活结点使用一个“有智力”排序函数 c(.)来选取下一个E-结点往往可以加快到达一答案结点的速度。对任意结点X，可用两种标准来量度：在生成一个答案结点之前，子树X需要生成的结点数在子树X中离X最近的那个答案结点到X的路径长度,7,使用后一种度量，图7.1中树的根结点付出的代价是4。结点（18和34），（29和35）以及（30和38）的代价分别是3,2和1。所有在2,3和4级上剩余结点的代价应分别大于3,2和1。以这些代价
4、作为选择下一个E-结点的依据，则E-结点依次为1,18,29和30。得以生成的其它结点仅是2,34,50,19,24,32和31。易于看出，如果使用度量1，则对于每一种分枝-限界算法，总是生成最小数目的结点。,8,如果使用度量2，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。以后用C(.)表示“有智力的”排序函数，有称为结点的成本函数。其定义如下：如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本；如果X不是答案结点且子树X不包含任何答案结点，则C(X)=；否则C(X)等于子树X中具有最下成本的答案结点的成本。但要指出的是：要得到结点成本函数C(.)所用的计算工
5、作量与解原问题具有相同的复杂度，所以要得到精确的成本函数一般是不现实的。,9,解决方法：考虑在算法中检测活结点的次序通常可以根据能大致估计结点成的函数g(.)来排出。设g(X)是由X到达一个答案结点所需做的附加工作的估计函数。但是单纯使用函数g(.)并不合适，它会导致算法偏向于作纵深检查。假设结点X是当前的E-结点且它的儿子为Y，由于通常要求g(Y)g(X)，因此，活结点表中其它结点的成本估计值均大于g(Y)，于是Y将在X之后变成E-结点；然后Y的儿子中有一个变成E-结点；接着Y的一个孙子变成E-结点等等，直到子树X全部检索完毕才可能生成那些除X子树以外的子树结点。,10,如果g(X)就是C(
6、X)，这种纵深检索正是所希望的，因为这样可以用最下成本到达离根最近的答案结点，其它子树的结点无需生成。但是g(X)仅是精确成本的估计值，因此偏向于纵深检查可能导致不能很快找到更接近根的答案结点。例如，对于结点W和Z完全可能有这样一种情况，g(W)g(Z)且Z比W更接近答案结点。此时若使用g(.)给结点排序，必然导致对W子树作纵深检查，结果显然是不理想的。,11,解决方法：不仅考虑结点X到一个答案结点的估计成本值，还应考虑由根结点到结点X的成本h(X)。用c(.)来表示新的成本估计函数，使得：c(X)=f(h(X)+g(X)用f(.)不等于0可以减少算法作偏向于纵深检查的可能性，它可以使算法在结
7、点W和Z之间优先检索更靠近答案结点但又离根较近的结点Z。用成本估计函数c(X)=f(h(X)+g(X)选择下一个E-结点的检索策略总是选取c(.)值最小的活结点作为下一个E-结点。因此这种检索策略称之为最小成本检索，简称LC-检索。,12,例：15-谜问题,a,b,c,问题描述：在一个分成16格的方形棋盘上，放有15块编了号码的牌（见下图）。对这些牌给定一种初始排列如图7.2(a)，要求通过一系列的合法移动将这一初始排列转换成图7.2(b)所示的那样的目标排列。,图7.2 15-谜的排列图,13,例：15-谜问题,图7.2(a)所示的初始排列有四种可能的移动，可以将编号为2,3,5或6的任何一
8、块牌移到空格。在作了这次移动之后，可作其他的移动。每移动一次，就产生一种新的排列。这些排列称为这个谜问题的状态。初始排列和目标排列叫做初始状态和目标状态。若由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达。一种初始状态的状态空间由所有可从初始状态到达的状态构成。,14,例：15-谜问题,可以看出棋盘上这些牌有16！种不同的排列，所以这个问题的状态空间是相当庞大的。有必要在具体求解问题之前判定目标状态是否在这个初始状态的状态空间中。对此有一个非常简单的判定方法：我们先给棋盘的方格位置编上116的号码。位置i 是在图7.2(b)所示的目标排列中放i 号牌的方格位置，位置16是空格
9、的位置。假设POSITION(i)是编号为i的那块牌在初始状态下的位置号，1 i 16；POSITION(16)表示空格的位置。,15,对于任意一种状态，设LESS(i)是使牌j 小于牌i，且使POSITION(j)POSITION(i)的数目。例如，对于图7.2(a)所示的状态，有LESS(1)=0，LESS(4)=1和LESS(12)=6。在初始状态下，如果空格在图7.2的阴影位置中的某一格处，则令X=1；否则X=0。于是有定理7.1：当且仅当LESS(i)+X（1 i16)是偶数时，图7.2(b)所示的目标状态可由此初始状态到达。可以用定理7.1来判定目标状态是否在初始状态的状态空间中。
10、若在，就可以着手确定导致目标状态的一系列移动。,16,为了实现这一检索，可以将此状态空间构造成一棵树。在这棵树中，每一个结点的儿子表示由状态X通过一次合法的移动可到达的状态。不难看出，移动牌与移动空格实质上是等效的，而且在作实际移动时，因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。,例：15-谜问题,17,例：15-谜问题,按照FIFO检索方法不管开始格局如何，总是采取由根开始的那条最左路径，因而检索是呆板而盲目的。我们所期望的是：有一个具有一定“智能”的检索方法。这就需给状态空间树的每个结点X赋予一定的成本值c(X)，可将由根出发到最近目标结点路径上的每个结点X赋予这条路径长
11、度作为他们的成本值。切合实际的做法是：给出一个便于计算成本估计值的函数c(X)=f(X)+g(X)，其中f(X)是由根到结点X的路径长度,18,例：15-谜问题,g(X)是以X为根的子树中由X到目标状态的一条最短路径长度的估计值。因此，g(X)至少应是能把状态X转换成目标状态所需的最小移动数。一种可能的选择是：g(X)=不在其目标位置的非空白牌数目使用c(X)图7.3(a)的LC-检索将结点1作为E-结点的开始。结点1在生成它的儿子结点2,3,4和5之后死去。变成E-结点的下一个结点是具有最小c(X)的活结点。,19,例：15-谜问题,c(2)=1+4，c(3)=1+4，c(4)=1+2，c(
12、5)=1+4，所以结点4成为E-结点。生成结点4的儿子结点，此时的活结点是2,3,5,10,11,12。c(10)=2+1，c(11)=2+3，c(12)=2+3，具有最小c值的活结点10成为下一个E-结点。接着生成结点22和23，结点23被判定是目标结点，此次检索结束。,20,分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。,21,分支限界法的基本思想,在这些儿
13、子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。,22,LC-检索的抽象化控制,设T是一棵状态空间树，C(.)是T中结点的成本函数。如果，C(X)是其根为X的子树中任一答案结点的最小成本，则C(T)是T中最小成本答案结点的成本。由于函数C(.)不容易实现，所以使用一个对C(.)估值的启发性函数C(.)来代替。这个启发函数应易于计算并具有如下性质：如果X是一个答案结点或者是一个叶结点，则C(X)=C(X)。,23,算法7.1 LC-检
14、索,Line procedure LC(T,c)if T是答案结点 then 输出T;return end ifET/E-结点/将活结点表初始化为空loopfor E 的每个儿子X doif X是答案结点 then 输出从X到T的那条路径return;end ifcall ADD(X)/X是新的活结点/PARENT(X)E repeatif 不在有活结点 then print(no answer node)stop;end ifcall LEAST(E)repeatEnd LC,24,LC-检索的特性,LC是否一定能找到具有最小成本的答案结点呢？考虑下图所示的状态空间树，方形叶子结点是答案结点
15、。每个结点有两个数，上面的是C的值，下面的是C的值。,25,LC-检索的特性,定理7.2 在有限状态空间树T中，对于每一个结点X，令c(X)是c(X)的估计值且具有以下性质：对于每一个结点Y、Z，当且仅当c(Y)c(Z)时有c(Y)c(Z)。那么在使c()作为c()的估计值时，算法LC到达一个最小的成本答案结点且终止。如果对于每一个结点X有c(X)c(X)且对于答案结点X有c(X)=c(X)，只要对LC稍作修改就可得到一个在达到某个最小成本答案结点时终止的检索算法LC1。,26,算法7.2 找最小成本答案结点的LC-检索,Line procedure LC1(T,c)ET置活结点表为空loop
16、if E是答案结点 then 输出从E到T的路径 return end iffor E的每一个儿子X docall ADD(X);PARENT(X)Erepeatif 不再有活结点 then print(No answer node)stopend ifcall LEAST(E)repeatEnd LC1,27,分枝-限界算法,检索状态空间树的各种分枝-限界方法都是在生成当前E-结点的所有儿子之后再将另一个结点变成E-结点。假定每一个答案结点X有一个与其相联系的C(X)，并且假定会找到最小成本的答案结点。使用一个使得 C(X)C(X)的成本估计函数 C(.)来给出可由任一结点X得出的解的下界。
17、采用下界函数使算法具有一定的智能，减少了盲目性。另外还可以通过设置最小成本的上界使算法进一步加速。,28,分枝-限界算法,如果U是最小成本解的上界，则具有 C(X)U的所有活结点X可以被杀死，这是因为由X可以到达的所有答案结点有U C(X)C(X)。在已经到达一个具有成本U的答案结点的情况下，那些有U C(X)的所有活结点都可以被杀死。U的初始值可以用某种启发性方法得到，也可以置为，每当找到一个新的答案结点就可以修改U的值。,29,实例：带限期的作业排序问题,假定有n个作业和一台处理机，每一个作业i 与一个三元组(pi,di,ti)相联系，它要求ti个单位处理时间，如果在期限di内没处理完则要
18、招致的罚款pi。问题的目标是从这n个作业中选取一个子集合J，要求在J中的作业都能在相应的期限内完成且使不在J中的作业招致的罚款总额最小。,30,N=4;(p1,d1,t1)=(5,1,1);(p2,d2,t2)=(10,3,2);(p3,d3,t3)=(6,2,1);(p4,d4,t4)=(3,1,1);,图7.7 大小可变的元组表示对应的状态空间树,31,图7.8 大小固定的元组表示对应的状态空间树,32,实例：带限期的作业排序问题,图7.7中可将成本函数C(.)定义为，对于圆形结点X，C(X)是根为X的子树中结点的最小罚款；对于方形结点，C(X)=。设SX是在结点X对J所选择的作业的子集。
19、如果m=maxi|i 属于SX，则C(X)等于作业数i 小于m的所有罚款累加和。C(1)=0；C(2)=0；C(3)=5；C(4)=15；C(5)=21；,33,实例：带限期的作业排序问题,作业排序问题的一个FIFO分枝-限界算法开始时可以将最小成本答案结点的成本上界定义为。假定使用图7.7大小可变的元组表示，开始时结点1作为E-结点，于是依次生成结点2,3,4和5。由于u(2)=19,u(3)=14,u(4)=18,u(5)=21,因此在生成结点3时，就将上界U修改为14。因为C(4)和C(5)大于U，所以结点4和5被杀死。,34,实例：带限期的作业排序问题,结点2成为下一个E-结点，生成它的儿子6,7,8。u(6)=9，因此U修改为9；C(7)=10U，所以结点7被杀死；结点8是不可行结点，也被杀死。结点3成为E-结点，生成其儿子结点9和10。u(9)=8，因此U变成8；C(10)=11U，所以10被杀死。结点9只有一个儿子且不可行，因此结点9是最小成本答案结点，其成本值为8。,
