第七章 分枝-限界法.ppt

第七章第七章 分枝分枝-限界法限界法一般方法一般方法n分枝分枝-限界法是在生成当前限界法是在生成当前E-结点全部结点全部儿子之后，再生成其他活结点的儿子，儿子之后，再生成其他活结点的儿子，并且使用限界函数帮助避免生成不包含并且使用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。答案结点子树的状态空间的检索方法。n根据对状态空间树中结点检索次序的不根据对状态空间树中结点检索次序的不同，可将分枝同，可将分枝-限界的设计策略分为：限界的设计策略分为：FIFO检索，活结点采用一张检索，活结点采用一张先进先出表先进先出表LIFO检索，活结点采用一张检索，活结点采用一张先进后出表先进后出表2例例7.1：4-皇后问题皇后问题39553n本例本例考察用一个考察用一个FIFO分支分支-限界算法检索限界算法检索4-皇后问题的状态空间树的基本过程。皇后问题的状态空间树的基本过程。n起初，只有一个活结点，即结点起初，只有一个活结点，即结点1。这表。这表示没有皇后被放在棋盘上。示没有皇后被放在棋盘上。n扩展这个结点，生成它的儿子结点扩展这个结点，生成它的儿子结点2,18,34和和50。这些结点分别表示皇后。这些结点分别表示皇后1在在第第1行的行的1,2,3,4列情况下的棋盘。列情况下的棋盘。n现在仅有的活结点是现在仅有的活结点是2,18,34和和50。如果。如果按这样的次序生成这些结点，则下一个按这样的次序生成这些结点，则下一个E-结点就是结点结点就是结点2。扩展结点。扩展结点2，生成结点，生成结点3,8和和13。利用限界函数，结点。利用限界函数，结点3立即被杀立即被杀死，将结点死，将结点8和和13加到活结点队列。加到活结点队列。4结点结点18变成下一个变成下一个E-结点，生成结点结点，生成结点19,24和和29，限界函数杀死结点，限界函数杀死结点19和和24，结点，结点29被加到被加到活结点队列。下一个活结点队列。下一个E-结点是结点是34。图中显示了由图中显示了由FIFO分枝分枝-限界检索生成图限界检索生成图6.2中的那棵树的一部分。由限界函数杀死的那些中的那棵树的一部分。由限界函数杀死的那些结点的下方有一个结点的下方有一个B字。结点内的数与图字。结点内的数与图6.2所所示的结点内的数对应。示的结点内的数对应。结点外的数给出了用结点外的数给出了用FIFO分枝分枝-限界法生成限界法生成结点的次序。结点的次序。在到达答案结点在到达答案结点31时，仅剩下活结点时，仅剩下活结点38和和54。比较图比较图6.6和图和图7.1可以看出，对于这个问题可以看出，对于这个问题回回溯法占优势。溯法占优势。57.1.1 LC-检索检索n问题：问题：在在LIFO和和FIFO分枝分枝-限界法中，对下限界法中，对下一个一个E-结点的选择规则相当死板，在某种意结点的选择规则相当死板，在某种意义上是盲目的。义上是盲目的。n方法：方法：对活结点使用一个对活结点使用一个“有智力有智力”排序函排序函数数 c(.)来选取下一个来选取下一个E-结点往往可以加快到结点往往可以加快到达一答案结点的速度。达一答案结点的速度。n对任意结点对任意结点X，可用两种标准来量度：可用两种标准来量度：在生成一个答案结点之前，子树在生成一个答案结点之前，子树X需要生成的结点需要生成的结点数数在子树在子树X中离中离X最近的那个答案结点到最近的那个答案结点到X的路径长的路径长度度6使用后一种度量，图使用后一种度量，图7.1中树的根结点付出中树的根结点付出的代价是的代价是4。结点（。结点（18和和34），（），（29和和35）以及（以及（30和和38）的代价分别是）的代价分别是3,2和和1。所有在所有在2,3和和4级上剩余结点的代价应分别级上剩余结点的代价应分别大于大于3,2和和1。以这些代价作为选择下一个。以这些代价作为选择下一个E-结点的依据，则结点的依据，则E-结点依次为结点依次为1,18,29和和30。得以生成的其它结点仅是得以生成的其它结点仅是2,34,50,19,24,32和和31。易于看出，如果使用度量。易于看出，如果使用度量1，则对于，则对于每一种分枝每一种分枝-限界算法，总是生成最小数目限界算法，总是生成最小数目的结点。的结点。7如果使用度量如果使用度量2，则要成为，则要成为E-结点的结点结点的结点只是由根到最近的那个答案结点路径上的只是由根到最近的那个答案结点路径上的那些结点。那些结点。以后用以后用C(.)表示表示“有智力的有智力的”排序函数，有称排序函数，有称为结点的成本函数。其定义如下：为结点的成本函数。其定义如下：如果如果X是答案结点，则是答案结点，则C(X)是由是由状态空间树的根状态空间树的根结点到结点到X的成本；如果的成本；如果X不是答案结点且子树不是答案结点且子树X不不包含任何答案结点，则包含任何答案结点，则C(X)=；否则否则C(X)等于等于子树子树X中具有最下成本的答案结点的成本。中具有最下成本的答案结点的成本。但要指出的是：要得到结点成本函数但要指出的是：要得到结点成本函数C(.)所用的所用的计算工作量与解原问题具有相同的复杂度，所以计算工作量与解原问题具有相同的复杂度，所以要得到精确的成本函数一般是不现实的。要得到精确的成本函数一般是不现实的。8n解决方法：解决方法：考虑在算法中检测活结点的次序通考虑在算法中检测活结点的次序通常可以根据能大致估计结点成的函数常可以根据能大致估计结点成的函数g(.)来排来排出。出。n设设g(X)是由是由X到达一个答案结点所需做的附加到达一个答案结点所需做的附加工作的估计函数。工作的估计函数。n但是单纯使用函数但是单纯使用函数g(.)并不合适，它会导致算并不合适，它会导致算法偏向于作纵深检查。法偏向于作纵深检查。n假设结点假设结点X是当前的是当前的E-结点且它的儿子为结点且它的儿子为Y，由由于通常要求于通常要求g(Y)g(X)，因此，活结点表因此，活结点表中其它结点的成本估计值均大于中其它结点的成本估计值均大于g(Y)，于是于是Y将在将在X之后变成之后变成E-结点；结点；n然后然后Y的儿子中有一个变成的儿子中有一个变成E-结点；接着结点；接着Y的一的一个孙子变成个孙子变成E-结点等等，直到子树结点等等，直到子树X全部检索全部检索完毕才可能生成那些除完毕才可能生成那些除X子树以外的子树结点。子树以外的子树结点。9n如果如果g(X)就是就是C(X)，这种纵深检索正是所这种纵深检索正是所希望的，因为这样可以用最下成本到达离根最希望的，因为这样可以用最下成本到达离根最近的答案结点，其它子树的结点无需生成。近的答案结点，其它子树的结点无需生成。n但是但是g(X)仅是精确成本的估计值，因此仅是精确成本的估计值，因此偏向于纵深检查可能导致不能很快找到偏向于纵深检查可能导致不能很快找到更接近根的答案结点。更接近根的答案结点。n例如，对于结点例如，对于结点W和和Z完全可能有这样一完全可能有这样一种情况，种情况，g(W)g(Z)且且Z比比W更接更接近答案结点。此时若使用近答案结点。此时若使用g(.)给给结点排结点排序，必然导致对序，必然导致对W子树作纵深检查，结子树作纵深检查，结果显然是不理想的。果显然是不理想的。10n解决方法：解决方法：不仅考虑结点不仅考虑结点X到一个答案结点的到一个答案结点的估计成本值，还应考虑由根结点到结点估计成本值，还应考虑由根结点到结点X的成的成本本h(X)。n用用c(.)来表示新的成本估计函数，使得：来表示新的成本估计函数，使得：c(X)=f(h(X)+g(X)n 用用f(.)不等于不等于0可以减少算法作偏向于纵深检查可以减少算法作偏向于纵深检查的可能性，它可以使算法在结点的可能性，它可以使算法在结点W和和Z之间优之间优先检索更靠近答案结点但又离根较近的结点先检索更靠近答案结点但又离根较近的结点Z。n用成本估计函数用成本估计函数c(X)=f(h(X)+g(X)选择下一选择下一个个E-结点的检索策略总是选取结点的检索策略总是选取c(.)值值最小的活最小的活结点作为下一个结点作为下一个E-结点。结点。n因此这种检索策略称之为最小成本检索，简称因此这种检索策略称之为最小成本检索，简称LC-检索。检索。11例：例：15-谜问题谜问题134152512761114891013123456789101112131415abc问题描述：在一个分成问题描述：在一个分成16格的方形棋盘上，放有格的方形棋盘上，放有15块编了号码的牌（见下图）。对这些牌给定一块编了号码的牌（见下图）。对这些牌给定一种初始排列如图种初始排列如图7.2(a)，要求通过一系列的合法移要求通过一系列的合法移动将这一初始排列转换成图动将这一初始排列转换成图7.2(b)所示的那样的目所示的那样的目标排列。标排列。图图7.2 15-谜的排列图谜的排列图12例：例：15-谜问题谜问题 图图7.2(a)所示的初始排列有四种可能的移动，所示的初始排列有四种可能的移动，可以将编号为可以将编号为2,3,5或或6的任何一块牌移到空格。的任何一块牌移到空格。在作了这次移动之后，可作其他的移动。每在作了这次移动之后，可作其他的移动。每移动一次，就产生一种新的排列。这些排列称移动一次，就产生一种新的排列。这些排列称为这个谜问题的状态。为这个谜问题的状态。初始排列和目标排列叫做初始状态和目标状初始排列和目标排列叫做初始状态和目标状态。态。若由初始状态到某状态存在一系列合法的移若由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达。动，则称该状态可由初始状态到达。一种初始状态的状态空间由所有可从初始状一种初始状态的状态空间由所有可从初始状态到达的状态构成。态到达的状态构成。13例：例：15-谜问题谜问题 可以看出棋盘上这些牌有可以看出棋盘上这些牌有16！种不同的排列，！种不同的排列，所以这个问题的状态空间是相当庞大的。所以这个问题的状态空间是相当庞大的。有必要在具体求解问题之前判定目标状态是有必要在具体求解问题之前判定目标状态是否在这个初始状态的状态空间中。否在这个初始状态的状态空间中。对此有一个非常简单的判定方法：我们先给对此有一个非常简单的判定方法：我们先给棋盘的方格位置编上棋盘的方格位置编上116的号码。位置的号码。位置i 是在是在图图7.2(b)所示的目标排列中放所示的目标排列中放i 号牌的方格位置，号牌的方格位置，位置位置16是空格的位置。是空格的位置。假设假设POSITION(i)是编号为是编号为i的那块牌在初始的那块牌在初始状态下的位置号，状态下的位置号，1 i 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 i i16)16)是是偶数时，图偶数时，图7.2(7.2(b)b)所示的目标状态所示的目标状态可由此初始状态到达。可由此初始状态到达。可以用定理可以用定理7.17.1来判定目标状态是否在初始状来判定目标状态是否在初始状态的状态空间中。若在，就可以着手确定导致态的状态空间中。若在，就可以着手确定导致目标状态的一系列移动。目标状态的一系列移动。15 为了实现这一检索，可以将此状态空间构造为了实现这一检索，可以将此状态空间构造成一棵树。在这棵树中，每一个结点的儿子表成一棵树。在这棵树中，每一个结点的儿子表示由状态示由状态X通过一次合法的移动可到达的状态。通过一次合法的移动可到达的状态。不难看出，移动牌与移动空格实质上是等效的，不难看出，移动牌与移动空格实质上是等效的，而且在作实际移动时，因此以后都将父状态到而且在作实际移动时，因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。子状态的一次转换看成是空格的一次合法移动。例：例：15-谜问题谜问题16例：例：15-谜问题谜问题n按照按照FIFO检索方法不管开始格局如何，总是采检索方法不管开始格局如何，总是采取由根开始的那条最左路径，因而检索是呆板而取由根开始的那条最左路径，因而检索是呆板而盲目的。盲目的。n我们所期望的是：我们所期望的是：有一个具有一定有一个具有一定“智能智能”的检索方法。这就需给的检索方法。这就需给状态空间树的每个结点状态空间树的每个结点X赋予一定的成本值赋予一定的成本值c(X)，可将可将由根出发到最近目标结点路径上的每个结由根出发到最近目标结点路径上的每个结点点X赋予这条路径长度作为他们的成本值赋予这条路径长度作为他们的成本值。n切合实际的做法是：切合实际的做法是：n给出一个便于计算成本估计值的函数给出一个便于计算成本估计值的函数c(X)=f(X)+g(X)，其中其中f(X)是由根到结点是由根到结点X的路径长度的路径长度17例：例：15-谜问题谜问题ng(X)是以是以X为根的子树中由为根的子树中由X到目标状态的一到目标状态的一条最短路径长度的估计值。条最短路径长度的估计值。n因此，因此，g(X)至少应是能把状态至少应是能把状态X转换成目标状转换成目标状态所需的最小移动数。态所需的最小移动数。n一种可能的选择是：一种可能的选择是：g(X)=g(X)=不在其目标位置的非空白牌数目不在其目标位置的非空白牌数目不在其目标位置的非空白牌数目不在其目标位置的非空白牌数目n使用使用c(X)图图7.3(a)的的LC-检索将结点检索将结点1作为作为E-结点的开始。结点结点的开始。结点1在生成它的儿子结点在生成它的儿子结点2,3,4和和5之后死去。变成之后死去。变成 E-结点的下一个结结点的下一个结点是具有最小点是具有最小c(X)的的活结点。活结点。18例：例：15-谜问题谜问题nc(2)=1+4，c(3)=1+4，c(4)=1+2，c(5)=1+4，所以结点所以结点4成为成为E-结点。结点。n生成结点生成结点4的儿子结点，此时的活结点的儿子结点，此时的活结点是是2,3,5,10,11,12。nc(10)=2+1，c(11)=2+3，c(12)=2+3，具有最小具有最小c值的值的活结点活结点10成为下一个成为下一个E-结点。结点。n接着生成结点接着生成结点22和和23，结点，结点23被判定被判定是目标结点，此次检索结束。是目标结点，此次检索结束。19分支限界法的基本思想分支限界法的基本思想n分支限界法常以广度优先或以最小耗费分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解（最大效益）优先的方式搜索问题的解空间树。空间树。n在搜索问题的解空间树时，分支限界法在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其点一旦成为扩展结点，就一次性产生其所有儿子结点。所有儿子结点。20分支限界法的基本思想分支限界法的基本思想n在这些儿子结点中，那些导致不可行解在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。此后，余儿子结点被加入到活结点表中。此后，从活结点表中取下一结点成为当前扩展从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点过程一直持续到找到所求的解或活结点表为空时为止。表为空时为止。21LC-检索的抽象化控制检索的抽象化控制n设设T是一棵状态空间树，是一棵状态空间树，C(.)是是T中结点中结点的成本函数。如果，的成本函数。如果，C(X)是其根为是其根为X的的子树中任一答案结点的最小成本，则子树中任一答案结点的最小成本，则C(T)是是T中最小成本答案结点的成本。中最小成本答案结点的成本。n由于函数由于函数C(.)不容易实现，所以使用一个不容易实现，所以使用一个对对C(.)估值的启发性函数估值的启发性函数C(.)来代替。来代替。n这个启发函数应易于计算并具有如下性这个启发函数应易于计算并具有如下性质：如果质：如果X是一个答案结点或者是一个是一个答案结点或者是一个叶结点，则叶结点，则C(X)=C(X)。22算法算法7.1 LC-检索检索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将将一个活结点加一个活结点加入到队列中入到队列中将将一个活结点从一个活结点从队列中删除队列中删除保存结点保存结点X的父的父结点结点E23LC-检索的特性检索的特性nLC是否一定能找到具有最小成本的答案结点呢是否一定能找到具有最小成本的答案结点呢？n考虑下图所示的状态空间树，方形叶子结点是答考虑下图所示的状态空间树，方形叶子结点是答案结点。每个结点有两个数，上面的是案结点。每个结点有两个数，上面的是C的值，的值，下面的是下面的是C的值。的值。10020220201041010 24LC-检索的特性检索的特性n定理定理7.2 在有限状态空间树在有限状态空间树T中，对于每一个中，对于每一个结点结点X，令令c(X)是是c(X)的估计值且具有以下性的估计值且具有以下性质：对于每一个结点质：对于每一个结点Y、Z，当且仅当当且仅当c(Y)c(Z)时有时有c(Y)U的的所有活结点所有活结点X可以被杀死，这是因为由可以被杀死，这是因为由X可以可以到达的所有答案结点有到达的所有答案结点有UU，所以结点所以结点7被杀死；结点被杀死；结点8是不可行结点，是不可行结点，也被杀死。也被杀死。n结点结点3成为成为E-结点，生成其儿子结点结点，生成其儿子结点9和和10。u(9)=8u(9)=8，因此因此U U变成变成8 8；C(10)=11U，所以所以10被杀死。被杀死。n结点结点9只有一个儿子且不可行，因此结点只有一个儿子且不可行，因此结点9是最小成本答案结点，其成本值为是最小成本答案结点，其成本值为8。34