第七章分枝-限界法.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
3、。比较图6.6和图7.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级上剩余结点的代价
4、应分别大于3,2和1。以这些代价作为选择下一个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中具有最下成本的答案结点的成本。 但要指出的
5、是:要得到结点成本函数C(.)所用的计算工作量与解原问题具有相同的复杂度,所以要得到精确的成本函数一般是不现实的。,9,解决方法:考虑在算法中检测活结点的次序通常可以根据能大致估计结点成的函数g(.)来排出。 设g(X)是由X到达一个答案结点所需做的附加工作的估计函数。 但是单纯使用函数g(.)并不合适,它会导致算法偏向于作纵深检查。 假设结点X是当前的E-结点且它的儿子为Y,由于通常要求g(Y) g(X) ,因此,活结点表中其它结点的成本估计值均大于g(Y) ,于是Y将在X之后变成E-结点; 然后Y的儿子中有一个变成E-结点;接着Y的一个孙子变成E-结点等等,直到子树X全部检索完毕才可能生成
6、那些除X子树以外的子树结点。,10,如果g(X) 就是C(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
7、) 用f(.)不等于0可以减少算法作偏向于纵深检查的可能性,它可以使算法在结点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-谜问题,
8、图7.2(a)所示的初始排列有四种可能的移动,可以将编号为2,3,5或6的任何一块牌移到空格。 在作了这次移动之后,可作其他的移动。每移动一次,就产生一种新的排列。这些排列称为这个谜问题的状态。 初始排列和目标排列叫做初始状态和目标状态。 若由初始状态到某状态存在一系列合法的移动,则称该状态可由初始状态到达。 一种初始状态的状态空间由所有可从初始状态到达的状态构成。,14,例:15-谜问题,可以看出棋盘上这些牌有16!种不同的排列,所以这个问题的状态空间是相当庞大的。 有必要在具体求解问题之前判定目标状态是否在这个初始状态的状态空间中。 对此有一个非常简单的判定方法:我们先给棋盘的方格位置编上
9、116的号码。位置i 是在图7.2(b)所示的目标排列中放i 号牌的方格位置,位置16是空格的位置。 假设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
10、)是偶数时,图7.2(b)所示的目标状态可由此初始状态到达。 可以用定理7.1来判定目标状态是否在初始状态的状态空间中。若在,就可以着手确定导致目标状态的一系列移动。,16,为了实现这一检索,可以将此状态空间构造成一棵树。在这棵树中,每一个结点的儿子表示由状态X通过一次合法的移动可到达的状态。 不难看出,移动牌与移动空格实质上是等效的,而且在作实际移动时,因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。,例:15-谜问题,17,例:15-谜问题,按照FIFO检索方法不管开始格局如何,总是采取由根开始的那条最左路径,因而检索是呆板而盲目的。 我们所期望的是: 有一个具有一定“智能”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七 分枝 限界
链接地址:https://www.31doc.com/p-2094703.html