9算法第九章分枝限界法剖析

《9算法第九章分枝限界法剖析》由会员分享，可在线阅读，更多相关《9算法第九章分枝限界法剖析（51页珍藏版）》请在金锄头文库上搜索。

1、第九章 分枝限界法,1,目录,9.1 一般方法 9.1.1 LC-检索 9.1.2 15-谜问题一个例子 9.1.3 LC-检索的抽象化控制 9.1.4 LC检索的特性 9.1.5 分枝限界算法 9.1.6 效率分析(略) 9.2 0/1背包问题(略) 9.3 货郎担问题(略),2,分枝限界法,分枝限界策略： 在生成当前E-结点的全部儿子结点之后，再生成其他活结点的儿子结点； 借助限界函数避免生成那些不包含答案结点的子树的状态空间。 根据结点检索次序，分枝限界策略可以分为不同的检索方法： FIFO检索：采用先进先出的方式(队列)使用活结点表。 LIFO检索：采用后进先出的方式(堆栈)使用活结点

2、表。,类似于BSF,类似于D-检索,成为死结点,3,例9.1 FIFO分枝限界法检索四皇后问题的状态空间树,4-皇后问题的状态空间树(图8.2-P195),1,2,18,34,50,3,8,13,19,24,29,35,40,45,51,56,61,4,3,8,13,19,24,29,35,40,45,51,56,61,B,9,11,14,16,B,B,30,32,B,B,36,38,52,54,57,59,B,B,B,15,B,31,B, , ,B,答案节点,分枝限界法一共处理了31个节点。,回溯法一共处理了16个节点(P198 图8.6)。,5,9.1.1 LC-检索,缺陷： 在LIFO和

3、FIFO分枝-限界法中，对下一个E-结点的选择是死板的、盲目的，对于可能快速检索到答案结点的结点没有给出任何优先权。 改进： 对活结点使用一个“有智力的”排序函数c来选取下一个E-结点，从而加快到达答案结点的检索速度。,6,要对活结点计算优先次序，必然要附加计算工作，即付出代价。对于任意结点X，要付出的代价可以用两种标准来度量：,生成一个答案结点之前，子树X需要生成的结点数； 在子树X中，离X最近的那个答案结点到X的路径长度。,2,1,总是生成最小数目的结点。,那条路径上的结点会成为E-结点。,答案结点,结点成本函数c是可以量化的,7,结点成本函数c,“有智力的”排序函数c也称为结点成本函数

4、如果X是答案结点，则c(X)是由状态空间树的根节点到X的成本(即所用的代价，可以是级数、计算复杂度等)； 如果X不是答案结点且子树X不包含任何答案结点，则c(X)=； 如果X不是答案结点，但子树X中包含答案结点，则c(X)等于子树X中具有最小成本的答案结点的成本。,8,函数c的计算工作量,结点成本函数c的计算工作量往往与原问题具有相同的复杂度。,计算一个节点X的成本通常需要检索以X为根结点的整个子树才能确定。,要得到精确的成本函数并不现实，一般大致估计结点成本。,9,估计函数(X),设(X)是由X到达一个答案结点所需做的附加工作的估计函数。 假设子树X中有答案结点； 设X是当前E-结点，X的儿

