计算机算法设计与分析 第九章分枝-限界法

9.1一般方法9.1.1LC-检索9.1.215谜问题9.1.3LC-检索的抽象化控制9.1.4LC-检索的特性9.1.5分枝-限界算法第九章分枝-限界法1分枝-限界法:

是在生成当前E-结点全部儿子之后,再生成其他活结点的儿子,并且使用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法根据对状态空间树中结点检索次序的不同，可将分枝-限界的设计策略分为两种:FIFO检索(FirstInFirstOut)

活结点表采用先进先出表(即队列)LIFO检索(LastInFirstOut)

活结点表采用后进先出表(即栈)9.1一般方法2例:4-皇后问题:用FIFO检索生成解空间树的过程

起初只有一个活结点,即结点1,这表示没有皇后被放在棋盘上。1

扩展结点1,生成儿子结点2,18,34和50。这些结点分别表示皇后1在第1行的1,2,3,4列情况下的棋盘。3813234现在活结点是2,18,34和50下一个E-结点是结点2,扩展结点2,生成结点3,8和13。利用限界函数,结点3立即被杀死,将结点8和13加到活结点队列21834503421kill3192429134124354045

结点18变成E-结点,生成结点19,24和29,限界函数杀死结点19和24,结点29被加到活结点队列中。123515661killkill3813234kill121834503421killkillkill

结点34变成E-结点,生成结点35,40和45,限界函数杀死结点40和45,结点35被加到活结点队列中。

结点50变成E-结点,生成结点51,56和61,限界函数杀死结点61,结点51和56被加到活结点队列中。411942161432323031383642192429134killkill8132343kill121834503421124354045killkill123515661kill545232595731killkillkillkillkillkillkillkill153313392552kill5631x4=318x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill19x2=124x2=3killkill29x2=430x3=1回溯法生成的解空间树对于4-皇后问题,比较回溯法和分枝-限界法的解空间树,很明显回溯法占优势79.1.1LC-检索分枝-限界法中存在的问题:对下一个E-结点的选择规则相当死板,这种选择对于有可能快速检索到一个答案的结点没有给出任何的优先权。改进方法:对活结点使用一个“有智力”排序函数c(.)来选取下一个E-结点,这样通常可以更快地到达一个答案结点。对可能导致答案的活结点赋以优先权,需要增加额外的计算工作(即需要付出相应的代价)对任一结点X,要付出的代价可使用两种标准来度量:在生成一个答案结点之前,子树X需要生成的结点数在子树X中离X最近的那个答案结点到X的路径长度8使用第2种度量,图中树的根结点的代价是4;结点18和34的代价是3;结点29和35的代价是2;结点30和38的代价是1。在2,3和4级上的其他结点的代价应分别大于3,2和1以这些代价作为选择下一个E-结点的依据,则E-结点依次为1,18,29和3011942161432323031383642192429134killkill8132343kill121834503421124354045killkill123515661kill545232595731killkillkillkillkillkillkillkill153313kill39答案答案2255kill9结论:使用度量1,对于每一种分枝-限界算法,总是生成最小数目的结点。使用度量2,要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。“有智力的”排序函数C(.)又称为结点成本函数C(.)函数定义如下:

