算法第九章详解.ppt

《算法第九章详解.ppt》由会员分享，可在线阅读，更多相关《算法第九章详解.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第九章第九章分支分支-限界法限界法29.1 一般方法一般方法9.1.1 LC-检索检索9.1.2 15-谜谜9.1.3 LC-检索的抽象化控制检索的抽象化控制9.1.4 LC-检索的特性检索的特性9.1.5 分支分支-限界算法限界算法39.1 一般方法一般方法p分支分支-限界法类似于回溯法，也是一种在问题的解空限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。但二者间树上搜索问题解的算法。但二者搜索方式搜索方式不同。不同。p以四皇后问题的解空间树为例以四皇后问题的解空间树为例1456743341011129424214151617323220212223434325262728

2、411430313233311338133419242913421834503424-皇后问题的解空间树皇后问题的解空间树x1=1x2=2结点编号结点编号按深度优先次序按深度优先次序5回溯法回溯法使用限界函数的使用限界函数的深度优先深度优先结点生成方法结点生成方法当前的当前的E-结点一旦生成一个新儿子结点一旦生成一个新儿子C，C就变成新就变成新的的E-结点。结点。6kill31x4=318x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=216x3=3kill19x2=124x2=3killkill29x2=430 x3=1

3、用回溯法解决四皇后问题用回溯法解决四皇后问题回溯法一共处理了回溯法一共处理了16个结点，到达一个答案结点（结点个结点，到达一个答案结点（结点31）7分支分支-限界法限界法p分支分支-限界法限界法生成当前生成当前E-结点全部儿子结点全部儿子之后，才从活结点表中选一个之后，才从活结点表中选一个活结点作为新的活结点作为新的E-结点，结点，使用使用限界函数限界函数帮助帮助避免生成不包含答案结点子树避免生成不包含答案结点子树的状态的状态空间空间89.1 一般方法一般方法p根据对状态空间树中根据对状态空间树中结点检索次序结点检索次序的不同，分支的不同，分支-限限界可以采用不同的活结点表：界可以采用不同的活

4、结点表：nFIFO检索，活结点采用一张先进先出表（队列）检索，活结点采用一张先进先出表（队列）nLIFO检索，活结点采用一张后进先出表（堆栈）检索，活结点采用一张后进先出表（堆栈）9例例9.1 FIFO分枝限界法检索四皇后问题的状态分枝限界法检索四皇后问题的状态空间树空间树p4-皇后问题的状态空间树皇后问题的状态空间树(图图8.2-P195)192429910111138137863445051832213540451213145156611516172 183450 3 8 13192429354045515661活结点表活结点表1019242991011113813786153014162

5、1201991118344505183223540451213145156611516173 8 13192429354045515661B9 111416BB30322322303238362425BB3638275254265254595728295759BBB15B313131B B答案节点答案节点分枝限界法一共处理了分枝限界法一共处理了31个节点。个节点。回溯法一共处理了回溯法一共处理了16个节点个节点(P198 图图8.6)。119.1.1 LC-检索检索(least cost)pLC-检索的问题检索的问题：只有这两种活结点表吗？只有这两种活结点表吗？n 队列实现的活结点表队列实现的

6、活结点表FIFOn 堆栈实现的活结点表堆栈实现的活结点表LIFOn 对下一个对下一个E-节点的选择规则相当节点的选择规则相当死板死板，在某种意，在某种意义上是义上是盲目盲目的。对于可能快速检索到答案结点的的。对于可能快速检索到答案结点的结点结点没有给出任何优先权没有给出任何优先权。12515661151617B19242991011113813786153014162120199111834450518322354045121314BB3032232238362425BB2752542659572829BBBB3131B B答案节点答案节点在上例中，尽管在生成结点在上例中，尽管在生成结点30后

7、，该结点只要走一步就后，该结点只要走一步就可到达答案结点可到达答案结点31；但死板的但死板的FIFO规则却要求先扩展已生成的其他活结点规则却要求先扩展已生成的其他活结点能否根据某个优先级，使得结点能否根据某个优先级，使得结点31比其他活结点具有更高的优先级，比其他活结点具有更高的优先级，从而被快速得到？从而被快速得到？139.1.1 LC-检索检索(least cost)p解决解决：对活结点使用一个对活结点使用一个“有智力的有智力的”排序函数排序函数c(.)来选取下来选取下一个一个E-结点，往往可以加快到达一答案结点的速度。结点，往往可以加快到达一答案结点的速度。14p要对活结点计算优先次序，