5、子结点是Y，(Y) (X) ； 若活结点表中其他结点成本估计值均大于(Y)，则Y在X之后成为新的E-结点。 该过程直到子树X全部检索完毕才可能生成子树X以外的结点。,10,(X)分析,只用(X)为结点排序是否适合? 不适合,只考虑未来的可能的代价,导致算法偏向于纵深方向检索。,理想:) 如果(X)=c(X)总成立，那么问题可以用最小成本到达离根最近的答案结点。,乐观的冒进,现实:( 但通常情况下，(X)只是精确成本的一个估计值，因此偏于纵深检查可能会丢失掉更靠近根的答案结点。导致结果不理想。,(X)是对未来可能发生的成本估计,11,结点成本估计函数,考虑结点X到一个答案结点的估计成本(X);

6、考虑根结点到结点X的成本h(X);,(X)=f(h(X)+ (X),(X),h(X),算法对活结点表进行检索时，优先选择更靠近答案结点但又离根结点较近的结点。,函数f是一个非降函数。不妨将f的作用理解为调整h和在成本估计函数中的影响比例。,12,LC-检索总结,LC-检索(Least Cost search)：选取成本估计函数的值最小的活结点作为下一个E-结点。 伴有限界函数的LC-检索称为LC分枝-限界检索。 f(h(X)=结点X的级数，(X)=0时，则变为BFS检索。 f(h(X)=0，且每当Y是X的一个儿子时总有(X)(Y)时，则变为D-检索。,(X)=f(h(X)+ (X),BFS和D

7、检索是LC-检索的特殊情况,13,9.1.2 15-谜问题一个例子,在一个分成16格的方形棋盘上放有15块编了号码的牌，如(a)所示，要求通过一系列合法的移动转换成(b)所示那样的目标排列。,若当前牌邻接有空位置，则可将牌移动到空位置。,(a),(b),14,术语定义,每移动一次，就会产生一个新的棋牌状态，即15-谜问题的状态。 初始排列称为初始状态。目标排列称为目标状态。 若由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达。 状态空间由所有可从初始状态到达的状态构成。,15,对棋盘的方格位置编上116的号码，编号顺序如图(b)所示，空格位是位置16。 设POSITION(i

8、)是棋牌i在初始状态时的位置号，1iPOSITION(i)的j的数目，即反序的数目。,(a),(b),函数定义,LESS(1)=0； LESS(4)=1；2 LESS(12)=6；7,6,11,8,9,10,16,定理9.1,定理9.1 当且仅当LESS(i)+X是偶数时，图(b)所示的目标状态可由此初始状态到达。,i=1,16,判定初始状态，若满足该条件，才能达到目标状态(b),(c),在初始状态下，如果空格在(c)的阴影位置中的某一格处，则令X=1；否则令X=0。,15-谜问题的状态空间树 结点：棋牌布局状态； 边：移动牌与移动空格等效，因此表示为空格的合法移动，依次为上、右、下、左。 儿

9、子结点:通过一次合法的移动可以到达的布局状态。,17,求解方法,法1：宽度优先FIFO检索 法2：深度优先检索 法3：LC检索,18,上,右,下,左,右,左,上,下,右,下,左,上,下,左,下,下,左,左,下,左,上,下,宽度优先FIFO检索,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,离根结点最近的答案结点。,上、右、下、左,19,求解方法,法1：宽度优先FIFO检索 能找到离根最近的答案结点，不管开局如何（不关心问题的具体实例），总是按千篇一律的顺序移动。 法2：深度优先检索 法3：LC检索,20,深度优先,1,2

10、,上,右,3,4,下,下,5,下,6,左,7,上、右、下、左,8,上,9,上,上,10,右,11,下,12,21,求解方法,法1：宽度优先FIFO检索 能找到离根最近的答案结点，但不管开局如何(不关心问题的具体实例)，总是按千篇一律的顺序移动。 法2：深度优先检索 不管开局如何（不关心问题的具体实例），总是采取由根开始的最左路径，呆板而盲目。搜索过程中有可能远离目标。 法3：LC检索,22,LC检索,给状态空间树的每个节点X赋予一定的成本c(X)。 将根结点到最近目标结点路径上的每个结点的成本设置为这条路径的长度。 其余结点成本赋值为。 在宽度优先搜索方式下，首先将根结点作为E-结点，将成本为

11、的子结点统统杀掉，只保留与根结点成本相同的子结点，并使其成为下一个E-结点。该策略重复进行，直到找到目标结点为止。,P221 图9.3(a) c(1)=c(4)=c(10)=c(23)=3,理想状态下,基本不可能得到这样的函数c。,23,便于计算成本估计值的函数： f(X)是由根到结点X路径的长度； (X)是以X为根的子树中由X到目标状态的一条最短路径长度的估计值。,(X)=f(X)+(X),定义：(X)=不在其目标位置的非空白棋牌数目,(X)是c(X)的下界,最小移动数,(X)=1,(2)=1+4,3,7,11,12,(3)=1+4,7,8,11,12,(4)=1+2,11,12,(5)=1

12、+4,6,7,11,12,24,下,1,4,(10)=2+1,(11)=2+3,(12)=2+3,当前实例下，LC-检索几乎和使用精确函数c一样有效，LC-检索的选择性比很多检索方法强很多。,25,9.1.3 LC-检索的抽象化控制,T是一棵状态空间树 c是T中结点的成本函数 c(X)是根为X的子树中答案结点的最小成本。 c(T)是T中最小成本答案结点的成本。,找到这样一个易于计算的c是很难的。,用启发函数来代替 易于计算 如果X是一个答案结点或者是一个叶结点，则c(X)= (X),26,抽象化控制思想,如果根结点T是答案结点，输出该节点，操作结束；否则，令T是当前的E-结点，此时活结点表为空

13、。 判断E的每个子结点X：如果X是答案结点，输出从X到T的路径，操作结束；否则，将X添加到活结点表中。 如果活结点表中不再有结点，操作结束；否则从中选择一个函数值最小的结点作为当前新的E-结点，重复步骤2。,若ADD和LEAST遵循FIFO原则操作(队列)，LC就转换成FIFO检索；若遵循LIFO原则操作(栈)，LC就转换成LIFO检索。,27,算法9.1 LC-检索,line procedure LC(T, ) If T是答案结点 then 输出T; return endif ET 将活结点表初始化为空 loop for E的每个儿子X do if X是答案结点 then 输出从X到T的那条

14、路径; return endif call ADD(X);PARENT(X)E repeat if 不再有活结点 then print(“no answer node”); stop endif call LEAST(E) repeat end LC,/为找一个答案结点，检索T,步骤1,步骤2,步骤3,选择最小的结点作为E-结点,X是新的活结点,记录X的父结点E,28,算法有穷性分析,有限 LC在找到一个答案结点或者检索完整棵状态空间树后会终止下来 无限 有答案节点 无答案节点,如果当前是一棵没有答案结点的无限状态空间树，算法怎样才会终止？,成本估算函数对于每对结点X和Y，在X的级数足够大于Y

15、的级数时，有(X) (Y)。,当成本估算函数不大于某个给定的限界C时，E-节点可取。,29,9.1.4 LC-检索的特性,LC是否一定能找得到具有最小成本c(G)的答案结点G呢？,答案结点,c ,E,E,c(X)c(Y) (X) (Y),如果使每对c(X)c(Y)的X、Y结点都有(X) (Y)，那么对于一棵存在答案结点的有限状态空间树，LC算法是否总会找到一个最小成本答案结点？,返回算法9.2,30,证明： 已知若T有限且存在答案结点，LC一定能找到一个答案结点。下面证明满足已知条件时，LC能找到最小成本答案结点。,定理9.2 在有限状态空间树T中，对于每一个结点X，令(X)是c(X)的估计值

16、且具有以下性质：对于每一对结点Y、Z，当且仅当c(Y)c(Z)时有(Y) (Z)。那么在使作为c的估计值时，算法LC到达一个最小的成本答案结点且终止。,31,假设LC在G处终止，c(G)c(G)。 找到距离G和G最近的共同祖先R。 R到G的路径为R、 1、 k、G。 R到G的路径为R、1、 j、G。 若能检索到G，则R必在某时间成为E-结点。 子结点1和1成为活结点。,最小成本答案结点,答案结点,E,c(R)=c(1)=c(k)= c(G) c(1)=c(k)=c(G)c(G),(1) (G), (k), (1),在i(1i k)变成E结点并到达G之前，1不能变成E-结点，与假设矛盾，命题得证。