如果X是答案结点,则C(X)是由状态空间树的根结点到X的成本(如路径长度);如果X不是答案结点且子树X不包含任何答案结点,则C(X)=∞;否则C(X)等于子树X中具有最小成本的答案结点的成本。注:要得到结点成本函数C(.)所用的计算工作量与解原问题具有相同的复杂度,所以要得到精确的成本函数一般是不现实的10在算法中检测活结点的次序通常可以根据能大致估计结点成本的函数g(.)来排列。^为了不使算法过分偏向作纵深检查,需要改进成本估计函数单纯使用函数g(.)并不合适,它会导致算法偏向于作纵深检查。【越向下越可能接近答案节点】^如果g(X)就是C(X),这种纵深检索正是所希望的,因为这样可以用最小成本到达离根最近的答案结点,其它子树的结点无需生成。^但是g(X)仅是精确成本的估计值,因此偏向于纵深检查可能导致不能很快找到更接近根的答案结点。^11改进的成本估计函数:不仅考虑X到一个答案结点的估计成本值,还考虑了由根结点到X的成本(路径长)h(X)用c(.)来表示新的成本估计函数^c(X)=f(h(X))+g(X)^^要求函数f(.)是一个非降函数,用f(.)不等于0可以减少算法作偏向于纵深检查的可能性^用成本估计函数c(X)选择下一个E-结点的检索策略总是选取c(.)值最小的活结点作为下一个E-结点。^这种检索策略称为最小成本检索,简称LC-检索。伴之有限界函数的LC-检索称为LC分枝-限界检索129.1.215谜问题134152512761114891013123456789101112131415图a图b问题描述:在一个分成16格的方形棋盘上,放有15块编了号码的牌。对这些牌给定一种初始排列,如图a,要求通过一系列的合法移动将初始排列转换成图b所示那样的目标排列。13134152512761114891013图a所示的初始排列有四种可能的移动,可以将编号为2,3,5或6的任何一块牌移到空格。在作了这次移动之后,可作其他的移动。每移动一次，就产生一种新的排列。这些排列称为这个15谜问题的状态。初始排列和目标排列叫做初始状态和目标状态。若由初始状态到某状态存在一系列合法的移动,则称该状态可由初始状态到达。一种初始状态的状态空间由所有可从初始状态到达的状态构成。图a14在求解问题之前应判定目标状态是否在这个初始状态的状态空间中。一个简单的判定方法:先给棋盘的方格位置编上1~16的号码。位置i是在图b所示的目标排列中放i号牌的方格位置,位置16是空格的位置。假设POSITION(i)是编号为i的那块牌在初始状态下的位置号,1≤i<16;POSITION(16)表示空格的位置。12345678910111213141516134152512761114891013图a图bPOSITION(1)=1POSITION(2)=5POSITION(3)=2POSITION(16)=615对于任意一种状态,设LESS(i)是使牌j<牌i,且使POSITION(j)>POSITION(i)的数目。134152512761114891013图a图c在初始状态下,如果空格在图c的阴影位置中的某一格处,则令X=1;否则X=0。例如:对于图a所示的状态LESS(1)=0,LESS(2)=0,LESS(3)=1LESS(4)=1,LESS(12)=6定理9.1:

当且仅当∑LESS(i)+X(1≤i≤16)是偶数时,图b所示的目标状态可由此初始状态到达。例如图a,算出∑LESS(i)+X=37+0=37,因此由图a的初始状态不能到达图b的目标状态16定理9.1用来判定目标状态是否在初始状态的状态空间中。若在就可以开始确定导致目标状态的一系列移动。为实现这一检索,可以将此状态空间构造成一棵树。在这棵树中,每一个结点的儿子表示由状态X通过一次合法的移动可到达的状态。移动牌与移动空格实质上是等效的,而且在作实际移动时移动空格更为直观,因此将父状态到子状态的一次转换看成是空格的一次合法移动。1715-谜问题一个实例的状态空间树该树已做部分修剪,如果结点P的儿子中有和P的父亲的状态相同的就将该枝剪去123456891071113141512124563891071113141512123456891071113141512123456789101113141512123456891071113141512123456789101113141512123456789101511131412123456789101113141512123456791011813141512123456789101112131415………上右下左右下左上下目标状态按照FIFO检索方法不管开始格局如何,总是采取由根开始的那条最左路径因而检索是呆板而盲目的1819我们期望的是有一种能按不同具体实例作出不同处理的有一定“智能”的检索方法。这就需给状态空间树的每个结点X赋予一定的成本c(X),如果具体实例有解,则将由根出发到最近目标结点路径上的每个结点赋予这条路径长度作为它们的成本。在上例的状态空间树中,由根结点1到目标结点23的路径长度为3,因此有c(1)=c(4)=c(10)=c(23)=3,而树中、的其他结点的成本均赋为∞,如果能做到这一点,宽度优先检索将很有效,但这是一种很不实际的策略,因为想要得到那样的成本函数c(.)是不可能的20实际的做法是:给出一个便于计算成本估计值的函数c(X)=f(X)+g(X),