8、必然要附加计算工作，即付出代价。要对活结点计算优先次序，必然要附加计算工作，即付出代价。对于任意结点对于任意结点X，要付出的代价可以用两种标准来度量：，要付出的代价可以用两种标准来度量：1n生成一个答案结点之前，子树生成一个答案结点之前，子树X需需要要生成的结点数生成的结点数；n在子树在子树X中，离中，离X最近的那个答案最近的那个答案结点结点到到X的路径长度的路径长度。43213450182192429303231总是生成最小数目的结点。总是生成最小数目的结点。那条路径上的结点会成为那条路径上的结点会成为E-结点。结点。答案结点答案结点结点结点1代价是代价是4;18.3;292;30115结点

9、成本函数结点成本函数cp“有智力的有智力的”排序函数排序函数c也称为结点成本函数也称为结点成本函数n如果如果X是答案结点是答案结点，则，则c(X)是由状态空间树的根是由状态空间树的根节点到节点到X的成本的成本(即所用的代价，可以是级数、计即所用的代价，可以是级数、计算复杂度等算复杂度等)；n如果如果X不是答案结点且子树不是答案结点且子树X不包含任何答案结不包含任何答案结点点，则，则c(X)=；n如果如果X不是答案结点，但子树不是答案结点，但子树X中包含答案结点中包含答案结点，则则c(X)等于子树等于子树X中具有最小成本的答案结点的中具有最小成本的答案结点的成本成本。16函数函数c的计算工作量的

10、计算工作量结点成本函数结点成本函数c的计算工作量往往的计算工作量往往与原问题具有相同的复杂度。与原问题具有相同的复杂度。计算一个节点计算一个节点X的成本通常需要检索的成本通常需要检索以以X为根结点的整个子树才能确定。为根结点的整个子树才能确定。要得到精确的成本函要得到精确的成本函数并不现实，一般大数并不现实，一般大致估计结点成本。致估计结点成本。17估估计计函数函数(X)p设设(X)是由是由X到达一个答案到达一个答案结点所需做的附加工点所需做的附加工作的作的估估计函数函数。n假假设子子树X中有中有答案答案结结点点；n设设X的儿子的儿子结结点是点是Y，应应有有(Y)(X)，因，因为为Y到达答案到

11、达答案结结点的成本肯定比点的成本肯定比X到达答案到达答案结结点点的成本小；的成本小；18用用(X)给给活活结结点排序是否合适？点排序是否合适？p若若X是当前是当前E-结点点n说明在活明在活结点表中，点表中，(X)最小，即最小，即(X)(其他活其他活结结点点)p生成生成X的儿子的儿子结结点点Y，并放入活，并放入活结结点表点表p则则有有Y成成为为当前当前E-结点点n因因为(Y)(X)(其他活其他活结结点点)，故故Y在在X之后成之后成为为新的新的E-结点点。p该过程直到子程直到子树X全部全部检检索完索完毕毕才可能生成才可能生成子子树树X以外的以外的结结点。点。19(X)分析分析p只用只用(X)为结为

