首页计算机计算机基础计算机算法设计与分析 07 第9章 分支-限界法.pptx

07 第9章 分支-限界法.pptx

页数:41页文件大小:308.4 KB来源: 计算机算法设计与分析ppt课件

本课件讲解分支-限界法,先对比回溯法说明其搜索方式的差异,再依次介绍LC-检索的提出与成本估计函数、15-谜问题的可达性判定与检索策略、LC-检索的抽象化控制与特性、分支-限界算法的成本函数与上界剪枝,最后给出FIFOBB与LCBB过程及方法评价。

第九章分支-限界法章节封面,标示本章主题为在解空间树上按成本估计搜索最优解
第九章目录页,列出LC-检索、15-谜问题、LC-检索的抽象化控制与特性、分支-限界算法各节
方法对比页,说明分支-限界法先生成当前E-结点的全部儿子并用限界函数避免无效分支
查看本课件的文字版(共 41 页,供检索与复制)

第1页:第九章 分支-限界法章节封面

1第九章分支-限界法

第2页:本章目录

29.1一般方法9.1.1 LC-检索9.1.2 15-谜9.1.3 LC-检索的抽象化控制9.1.4 LC-检索的特性9.1.5分支-限界算法

第3页:分支-限界法与回溯法的区别

39.1一般方法

  • 分支-限界法类似于回溯法,也是一种在问题的解空间树上搜索问题解的算法。但二者搜索方式不同。
  • 分支-限界法
  • 生成当前E-结点全部儿子之后,再生成其他活结点的儿子,
  • 使用限界函数帮助避免生成不包含答案结点子树的状态空间
  • 根据对状态空间数中结点检索次序的不同,可将分支-限界的设计策略分为
  • FIFO检索,活结点采用一张先进先出表(队列)
  • LIFO检索,活结点采用一张先进后出表(堆栈)

第4页:4-皇后问题的解空间树

4例9.1 4-皇后问题67891011234511213141516171234567891011121314151617

第5页:4-皇后问题的分支-限界搜索

5例9.1 4-皇后问题1918202130262731222367891011B23451BB12131424251516172829BBBBBBBBBBB678910111213141516171819202122232425262728293031… …B分支-限界法生成31个结点

第6页:回溯与分支-限界的结点数对比

631x4=318x1= 213x2= 415x4=313x2= 22x1=1B11x3=49x3=2BB8x2= 314x3=2B16x3=3B19x2= 124x2= 3BB29x2= 430x3=1回溯法生成16个结点

第7页:LC-检索的提出

79.1.1 LC-检索

  • 问题:在LIFO和FIFO分支-限界法中,对下一个E-节点的选择规则相当死板,在某种意义上是盲目的。对于可能快速检索到答案结点的结点没有给出任何优先权。
  • 解决:对活结点使用一个“有智力的”排序函数c(.)来选取下一个E-结点,往往可以加快到达一答案结点的速度。

第8页:结点成本的两种度量标准

89.1.1 LC-检索

  • 要对活结点计算优先次序,必然要附加计算工作,即付出代价。对于任意结点X,要付出的代价可以用两种标准来度量:①生成一个答案结点之前,子树X需要生成的结点数总是生成最小数目的结点。②子树X中离X最近的那个答案结点到X的路径长度生成由根到最近的那个答案结点路径上的那些结点。43211453291011222331

第9页:结点成本函数c(X)

99.1.1 LC-检索

  • c(.):“有智力的”排序函数,称为“节点的成本函数”:状态空间树的根结点到X的成本若X是答案结点c(X)=∞若X不是答案结点且子树X不包含任何答案结点子树X中具有最小成本的答案结点的成本否则Note:要得到结点成本函数c(.)所用的计算工作量与解原问题具有相同的复杂度,所以要得到精确的成本函数一般是不现实的。计算一个节点X的成本通常需要检索以X为根结点的整个子树才能确定。

第10页:成本估计函数ĝ(X)