其中f(X)是由根到结点X的路径长度,g(X)是以X为根的子树中由X到目标状态的一条最短路径长度的估计值。^^^g(X)是能把状态X转换成目标状态所需的最小移动数。一种选择是:g(X)=不在其目标位置的非空白牌数目^^为达到目标状态所需要的移动数可能大于g(x),对于右图,只有7号牌不在目标位置上,所以有g(x)=1,很明显为到达目标状态所需的移动次数比g(x)大得多,因此c(x)是c(x)的下界^^^^12345689101112131415721使用c(X))的LC-检索将结点1作为E-结点的开始,结点1在生成它的儿子结点2,3,4和5之后死去。变成E-结点的下一个结点是具有最小c(X)的活结点。^^c(2)=1+4=5,c(3)=1+4=5c(4)=1+2=3,c(5)=1+4=5^^^^结点4成为E-结点,结点4生成儿子结点,此时的活结点是2,3,5,10,11,121215141311710986543211上右下左1215141311710983654212121514131171098654321312151413111098765432141215141311710986543215右下左121514131110987654321101214131115109876543211112151413111098765432112c(10)=2+1=3c(11)=2+3=5c(12)=2+3=5^^^具有最小值的活结点10成为下一个E-结点22活结点10生成结点22和23,结点23被判定是目标结点,此次检索结束目标状态上12151413811109765432122下151413121110987654321231215141311710986543211上右下左1215141311710983654212121514131171098654321312151413111098765432141215141311710986543215右下左12151413111098765432110121413111510987654321111215141311109876543211223分枝-限界法的基本思想分枝-限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在搜索问题的解空间树时,在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入到活结点表中。此后从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程,这个过程一直持续到找到所求的解或活结点表为空时为止。249.1.3

LC-检索的抽象化控制设T是一棵状态空间树,c(.)是T中结点的成本函数。如果c(X)是其根为X的子树中任一答案结点的最小成本,则c(T)是T中最小成本答案结点的成本。^如前所述,函数c(.)不容易实现,所以使用一个对c(.)估值的启发性函数c(.)来代替这个启发函数应易于计算并具有如下性质:如果X是一个答案结点或者是一个叶结点,则c(X)=c(X)^25procedureLC(T,c)ifT是答案结点then{输出T;return;}E=T;活结点表初始化为空;loop{forE结点的每个儿子结点Xdo {ifX是答案结点then{输出从X到T的那条路径;return;}

callADD(X);

PARENT(X)=E;}if不再有活结点then{print(“noanswernode”);stop;}

callLEAST(E);}endLC^//使结点T成为E-结点//LC用函数c(.)去寻找一个答案结点//将新的活结点X添加到活结点表中//用来找一个具有最小成本值的活结点,并从活结点表中删除该结点,然后将此结点放在变量X中返回//用信息段PARENT保存X的父结点E26LC算法正确性证明有限状态空间树算法过程同LC检索定义相吻合无限状态空间树若不加限定，则可能陷入无限深度中如果X的级数大于Y的级数达到一定程度，则ĉ(X)>ĉ(Y),阻止进一步下陷没有答案的无限状态空间树，LC不停机可以规定杀死成本大于一个限界的活节点，保证停机LEAST按队列：FIFO,宽度优先检索LEAST按栈：LIFO,D-检索279.1.4

LC-检索的特性

在许多应用中希望在所有答案结点中找到一个最小成本的结点,LC检索是否一定能找到具有最小成本的答案结点呢？^考虑下图所示的状态空间树,方结点是答案结点。每个结点有两个数,上面的是c的值,下面的是c的值132654710020220201041010∞∞∞∞LC算法先生成根结点的儿子结点2和3,因c(2)=2,所以结点2成为E-结点,它扩展出结点4和5,结点4就是答案结点,其成本为20,但成本最小的答案结点应该是结点7。^28LC算法没能找到最小成本答案结点的原因在于存在这样两个结点X和Y,当c(X)>c(Y)时,c(X)<c(Y)^^定理9.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^^29procedureLC1(T,c)E=T;活结点表初始化为空;loop{ifE是答案结点then{输出从E到T的路径;return;}forE结点的每个儿子结点Xdo {callADD(X);

PARENT(X)=E;}if不再有活结点then{print(“noanswernode”);stop;}

callLEAST(E);}endLC1^找最小成本答案结点的LC-检索将if语句放在for循环的外面先执行,如果满足条件则结束loop循环,即结束算法LC1309.1.5分枝-限界算法

检索状态空间树的各种分枝-限界算法都是在生成当前E-结点的所有儿子结点后,再将另一个结点变为E-结点。之前我们使用一个成本估计函数c(.)来给出可由任一结点X得出的解的下界。采用下界函数使算法具有一定的“智能”,另外还可以通过设置最小成本的上界使算法进一步加速。^如果U是最小成本解的上界,则具有c(X)>U的所有活结点X可以被杀死,因为由X可以到达的所有答案结点有c(X)≥c(X)>U^^U的初始值可用某种启发性方法得到,也可以置为∞,每当找到一个新的答案结点就可以修改U的值。31求解最优化问题的分枝限界法只考虑极小化问题成本函数定义为目标函数【而非达到答案节点的代价】成本函数分三种情况：X为答案，则为目标函数；X为不可行(部分)解，则为；否则为X子树中最小成本节点的成本。