12、结点排序是否适合点排序是否适合?n不适合不适合,只考只考虑虑未来的可能的代价未来的可能的代价,导致算法偏向于纵深导致算法偏向于纵深方向检索。方向检索。理想理想:)如果如果(X)=c(X)总成立总成立，那，那么问题可以用最小成本到么问题可以用最小成本到达离根最近的答案结点。达离根最近的答案结点。乐观的冒进乐观的冒进现实现实:(但通常情况下，但通常情况下，(X)只是只是精精确成本的一个估计值确成本的一个估计值，因此，因此偏于纵深检查可能会丢失掉偏于纵深检查可能会丢失掉更靠近根的答案结点。导致更靠近根的答案结点。导致结果不理想。结果不理想。(X)是对未来可能发生的成本估计是对未来可能发生的成本估计2

13、0结点成本估计函数结点成本估计函数p考虑结点考虑结点X到一个答案结点的估计成本到一个答案结点的估计成本(X);p考虑根结点到结点考虑根结点到结点X的成本的成本h(X);(X)=f(h(X)+(X)X(X)h(X)算法对活结点表进行检索时，优先选择算法对活结点表进行检索时，优先选择更靠近答案结更靠近答案结点且又离根结点较近点且又离根结点较近的结点。的结点。函数函数f是一个非降函数。不妨将是一个非降函数。不妨将f的作用理的作用理解为调整解为调整h和和在成本估计函数在成本估计函数中的影响中的影响比例。比例。21LC-检检索索pLC-检索检索(Least Cost search)：选取成本估：选取成本

14、估计函数计函数的的值最小的活结点作为下一个值最小的活结点作为下一个E-结点。结点。p伴有限界函数的伴有限界函数的LC-检索称为检索称为LC分枝分枝-限界检索限界检索。pf(h(X)=结点结点X的级数，的级数，(X)=0时，则变为时，则变为BFS检索检索。（队列实现的广度优先检索）。（队列实现的广度优先检索）pf(h(X)=0，且每当，且每当Y是是X的一个儿子时总有的一个儿子时总有(X)(Y)时，则变为时，则变为D-检索检索。（堆栈实现）。（堆栈实现）(X)=f(h(X)+(X)BFS和和D检索是检索是LC-检索的特殊情况检索的特殊情况221712345678910 11121314 15161

15、8202324 25192122262728 2930 31x1=1x1=0 x2=1x3=1101010 x2=0 x3=0 x3=1x3=0 x2=1x2=0 x3=1x3=0 x3=1x3=01010101010子集和数问题的解空间树子集和数问题的解空间树2注注:结点按结点按D-检索方式编号检索方式编号239.1.2 15-谜问题谜问题134152512761114891013123456789101112131415 a 初始排列初始排列p 问题描述问题描述在一个分成在一个分成16格的方形棋盘上，放有格的方形棋盘上，放有15块编了号码的块编了号码的牌。对这些牌给定一种初始排列，要求通过

16、一系列的牌。对这些牌给定一种初始排列，要求通过一系列的合法移动合法移动将这一初始排列转换成目标排列。将这一初始排列转换成目标排列。b 目标排列目标排列邻接空格的牌邻接空格的牌移到空格移到空格249.1.2 15-谜问题谜问题 每移动一次，就产生一种新的排列。这些排列称为这每移动一次，就产生一种新的排列。这些排列称为这个个谜问题的状态谜问题的状态。初始排列称为初始排列称为初始状态初始状态，目标排列称为目标排列称为目标状态目标状态。若由初始状态到某状态存在一系列合法的移动，则称若由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达该状态可由初始状态到达。一个初始状态的一个初始状态的状

17、态空间状态空间，由所有由所有可从初始状态到达可从初始状态到达的状态的状态构成。构成。1341525127611148910131341525127611 148910 13相当庞大，有必要在具相当庞大，有必要在具体求解之前，判断目标体求解之前，判断目标状态是否在这个初始状状态是否在这个初始状态的状态空间中态的状态空间中259.1.2 15-谜问题谜问题12345678910 11 1213 14 15 在具体求解问题之前判定：在具体求解问题之前判定：目标状态是否在目标状态是否在这个初始状态的状态空间中这个初始状态的状态空间中。方法：方法：对棋盘的对棋盘的方格位置方格位置编上编上116的号码。的

18、号码。位置位置i 是在右图的目标排列中放是在右图的目标排列中放i 号牌的方格位号牌的方格位置，位置置，位置16是空格的位置。是空格的位置。假设假设POSITION(i)是编号为是编号为i的那块牌在初始状的那块牌在初始状态下的位置号，态下的位置号，1 i 16；POSITION(16)表示空格的位置。表示空格的位置。对于任意一种状态，对于任意一种状态，LESS(i)是使是使牌牌j 牌牌i，且且POSITION(j)POSITION(i)的的j的数目的数目。初始状态下，如果空格在右图的初始状态下，如果空格在右图的阴影位置阴影位置中的中的某一格处，则令某一格处，则令X=1；否则；否则X=0。1341

19、525127611 148910 13LESS(1)=0LESS(4)=1LESS(12)=626定理定理9.1：当且仅当：当且仅当 LESS(i)+X是偶数是偶数时，图时，图b b所示所示的目标状态可由此初始状态到达。的目标状态可由此初始状态到达。15-谜的状态空间树谜的状态空间树 结点：棋盘的状态结点：棋盘的状态 每个结点的儿子：状态每个结点的儿子：状态X通过通过一次一次合法的移动可到合法的移动可到达的状态达的状态 移动牌与移动空格等效移动牌与移动空格等效：“上上”、“右右”、“下下”、“左左”的顺序的顺序9.1.2 15-谜问题谜问题1 i 16判定目标状态是判定目标状态是否在初始状态的

20、否在初始状态的状态空间中状态空间中27求解方法求解方法p法法1：宽度优先：宽度优先FIFO检索检索p法法2：深度优先检索：深度优先检索p法法3：LC检索检索2812345689 10 71113 14 15 1212456389 10 71113 14 15 1212345689 10 71113 14 15 12123456789 101113 14 15 1212345689 10 71113 14 15 1212456389 10 71113 14 15 1212456389 10 71113 14 15 1212356849 10 71113 14 15 121234568119 10

21、 713 14 15 12123456789 10 1113 14 15 12123456789 10 15 1113 141212345678910 1113 14 15 1212345 10 68971113 14 15 1212345689 10 71113 14 15 1213452689 10 71113 14 15 1212485639 10 71113 14 15 1216245389 10 71113 14 15 1212456389 10 71113 14 15 1212356849 10 71113 14 15 121234568119 107 1213 14 151234

22、568119 10713 14 15 1212345679 10 11813 14 15 12123456789 10 11 1213 14 15上上右右下下左左右右左左上上下下右右下下左左上上下下左左下下下下左左左左下下左左上上下下宽度优先宽度优先FIFO检索检索1234567891011121314151617181920212223离根结点最近离根结点最近的答案结点。的答案结点。上、右、下、左上、右、下、左29求解方法求解方法p法法1：宽度优先：宽度优先FIFO检索检索n不管开局如何（不关心问题的具体实例），总不管开局如何（不关心问题的具体实例），总是按千篇一律的顺序移动。是按千篇一律的

23、顺序移动。p法法2：深度优先检索：深度优先检索p法法3：LC检索检索30深度优先深度优先12345689 10 71113 14 15 12112456389 10 71113 14 15 122上上12456389 10 71113 14 15 12右右312485639 10 71113 14 15 1241281156491031213 147151285641191031213 147151285641191031213 1471512485611910 3 1213 14 7 151248563119101213 14 7 1512485631191071213 1415124856

24、311910 713 14 15 12下下下下512485631191071213 14 15下下6左左7上、右、下、左上、右、下、左8上上9上上上上10右右11下下1231求解方法求解方法p法法1：宽度优先：宽度优先FIFO检索检索n能找到离根最近的答案结点能找到离根最近的答案结点，但不管开局如何但不管开局如何(不关心问题的具体实例不关心问题的具体实例)，总是按千篇一律的，总是按千篇一律的顺序移动。顺序移动。p法法2：深度优先检索：深度优先检索n不管开局如何（不关心问题的具体实例），总不管开局如何（不关心问题的具体实例），总是采取由根开始的最左路径，呆板而盲目。搜是采取由根开始的最左路径，呆

25、板而盲目。搜索过程中索过程中有可能远离目标有可能远离目标。p法法3：LC检索检索32LC检索检索p给状态空间树的每个节点给状态空间树的每个节点X赋予一定的成本赋予一定的成本c(X)。n将根结点到最近目标结点路径上的每个结点的成本设置为将根结点到最近目标结点路径上的每个结点的成本设置为这条路径这条路径的长度的长度。n其余结点成本赋值为其余结点成本赋值为。p在宽度优先搜索方式下，首先将根结点作为在宽度优先搜索方式下，首先将根结点作为E-结点，结点，将成将成本为本为的子结点统统杀掉，只保留与根结点成本相同的子的子结点统统杀掉，只保留与根结点成本相同的子结点结点，并使其成为下一个，并使其成为下一个E-

26、结点。该策略重复进行，直到结点。该策略重复进行，直到找到目标结点为止。找到目标结点为止。P221 图图9.3(a)c(1)=c(4)=c(10)=c(23)=3理想状态理想状态下下很不实际，基本不可很不实际，基本不可能得到这样的函数能得到这样的函数c。33p便于计算成本估计值的函数：便于计算成本估计值的函数：nf(X)是由根到结点是由根到结点X路径的长度；路径的长度；n(X)是以是以X为根的子树中由为根的子树中由X到目标状态的一条最短路径到目标状态的一条最短路径长度的估计值。长度的估计值。(X)=f(X)+(X)定义：定义：(X)=不在其目标位置的非空白棋牌数目不在其目标位置的非空白棋牌数目1

27、234568910 11 1213 14 157(X)是是c(X)的下界的下界最小移最小移动数动数(X)=1121514131171098654321121514131171098365421121514131171098654321121514131110987654321121514131171098654321上上右右下下左左12345(2)=1+43,7,11,12(3)=1+47,8,11,12(4)=1+211,12(5)=1+46,7,11,123412345689 10 71113 14 15 12123456789 101113 14 15 12下下14123456789 1

28、0 1113 14 15 12123456789 10 15 1113 141212345678910 1113 14 15 12右右下下左左101112(10)=2+1(11)=2+3(12)=2+312345679 10 11813 14 15 12123456789 10 11 1213 14 15上上下下2223当前实例下，当前实例下，LC-检索几检索几乎和使用精确函数乎和使用精确函数c一样一样有效，有效，LC-检索的选择性检索的选择性比很多检索方法强很多。比很多检索方法强很多。3545-4645-46学时学时36结点成本函数结点成本函数cp“有智力的有智力的”排序函数排序函数c也称为

29、结点成本函数也称为结点成本函数n如果如果X是答案结点是答案结点，则，则c(X)是由状态空间树的根是由状态空间树的根节点到节点到X的成本的成本(即所用的代价，可以是级数、计即所用的代价，可以是级数、计算复杂度等算复杂度等)；n如果如果X不是答案结点且子树不是答案结点且子树X不包含任何答案结不包含任何答案结点点，则，则c(X)=；n如果如果X不是答案结点，但子树不是答案结点，但子树X中包含答案结点中包含答案结点，则则c(X)等于子树等于子树X中具有最小成本的答案结点的中具有最小成本的答案结点的成本成本。回顾回顾C(X)是结点是结点X的客观存在的真实成本，但是很难事先得到的客观存在的真实成本，但是很

30、难事先得到379.1.3 LC-检索的抽象化控制检索的抽象化控制pT是一棵状态空间树是一棵状态空间树pc是是T中结点的成本函数中结点的成本函数pc(X)是根为是根为X的子树中答案结点的最小成本。的子树中答案结点的最小成本。pc(T)是是T中最小成本答案结点的成本。中最小成本答案结点的成本。找到这样一个易于找到这样一个易于计算的计算的c是很难的。是很难的。p用启发函数用启发函数来代替来代替n易于计算易于计算n如果如果X是一个答案结点或者是一个叶结点，则是一个答案结点或者是一个叶结点，则c(X)=(X)38抽象化控制思想抽象化控制思想p如果根结点如果根结点T是答案结点，输出该节点，是答案结点，输出

31、该节点，操作结束；操作结束；否则，令否则，令T是当前的是当前的E-结点，此时结点，此时活结点表活结点表为空。为空。p判断判断E的每个子结点的每个子结点X：如果：如果X是答案结点，输出是答案结点，输出从从X到到T的路径，的路径，操作结束；操作结束；否则，将否则，将X添加到活添加到活结点表中。结点表中。p如果活结点表中不再有结点，如果活结点表中不再有结点，操作结束；操作结束；否则从否则从中选择一个函数值中选择一个函数值最小的结点作为当前新的最小的结点作为当前新的E-结点，重复步骤结点，重复步骤2。ADD(X)LEAST(X)39算法算法9.1 LC-检索检索Line procedure LC(T,

32、)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将一个活结点加入将一个活结点加入到活结点表中到活结点表中将

33、一个活结点从活结将一个活结点从活结点表中删除点表中删除保存结点保存结点X的的父结点父结点Emin堆堆409.1.3 LC-检索的抽象化控制检索的抽象化控制p算法终止：找到算法终止：找到答案结点答案结点或生成并检索了或生成并检索了整棵整棵 有限有限状态空间树状态空间树p无限无限状态空间树的终止：状态空间树的终止：至少有一个答案结点至少有一个答案结点，且，且对对(.)作出适当选择作出适当选择。p没有答案结点的没有答案结点的无限无限状态空间树，则不会终止状态空间树，则不会终止。p将检索局限在寻找将检索局限在寻找估计成本不大于某个给定的限估计成本不大于某个给定的限界界C的答案结点的答案结点419.1.

34、3 LC-检索的抽象化控制检索的抽象化控制 活结点表用活结点表用队列队列实现实现 FIFO检索检索pLC算法算法 活结点表用活结点表用堆栈堆栈实现实现 LIFO检索检索得到下一个得到下一个E-结点的选结点的选择规则不同择规则不同实际上，实际上，LC算法与状态空间树的宽度优先检索算法算法与状态空间树的宽度优先检索算法以及以及D-检索算法基本相同检索算法基本相同429.1.4 LC-检索的特性检索的特性pLC是否一定能找得到具有最小成本是否一定能找得到具有最小成本c(G)的答案结点的答案结点G呢？呢？10020220201041010答案结点答案结点cEEc(X)c(Y)(X)(Y)如果使每对如果

35、使每对c(X)c(Y)的的X、Y结点都有结点都有(X)(Y)，那么对于，那么对于一棵存在答案结点的有限状态空间树，一棵存在答案结点的有限状态空间树，LC算法是否总会找到算法是否总会找到一个最小成本答案结点？一个最小成本答案结点？最小成本结点最小成本结点43p证明：证明：已知若已知若T有限且存在答案结点，有限且存在答案结点，LC一定能找到一个一定能找到一个答案结点。答案结点。下面证明满足定理下面证明满足定理9.2的条件时，的条件时，LC能找到能找到最小成最小成本答案结点本答案结点。p定理定理9.2 在在有限有限状态空间树状态空间树T中，对于每一个结点中，对于每一个结点X，令，令(X)是是c(X)

36、的估计值且具有以下性质：对的估计值且具有以下性质：对于每一对结点于每一对结点Y、Z，当且仅当当且仅当c(Y)c(Z)时有时有(Y)c(G)。p找到距离找到距离G和和G最近的共同祖先最近的共同祖先R。pR到到G的路径为的路径为R、1、k、G。pR到到G的路径为的路径为R、1、j、G。p若能检索到若能检索到G，则，则R必在某时间成为必在某时间成为E-结点。结点。子结点子结点1和和1成为活结点。成为活结点。kjGG最小成本最小成本答案结点答案结点答案结点答案结点ER1122c(R)=c(1)=c(k)=c(G)c(1)=c(k)=c(G)c(G)(1)(G),(k),(1)在在i(1i k)变成变成

37、E结点并到达结点并到达G之前，之前，1不能变成不能变成E-结点，与结点，与假设矛盾，命题得证。假设矛盾，命题得证。459.1.4 LC-检索的特性检索的特性p定理定理9.2 在有限状态空间树在有限状态空间树T中，对于每一个结点中，对于每一个结点X，令，令(X)是是c(X)的估计值且具有以下性质：对于的估计值且具有以下性质：对于每一对结点每一对结点Y、Z，当且仅当，当且仅当c(Y)c(Z)时有时有(Y)(Z)。那么在使用。那么在使用()作为作为c()的估计值时，算法的估计值时，算法LC到达一个最小的成本答案结点且终止。到达一个最小的成本答案结点且终止。这样的这样的(.)通常得不到通常得不到一般可

38、以找到一个易于计算、且具有如下特性的一般可以找到一个易于计算、且具有如下特性的()，对于每一个结点，对于每一个结点X，有，有(X)C(X)算法算法LC仍然未必仍然未必找到最小答案结点找到最小答案结点4610020220201041010答案结点答案结点cEEc(X)c(Y)(X)U的所有活结点的所有活结点X可以被杀死。可以被杀死。U的初值：启发式方法或的初值：启发式方法或，不断修改。，不断修改。只要只要U的初始值不小于最小成本答案结点的成本，的初始值不小于最小成本答案结点的成本，就不会杀死可以到达最小成本答案结点的活结点就不会杀死可以到达最小成本答案结点的活结点C(X)(X)U519.1.5

39、分枝分枝-限界算法限界算法p最优化问题最优化问题-极小化问题极小化问题p成本函数：代表最优解的答案结点的成本函数：代表最优解的答案结点的c(X)是所有是所有结点中成本最小的结点中成本最小的-目标函数目标函数 可行解的目标函数值可行解的目标函数值 若若X是可行解结点是可行解结点 c(X)=若若X是不可行解结点是不可行解结点 根为根为X的树中的树中最小成本最小成本 若若X是部分解结点是部分解结点 结点结点的成本的成本p状态空间树中每个答案结点都对应一个可行解，成本最状态空间树中每个答案结点都对应一个可行解，成本最小的答案结点对应最优解。小的答案结点对应最优解。p估计函数估计函数(X)c(X)：对对

40、目目标标函数函数进进行估行估计计，而不是估，而不是估计计达到一个答案达到一个答案结结点在点在计计算上的算上的难难易程度。易程度。529.1.5 分枝分枝-限界算法限界算法p带期限的作业排序问题：带期限的作业排序问题：允许作业有不同的处理时间允许作业有不同的处理时间 每个作业每个作业i与一个三元组联系与一个三元组联系(pi,di,ti)目标：目标：n个作业的子集合个作业的子集合J，J中的作业都能中的作业都能在相应的在相应的期限内完成期限内完成，且不在，且不在J中的作业招致的中的作业招致的罚款总额最小罚款总额最小。p例：例：n=4,(p1,d1,t1)=(5,1,1),(p2,d2,t2)=(10

41、,3,2),(p3,d3,t3)=(6,2,1),(p4,d4,t4)=(3,1,1),作业作业i的的处理时间处理时间如果没有在期限如果没有在期限值之前完成，招值之前完成，招致致pi的罚款的罚款53123456791011x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4121314815元组大小可变的状态空间树元组大小可变的状态空间树方形结点是方形结点是不可行结点不可行结点圆形结点圆形结点都是答案都是答案结点结点对于圆形结点对于圆形结点X，C(X)=根为根为X的子树中结点的的子树中结点的最小罚款最小罚款对于方形结点对于方形结点X，

42、C(X)=(p1,d1,t1)=(5,1,1)(p2,d2,t2)=(10,3,2)(p3,d3,t3)=(6,2,1)(p4,d4,t4)=(3,1,1)C(6)=9,C(7)=13,故故C(2)=9542512367141530 3128 29121326 274102321511919x1=1x1=0 x2=1x3=1x4=1010 x2=0 x3=0 x3=1x3=0 x2=1x2=0 x3=1x3=0 x3=1x3=01010101010圆形叶结点圆形叶结点是答案结点是答案结点 22元组大小固定的状态空间树元组大小固定的状态空间树913198111415182124c05010610

43、16551115211555123456791011x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4121314815元组大小可变的状态空间树元组大小可变的状态空间树方形结点是方形结点是不可行结点不可行结点圆形结点圆形结点都是答案都是答案结点结点(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)=0,(2)=0,(3)=5,(4)=15,(5)=21(6)=0,(7)=10,(8)=

44、,(9)=5,(10)=11,(11)=15569.1.5 分枝分枝-限界算法限界算法p设设SX是在结点是在结点X处选择的作业的子集处选择的作业的子集，m=maxi|i SX，(X)=pi u(X)=pi，U=minU(X)i mi SXi SXX对应的子集对应的子集SX的成本值（罚款）的成本值（罚款）初始时，成本上界初始时，成本上界U=或或U=pi1 i n子树子树X中最小成本答案结点的成本的简单上界中最小成本答案结点的成本的简单上界5716x2=27x2=39x2=310 x2=42x1=13x1=24x1=35x1=4x3=312x3=413x2=48x3=415元组大小可变的状态空间树

45、元组大小可变的状态空间树u(2)=p2+p3+p4=19,(2)=0u(3)=p1+p3+p4=14,(3)=5u(4)=p1+p2+p4=18,(4)=15U=19U=14Bu(5)=p1+p2+p3=21,(5)=21Bu(6)=p3+p4=9,(6)=0U=9u(7)=p2+p4=13,(7)=10Bu(9)=p1+p4=8,(9)=5U=8u(10)=p1+p3=11,(10)=11B(p1,d1,t1)=(5,1,1),(p2,d2,t2)=(10,3,2),(p3,d3,t3)=(6,2,1),(p4,d4,t4)=(3,1,1),5847-4847-48学时学时5916x2=27

46、x2=39x2=310 x2=42x1=13x1=24x1=35x1=4x3=312x3=413x2=48x3=415元组大小可变的状态空间树元组大小可变的状态空间树u(2)=p2+p3+p4=19,(2)=0u(3)=p1+p3+p4=14,(3)=5u(4)=p1+p2+p4=18,(4)=15U=19U=14Bu(5)=p1+p2+p3=21,(5)=21Bu(6)=p3+p4=9,(6)=0U=9u(7)=p2+p4=13,(7)=10Bu(9)=p1+p4=8,(9)=5U=8u(10)=p1+p3=11,(10)=11B(p1,d1,t1)=(5,1,1),(p2,d2,t2)=(

47、10,3,2),(p3,d3,t3)=(6,2,1),(p4,d4,t4)=(3,1,1),回顾回顾U如何得到？如何得到？609.1.5 分枝分枝-限界算法限界算法pU修改之后修改之后，对于活结点表中满足，对于活结点表中满足(X)U的的X，可，可以以当当X即将成为即将成为E结点时将其杀掉结点时将其杀掉对于对于(X)=U的结点的结点X是否杀死？是否杀死？p这取决于这取决于U的来源的来源，U可能有两种来源：可能有两种来源：p一个已找到的解的成本值；一个已找到的解的成本值；不是解成本的单不是解成本的单纯上界纯上界p如果如果U的来源是的来源是，那么相当于，那么相当于U本身就是一个本身就是一个解成本（结

48、点解成本（结点Y），对于其他），对于其他(X)=U，因为其真，因为其真实成本实成本C(X)(X)=U，至多，至多X的解成本与结点的解成本与结点Y的的解成本相同，不会比解成本相同，不会比Y更小，更小，所以所以X是没有意义的，是没有意义的，可以杀死可以杀死61p如果如果U的来源是的来源是，即，即U不是一个解成本，而只是不是一个解成本，而只是一个单纯的上界一个单纯的上界p对于其他对于其他(X)=U，其真实成本，其真实成本C(X)(X)=U，意味，意味着着存在着存在着C(X)=U的可能性的可能性p假设这种情况出现：结点假设这种情况出现：结点X是一个解，且其真实成是一个解，且其真实成本本C(X)=U，那

49、么结点，那么结点X就不能被杀死就不能被杀死p因为在此之前虽然上界是因为在此之前虽然上界是U，但是没有结点的成本，但是没有结点的成本可以达到可以达到U，而，而X的成本是的成本是可能可能达到达到U的，它的，它可能可能会会是一个最小成本结点，是一个最小成本结点，所以绝对不能杀死！所以绝对不能杀死！如果如果U是由上界得到，为了避免误杀是由上界得到，为了避免误杀(X)=U的结点，的结点，可在得到可在得到U时将时将U稍微变大一点点：假设稍微变大一点点：假设U是在处理是在处理结点结点Y时由上界时由上界u(Y)得到，则令得到，则令U=u(Y)+62如果如果U是由上界得到，为了避免误杀是由上界得到，为了避免误杀

50、(X)=U的结点，的结点，可在得到可在得到U时将时将U稍微变大一点点：假设稍微变大一点点：假设U是在处理是在处理结点结点Y时由上界时由上界u(Y)得到，则令得到，则令U=u(Y)+此时，对于此时，对于(X)=U，则有，则有C(X)(X)=U=u(Y)+u(Y)即即X的解成本一定比之前估计的上界值要大，不可的解成本一定比之前估计的上界值要大，不可能等于上界值，能等于上界值，所以所以X是没有意义的，可以杀死是没有意义的，可以杀死如此一来，对于修正后的如此一来，对于修正后的U，无论其来源是，无论其来源是还是还是，只要只要(X)U，则，则X结点可以被杀死结点可以被杀死639.1.5 分枝分枝-限界算法