109.1.1 LC-检索

  • 解决:在算法中检测活结点的次序通常根据能大致估计结点成本的函数ĝ(.)来排出。
  • ĝ(X):由X到达一个答案结点所需做的附加工作的估计函数。
  • 单纯使用函数ĝ(.)会导致算法偏向于做纵深检查。
  • 若ĝ(.)=c(X),可以用最小成本达到离根最近的答案结点,其它子树的结点无需生成。
  • 但通常情况下,ĝ(X)只是精确成本的一个估计值,因此偏于纵深检查可能会丢失掉更靠近根的答案结点。导致结果不理想。

第11页:改进的成本估计ĉ(X)

119.1.1 LC-检索

  • 改进:不仅考虑结点X到一个答案结点的估计成本值ĝ(.),还应考虑由根结点到结点X的成本h(X)
  • ĉ(X)=f(h(X))+ ĝ(X)
  • f(.)是一个非降函数,使f(.)不等于0,可以减少算法作偏向于纵深检查的可能性,使算法优先检索更靠近答案结点且又离根较近的结点。

第12页:LC-检索的定义

129.1.1 LC-检索

  • LC-检索(Least Cost search):选取成本估计函数ĉ的值最小的活结点作为下一个E-结点的检索策略。f(h(X))=结点X的级数,ĝ(X)ĝ0时,则变为BFS检索。f(h(X))=0,且每当Y是X的一个儿子时总有ĝ(X)≥ĝ(Y)时,则变为D-检索。
  • LC分枝-限界检索:伴有限界函数的LC-检索。BFS和D检索是LC-检索的特殊情况

第13页:15-谜问题描述

  • 139.1.2 15-谜问题154311252141167131098432187651211109151413a初始排列
  • 问题描述在一个分成16格的方形棋盘上,放有15块编了号码的牌。对这些牌给定一种初始排列,要求通过一系列的合法移动将这一初始排列转换成目标排列。b目标排列邻接空格的牌移到空格

第14页:状态与可达状态

149.1.2 15-谜问题

  • 每移动一次,就产生一种新的排列。这些排列称为这个谜问题的状态。
  • 初始排列称为初始状态,目标排列称为目标状态。
  • 若由初始状态到某状态存在一系列合法的移动,则称该状态可由初始状态到达。
  • 初始状态的状态空间由所有可从初始状态到达的状态构成。154311252141167131098154311252141167131098相当庞大

第15页:目标状态可达性的判定

  • 159.1.2 15-谜问题432187651211109151413
  • 在具体求解问题之前判定:目标状态是否在这个初始状态的状态空间中。
  • 方法:对棋盘的方格位置编上1~16的号码。位置i是在右图的目标排列中放i号牌的方格位置,位置16是空格的位置。
  • 假设POSITION(i)是编号为i的那块牌在初始状态下的位置号,1≤i<16;POSITION(16)表示空格的位置。
  • 对于任意一种状态,LESS (i)是使牌j<牌i,且POSITION(j)>POSITION(i)的j的数目。
  • 初始状态下,如果空格在右图的阴影位置中的某一格处,则令X=1;否则X=0。154311252141167131098LESS (1)=0LESS (4)=1LESS (12)=6

第16页:定理9.1与状态空间树

16

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

第17页:15-谜的搜索过程示意

17432186511710912151413421836511710912151413432186511710912151413432187651110912151413432186511710912151413421836511710912151413421836511710912151413321486511710912151413432111865710912151413432187651110912151413432187651115109121413432187651110912151413432186105117912151413432186511710912151413431862511710912151413842136511710912151413426183511710912151413421836511710912151413321486511710912151413432111865127109151413432111865710912151413432176581110912151413432187651211109151413上右下左右左上下右下左上下左下下左右下左上下尝试1:FIFO检索1234567891011121314151617181920212223上、右、下、左

第18页:三种检索策略的比较