ĉ(X)c(X)32实例:带限期的作业排序问题问题描述:假定有n个作业和一台处理机,每一个作业i与一个三元组(pi,di,ti)相联系,它要求ti个单位处理时间,如果在期限di内作业没处理完则要招致pi的罚款。目标是从这n个作业中选取一个子集合J,要求在J中的作业都能在相应的期限内完成,并且使不在J中的作业招致的罚款总额最小。33实例: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);该实例的解空间由作业指标集{1,2,3,4}的所有可能的子集合组成,使用元组大小可变的表示方法,构造一棵解空间树如下:911710612345x1=1x1=2x1=3x1=4x2=2x2=3x2=4x3=3x2=3x2=4x3=4x3=4x3=4812131415x2=4c=8c=0^c=0^c=0^c=10^c=5^c=5^c=11^c=15^c=15^c=21^树中方形结点代表不可行的子集合,所有的圆形结点都是答案结点结点9代表最优解,并且是仅有的最小成本答案结点J={2,3}罚款值为p1+p4=834成本函数c(.)定义为,对于圆形结点,c(X)是根为X的子树中结点的最小罚款;对于方形结点,c(X)=∞911710612345x1=1x1=2x1=3x1=4x2=2x2=3x2=4x3=3x2=3x2=4x3=4x3=4x3=4812131415x2=4c=8c=0^c=0^c=0^c=10^c=5^c=5^c=11^c=15^c=15^c=21^c(2)=min{9,13}=9c(3)=min{8,11}=8c(4)=15,c(5)=21c(1)=min{9,8,15,21}=8定义下界函数c(.),使c(X)≤c(X)。设SX是在结点X对J所选择的作业的子集。如果m=max{i|i属于SX},则c(X)=∑pi,(i<m且iSX),即c(X)等于作业i小于m,且作业i不属于SX的所有罚款累加和。^^^^子树X中最小成本答案结点的成本的一个简单上界u(X)定义为:u(X)=∑pi(i

SX)35开始时U=∞,

结点1为E-结点,依次生成结点2,3,4和5作业排序问题的一个FIFO分枝-限界算法开始时可以将最小成本答案结点的成本上界取为U=∞或U=∑pi1≤i≤n因为c(4)和c(5)大于U,所以结点4和5被杀死。^^u(2)=p2+p3+p4=19u(3)=p1+p3+p4=14

u(4)=p1+p2+p4=18u(5)=p1+p2+p3=21在生成结点3时,将上界修改为U=141c=0^2345x1=1x1=2x1=3x1=4c=0^c=5^c=15^c=21^c(1)=0;c(2)=0;c(3)=p1=5;c(4)=p1+p2=15;c(5)=p1+p2+p3=21;^^^^^killkill361c=0^2345x1=1x1=2x1=3x1=4c=0^c=5^c=15^c=21^killkill活节点（2，3）；结点2成为E-结点,生成儿子结点6,7,876x2=2x2=3x2=48c=0^c=10^u(6)=p3+p4=9,u(7)=p2+p4=13,因此U=9;c(6)=0,c(7)=p2=10>U,

结点7被杀死;结点8是不可行结点^^killkillx2=3x2=4c=5^c=11^910活节点(3);结点3成为E-结点,生成儿子结点9和10u(9)=p1+p4=8,u(10)=p1+p3=11,因此U=8;ĉ(9)=p1=5,c(10)=p1+p2=11>U,

所以10被杀死^活节点(6,3);结点6成为E-结点,其儿子结点12和13均不可行活节点表(9);结点9成为E-结点,其儿子结点15,不可行活节点表空。所以结点9是最小成本答案结点（U最小）x3=3x3=41213x3=41537因活结点队列中符合条件的结点是随机分布的,每修改一次U就在队列中找出这些结点并将其杀死是很麻烦的,一种方法是在应杀死的结点要变成E-结点时才将其杀掉。在实现FIFO分枝-限界算法时,每修改一次U,在活结点队列中那些有ĉ(X)>U的结点,或者在U是已找到的一个成本