189.1.2 15-谜问题

  • 尝试1:FIFO,找到离根最近的答案结点,但移动是千篇一律的,检索是呆板而盲目的。
  • 尝试2:深度优先,不管开始格局如何,总是采取由根开始的那条最左路径,有可能远离目标。
  • 尝试3:具有一定“智能”的检索方法。
  • 给状态空间树的每个结点X赋予一定的成本值c(X):由根出发到最近目标结点路径上的每个结点X赋予这条路径长度作为他们的成本值,其余结点的成本值赋予∞。

第19页:深度优先检索的路径

19尝试2:深度优先43218651171091215141314218365117109121514132上421836511710912151413右38421365117109121514134118214651231091571413821114651231091571413821114651231091571413842111651231091571413842111365121091571413842111365127109151413842111365710912151413下下5842111365127109151413下6左7上、右、下、左8上9上上10右11下12

第20页:15-谜的成本估计函数

209.1.2 15-谜问题

  • 切合实际的做法:给出一个便于计算成本估计值的函数ĉ(X)=f(X)+ĝ(X),f(X):由根到结点X的路径长度ĝ(X):以X为根的子树中由X到目标状态的一条最短路径长度的估计值。
  • 因此,ĝ(X)至少应是能把状态X转换成目标状态所需的最小移动数。
  • 一种可能的选择:ĝ(X)=不在其目标位置的非空白牌数目432186512111097151413

第21页:LC-检索下的状态展开

21432186511710912151413421836511710912151413432186511710912151413432187651110912151413432186511710912151413432187651110912151413432187651115109121413432187651110912151413432176581110912151413432187651211109151413上右下左右下左上下123459101112131+41+41+21+42+12+32+33+2

第22页:LC-检索的抽象化控制

229.1.3 LC-检索的抽象化控制

  • 设T是一棵状态空间树,c(.)是T中结点的成本函数。如果c(X)是根为X的子树中任一答案结点的最小成本,则c(T)是T中最小成本答案结点的成本。
  • 由于函数c(.)不容易实现,所以使用一个对c(.)估值的启发性函数ĉ(.)来代替。
  • 这个启发函数应易于计算并具有如下性质:如果X是一个答案结点或者是一个叶结点,则c(X)=ĉ(X)。

第23页:LC过程

23算法9.1 LC-检索Line procedure LC(T,ĉ)ifT是答案结点 then输出T; return end ifE←TloopforE的每个儿子XdoifX是答案结点 then输出从X到T的那条路径 return; end if callADD(X)repeatif不再有活结点 then print(‘no answer node’) stop; end if callLEAST(E) repeatEnd LC将一个活结点加入到活结点表中将一个活结点从活结点中删除保存结点X的父结点Emin堆

第24页:算法的终止条件

249.1.3 LC-检索的抽象化控制

  • 算法终止:找到答案结点或生成并检索了整棵树有限状态空间树
  • 无限状态空间树的终止:至少有一个答案结点,且对ĉ(.)作出适当选择。
  • 没有答案结点的无限状态空间树,则不会终止。
  • 将检索局限在寻找估计成本不大于某个给定的限界C的答案结点

第25页:活结点表的实现方式

  • 259.1.3 LC-检索的抽象化控制活结点表用队列实现FIFO检索
  • LC算法活结点表用堆栈实现LIFO检索得到下一个E-结点的选择规则不同

第26页:LC-检索的特性示例

269.1.4 LC-检索的特性

  • 算法LC找到一个满足约束条件的解时终止问题:具有最小成本的答案结点?10020220201041010∞∞∞∞方形叶子结点是答案结点cĉ原因:当c(X)>c(Y)时,有ĉ(X)<ĉ(Y)

第27页:定理9.2

279.1.4 LC-检索的特性

  • 定理9.2在有限状态空间树T中,对于每一个结点X,令ĉ(X)是c(X)的估计值且具有以下性质:对于每一对结点Y、Z,当且仅当c(Y)<c(Z)时有ĉ(Y)<ĉ(Z)。那么在使用ĉ()作为c()的估计值时,算法LC到达一个最小的成本答案结点且终止。
  • 若规定:对于每一个结点X,有ĉ(X)≤c(X)且对于答案结点X有ĉ(X) = c(X),仍不能保证算法LC找到最小成本答案结点
  • 对LC改进这样的ĉ(.)通常得不到

第28页:LC1过程

28算法9.2找最小成本答案结点的LC-检索Line procedure LC1(T,ĉ)E←T置活结点表为空 loopifE是答案结点 then输出从E到T的路径 return end ifforE的每一个儿子Xdo callADD(X); PARENT(X)←E repeatif不再有活结点 then print (‘No answer node’) stop end if callLEAST(E) repeatEnd LC1生成结点后立即加入活结点表

第29页:分枝-限界方法

299.1.5分枝-限界算法

  • 分枝-限界方法:生成当前E-结点的所有儿子之后,再将另一个活结点变成E-结点。①假定每一个答案结点X有一个与其相联系的成本函数c(X),并且会找到最小成本的答案结点。②成本估计函数ĉ(.):ĉ(X)≤c(X),由任一结点X得出解的下界—智能,减少盲目性。
  • 设置最小成本的上界U:使算法加速。ĉ(X) >U的所有活结点X可以被杀死。U的初值:启发式方法或∞,不断修改。只要U的初始值不小于最小成本答案结点的成本,就不会杀死可以到达最小成本答案结点的活结点

第30页:最优化问题的成本函数

309.1.5分枝-限界算法

  • 最优化问题---极小化问题
  • 成本函数:代表最优解的答案结点的c(X)是所有结点中成本最小的---目标函数可行解的目标函数值若X是可行解结点c(X)=∞若X是不可行解结点根为X的树中最小成本若X是部分解结点结点的成本
  • 状态空间树中每个答案结点都对应一个可行解,成本最小的答案结点对应最优解。
  • 估计函数ĉ(X)≤c(X):对目标函数进行估计,而不是估计达到一个答案结点在计算上的难易程度。

第31页:带期限的作业排序问题

319.1.5分枝-限界算法

  • 带期限的作业排序问题:允许作业有不同的处理时间每个作业i与一个三元组联系(pi,di,ti)目标:n个作业的子集合J,J中的作业都能在相应的期限内完成,且不在J中的作业招致的罚款总额最小。
  • 例: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),作业i的处理时间如果没有在期限值之前完成,招致pi的罚款

第32页:元组大小可变的状态空间树

32123456791011x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4121314815元组大小可变的状态空间树方形结点是不可行结点圆形结点都是答案结点对于圆形结点X,C(X)=根为X的子树中结点的最小罚款对于方形结点X,C(X) =∞

第33页:元组大小固定的状态空间树

332512367141530312829121326274102321511919x1=1x1=0x2=1x3=1x4=1010x2=0x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=01010101010圆形叶结点是答案结点22元组大小固定的状态空间树913198111415182124c05010610165511152115ĉ

第34页:罚款与成本估计的计算

349.1.5分枝-限界算法

  • 设SX是在结点X处选择的作业的子集,m=max{i|i∈SX},ĉ(X)=Σpiu(X)=Σpii<mi∈SXi∈SXX对应的子集SX的成本值(罚款)初始时,成本上界U=∞或U=Σpi1≤i≤n子树X中最小成本答案结点的成本的简单上界

第35页:各结点的罚款与估计值

3516x2=27x2=39x2=310x2=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=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),

第36页:上界U的更新与剪枝

369.1.5分枝-限界算法

  • U修改之后,活结点表中存在这样的X:ĉ(X)≥U
  • 当X即将成为E结点时将其杀掉
  • U的修改:①一个已找到的解的成本值②不是解成本的单纯上界可将ĉ(X)=U的结点杀死引入一个非常小的正常数ε来区分这两种情况ADDQ(X):将结点X加入队列DELETEQ(X):将结点X从队列中删去cost(X):若X是答案结点,对应解的成本a)处理一可行结点时修改而得b)找到一答案结点,但其成本值大于上界,说明该结点的子孙中还有成本更小的答案结点U=u(X)+ε

第37页:FIFOBB过程

37line procedure FIFOBB(T,ĉ,u,ε,cost)E←T; PARENT(E)←0;ifT是解结点 then U←min(cost(T),u(T)+ε);ans←T else U←u(T)+ε;ans←0 endif将队列置为空 loop for E的每个儿子X doifĉ(X)<U then callADDQ(X); PARENT(X)←E case:X是解结点andcost(X)<U: U←min(cost(X), u(X)+ε);ans←X:u(X)+ε<U: U←u(X)+ε end case endif repeat loopif队列为空 then print(“least cost=”,U) while ans≠0 do print(ans); ans←PARENT(ans) repeat return endif call DELETEQ(E)ifĉ(E)<U then exit endif repeat repeat end FIFOBB为找出最小成本答案结点检索T。假定T至少包含一个解结点且ĉ(X)≤c(X)≤u(X)

第38页:FIFO分支-限界的算法思想

38FIFO算法思想

  • 初始化
  • 令根结点T是当前E-结点;
  • 对估计成本上界U和答案解ans赋初值:如果T是解结点,U←min(T的成本,u(T)+ε),ans←T;否则U←u(T)+ε,ans←0;
  • 活结点队列置为空;
  • 对E的每个子结点X进行检验,添加到队列中,并修改U值
  • 如果ĉ(X)<U,将X加入到队列中,并对X进一步判断:如果X是解结点且X的成本<U,U←min(X的成本,u(X)+ε),ans←X;如果u(X)+ε<U,U←u(X)+ε;
  • 若队列为空,打印当前ans;否则从队列中获取下一个活结点E:若ĉ(E)<U,转到步骤2,否则转到步骤3。假定状态空间树T至少包含一个解结点,不可行结点的估计值ĉ(X)=∞;可行结点的估计值ĉ(X)≤c(X)≤u(X)。E←TU←min(cost(T),u(T)+ε)ADDQ(X)U←min(cost(X),u(X)+ε)DELETEQ(E)详细算法描述见P227算法9.3

第39页:带期限作业排序实例

带期限作业排序实例:四个作业的三元组取值如下表,目标是选出能在期限内完成的作业子集使罚款总额最小。

带期限作业排序实例中各作业的罚款、期限与处理时间
作业罚款 pi期限 di处理时间 ti
作业1511
作业21032
作业3621
作业4311

搜索过程中在每个结点计算罚款上界u(X)与成本下界ĉ(X),并用当前最优解成本更新上界U进行剪枝。

第40页:LCBB过程

40line procedure LCBB(T,ĉ,u,ε,cost)E←T; PARENT(E)←0;ifT是解结点 then U←min(cost(T),u(T)+ε); ans←T else U←u(T)+ε;ans←0 endif将活结点表初始化为空 loop for E的每个儿子X doifĉ(X)<U then callADDQ(X);PARENT(X)←E case:X是解结点and cost(X)<U: U←min(cost(X), u(X)+ε);ans←X:u(X)+ε<U: U←u(X)+ε end case endif repeatif不再有活结点or下一个E-结点有ĉ≥U then print(“least cost=”,U) while ans≠0 do print(ans); ans←PARENT(ans) repeat return endif callLEAST(E) repeat end LCBB为找出最小成本答案结点检索T。假定T至少包含一个解结点且ĉ(X)≤c(X)≤u(X)min堆活结点表中剩余结点都有ĉ≥U

第41页:分支-限界法的优缺点

41总结-分支限界法的优缺点

  • 有利于提高算法效率的特点
  • 首先扩展上层结点,采用“有智能”的限界函数,有利于大范围剪枝
  • 处理E结点时,一次扩展即得到所有子结点
  • 代价
  • 选择E结点是跳跃性的,需要保存结点的路径信息(PARENT),空间需求大
  • 维护“活结点表”,时间代价
  • 旅行商问题:占用空间回溯→分支限界→动态规划
顶部目录