计算机算法基础课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机算法基础,分枝限界法,0,预备知识,问题状态,解状态,状态空间,答案状态,状态空间树,活结点,E-,结点,死结点,等等,本节主要目的,通过对,n-,皇后问题的分析，学习以上概念，并且了解回溯法,解空间树结构的术语,树中每个结点确定求解问题的一个,问题状态,(problem state),由根结点到其它结点的所有路径确定了这个问题的,状态空间,(state space),解状态,(solution states),是这样一些问题状态,S,，对于这些问题状态，由根到,S,的那条路径确定了这解空间中的一个元组（满足显式约束）,答案状态,(solution states),是这样一些解状态,S,，由根到,S,的路径确定了问题的一个解（满足隐式约束）,解空间的树结构为,状态空间树,(state space tree),利用状态空间树解题,1,设想状态空间树,2,生成问题状态,3,确定问题状态中哪些是解状态,4,哪些解状态是答案状态,生成问题状态,构造状态空间树,状态空间树术语,活结点,：自己已经生成而其所有的儿子结点还没有全部生成的结点。,E-,结点,（正在扩展的结点）：当前正在生成其儿子结点的活结点。,死结点,：不再进一步扩展或者其儿子结点已全部生成的生成结点。,静态树,(static trees),：树结构与所要解决的问题的实例无关。,动态树,(dynamic trees),：根据不同的实例而使用不同的树结构。,构造状态空间树的两个方法,回溯法,当前,E-,结点,R,，生成一个新的儿子,C,，则,C,就变成一个新的,E-,结点，对子树,C,完全检测后，,R,结点再次成为,E-,结点,分枝,-,限界方法,一个,E-,结点一直保持到变成死结点为止,限界函数,以上两种方法都使用,限界函数,杀死还没有全部生成其儿子结点的那些活结点,分枝限界法,在生成当前,E-,结点全部儿子之后再生成其它活结点的儿子,并且，用限界函数帮助避免生成不包含答案结点子树的状态空间,FIFO,检索：活结点表采用,队,LIFO,检索：活结点表采用,栈,LC,检索：最小成本检索,FIFO,分枝限界法例,9.1,（,4-,皇后问题）,39,4-,皇后问题,回溯,vs,FIFO,分枝,-,限界,回溯,Win,！,LC-,检索（,Least Cost,）,分枝,-,限界失败的原因,对下一个,E-,结点的选择规则过于死板,如何解决？,排序，让答案结点排在前面！,寻找一种“有智力”的排序函数,C(),，该函数能够让答案结点尽早生成,排序的标准,下一个,E-,结点应当是生成答案结点花费成本最小的结点，因此,C(),又称作,结点成本函数,。,LC,：,Least Cost,LC-,检索（结点成本的两个标准）,一：在生成一个答案结点之前，子树,X,需要生成的结点数。,二：在子树,X,中离,X,最近的那个答案结点到,X,的路径长度。以,图,9.1,为例,节点,1,、,18,和,34,、,29,和,35,、,30,和,38,的代价分别是,4,，,3,，,2,，,1,其他,2,，,3,，,4,级上的点代价应分别大于,3,，,2,，,1,生成结点（,12 18 34 5019 24 2930 3231,）,39,LC-,检索（结点成本函数）,C(),定义,如果,X,是答案结点，则,C(X),是由状态空间树的根结点到,X,的成本（即花费的代价，可以是级数、计算复杂度等）,如果,X,不是答案结点且子树,X,不包含任何答案结点，则,C(X),如果,X,不是答案结点但子树,X,包含答案结点，则,C(X),等于子树,X,中具有最小成本的答案结点的成本,LC-,检索（成本估计函数）,从前面的两个成本度量标准看， 计算,C(),的工作量与原问题的解具有相同复杂度。这是因为计算一个结点的代价通常要检索包含一个答案结点的子树才能确定，而这正是解决此问题所要作的检索工作，因此要得到精确的成本函数一般是不现实的,因此需要成本估计函数,g(X,),出现的新问题,仅利用,g(X,),会导致算法偏向纵深检查，无法有效处理下面这种情况：即,g(W)=g(Y,),，,LC,分枝,-,限界检索：伴之有限界函数的,LC-,检索,15-,谜问题（问题描述）,1,3,4,15,2,5,12,7,6,11,14,8,9,10,13,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,通过一系列合法移动将初始排列转换成目标排列。,合法移动：将邻接于空格的牌移动到空格。,目标排列,一种初始排列,15-,谜问题（是否有解）,棋盘存在,16,！种不同排列,任一初始状态，可到达的状态为这些排列中的一半,在求解问题前，需要判定目标状态是否在初始状态的状态空间中,15-,谜问题（判定方法）,按目标状态给牌编号，空格为,16,用,POSITION(i,),记录编号为,i,的牌在初始状态中的位置；,POSITION(16),表示空格,图,9.2(a),的,POSITION,(1 5 2 3 7 10 9 13 14 15 11 8 16 12 4 6),LESS(i,),是使得牌,j,小于牌,i,且,POSITION(j) POSITION(i,),的数目,LESS(1)=0; LESS(4)=1; LESS(12)=6,15-,谜问题（判定方法）,定理,7.1,当且仅当,sum(LESS(i,) + X),是偶数时，目标状态可由此初始状态到达,X,1,：空格恰好在上图棋盘中的蓝色格子上,X,0,：空格在棋盘中的白色格子上,15-,谜问题,(,宽度优先,),15-,谜问题,(,深度优先,),15-,谜问题（“智能”方法）,针对不同实例用相同规则检索，过于呆板和盲目,是否能够找到一种“智能”方法，给每个结点赋予成本值,:,如果结点在根结点到最近目标结点路径上，则成本为这条路径的长度：,C(1)=C(4)=C(10)=C(23)=3,否则，成本为,检索时杀死成本为,的结点,该方法的实际可操作性？,15-,谜问题（成本估计值函数）,C(X) = f(X) + g(X,),f(X,),：根到结点,X,的路径长度,1,）,g(X,),：是子树,X,中，由,X,到目标状态的最短路径长度的估计值,2,）状态,X,转换成目标状态所需的最小移动数,3,）,g(X,) =,不在其目标位置的非空白牌数目；该值应该比,2,）要小,C(X),是,C(X),的下界,15-,谜问题（使用,C(X),的,LC-,检索）,5,5,5,3,5,5,3,结点,1,为,E-,结点，生成其儿子结点,C(2)=1+4,C(3)=1+4,C(4)=1+2,C(5)=1+4,所以结点,4,成为,E-,结点,LC-,检索的抽象化控制,line procedure LC(T, c),/,为找答案结点检索,T,0 if T,是答案结点,then,输出,T; return endif,1 E, T,2,将活结点表初始化为空,3 loop,4 for E,的每个儿子,X do,5 if X,是答案结点,then,输出从,X,到,T,的路径,6 return,7 endif,8 call ADD(X) /X,是新的活结点,9 PARENT(X),E /,指示到根的路径,10 repeat,(Continue),X,加入到活结点表中,LC-,检索的抽象化控制,loop,11 if,不再有活结点,then,print(“no,answer code”),12 stop,13 endif,14 call LEAST(E),15 repeat,16 end LC,从活结点表中删除具有最小,c,值的活结点，并且将该结点赋给,E,LC-,检索的抽象化控制（正确性证明）,过程略,结论,对于有限状态空间树，以及存在答案结点的无限状态空间树，算法能够终止,对于没有答案结点的无限状态空间树，,LC,不会终止,检索局限在寻找估计成本不大于某个给定的限界,C,的答案结点是可取的,LC-,检索的抽象化控制（,vs. BFS, D-Search,）,LC,算法与,BFS,及,D-Search,基本相同,活结点表采用队列,vs,BFS,活节点表采用栈,vs,D-Search,不同：活结点表的构造，即下一个,E-,结点的选择规则不同。,LC-,检索的特性,LC,是否一定找得到具有最小成本的答案结点呢？,否,LC-,检索的特性定理,7.2,定理,7.2,在有限状态空间树,T,中，对于每一个结点,X,，令,c(X,),是,c(X,),的估计值且具有以下性质：对于每一对结点,Y,、,Z,，当且仅当,c(Y)c(Z,),时有,c(Y)c(Z,),。那么在使,c( ),作为,c( ),的估计值时，算法,LC,到达一个最小的成本答案结点终止。,LC-,检索的特性 定理,7.2,的证明,略,LC-,检索的特性 找最小成本答案结点,line procedure LC1(T, c) /,为找最小成本答案结点的,LC-,检索,0 if T,是答案结点,then,输出,T; return endif,1 E, T,2,将活结点表初始化为空,3 loop,3 if E,是答案结点,then,输出从,E,到,T,的路径,return end if,4 for E,的每个儿子,X do,5 if X,是答案结点,then,输出从,X,到,T,的路径,6 return,7 endif,8 call ADD(X) /X,是新的活结点,9 PARENT(X),E /,指示到根的路径,10 repeat,(Continue),LC-,检索的特性 找最小成本答案结点,loop,11 if,不再有活结点,then,print(“no,answer code”),12 stop,13 endif,14 call LEAST(E),15 repeat,16 end LC1,LC-,检索的特性 定理,7.3,定理,7.3,令,c(),是满足如下条件的函数，在状态空间树,T,中，对于每一个结点,X,，有,c(X)=c(X,),，而对于,T,中的每一个答案结点,X,，有,c(X)=c(X,),。如果算法在第,3,行终止，则所找到的答案结点是具有最小成本的答案结点。,证明略,分枝,-,限界算法,限界的目的,减少算法的盲目性，减小搜索空间，从而降低计算量,下界,使用使得,c(X) U,的所有活结点,X,可以被杀死,分枝,-,限界算法,(,解最优化问题,),一般化的带限期的作业排序问题,假定,n,个作业和一台处理机,作业,i,对应一个三元组（,p,i,d,i,t,i,）,t,i,表示作业,i,需要的单位处理时间,d,i,表示完成期限,p,i,表示期限内未完成招致的罚款,目标：从,n,个作业选取子集,J,，要求,J,中所有作业都能在各自期限内完成并且使得不在,J,中的作业招致的罚款总额最小,分枝,-,限界算法,(,实例,),n = 4;,(p,1,d,1,t,1,) = (5,1,1); (p,2,d,2,t,2,) = (10,3,2); (p,3,d,3,t,3,) = (6,2,1); (p,4,d,4,t,4,) = (3,1,1);,成本函数,:,圆形结点,X,c(X,),是根为,X,的子树中结点的最小罚款；方形结点，,c(X,)=,下界函数,m=maxi|i, S,X,，,S,X,是在结点,X,对,J,所选择的作业的子集,上界,状态空间树,元组大小可变,其中：圆形结点是答案结点，方形结点代表不可行的子集合,状态空间树,元组大小固定,找最小成本答案结点的,FIFO,分枝,-,限界方法,如何处理,c(X,) = U,的情况,为什么要处理？,如何处理？引进,，当,u(X) u(Y,),时，,u(X) u(X) + u(Y,),。,在算法中，比较,c(X,),与,U,的时候，可以对,U,作以下处理：,当,U,是成本值，则不变,当,U,由一单纯上界得出，,U= u(X,) + ,FIFO,分枝,-,限界算法,FIFOBB,line procedure FIFOBB(T, c, u, cost),/,为找出最小成本答案结点检索,T,假定,T,至少包含一个解结点且,c(X) = c(X) = u(X,),1 E, T; PARENT(E) 0;,2 if T,是解结点,then,U min(cost(T), u(T,) +,); ans, T,3 else U u(T,) +,; ans, 0,4 Endif,5,将队列置初值为空,（,Continue,）,FIFO,分枝,-,限界算法,(,续,1),6 loop,7 for E,的每个儿子,X do,8 if,c(X,) U then call ADDQ(X); PARENT(X),E,9 case,10 :X,是解结点,and cost(X,)U:,11,U min(cost(T), u(T,) +,);,12 ans, X,13 : u(X,)+,U: U,u(X,)+,14 endcase,15 endif,16 repeat,（,Continue,）,FIFO,分枝,-,限界算法,(,续,2),17 loop /,得到下一个,E-,结点,18 if,队列为空,then print(least,cost=, U),19 while,ans, 0 do,20 print(ans,),21 ans,PARENT(ans,),22 repeat,23 return,24 endif,25 call DELETEQ(X),26 if c(X,) =U,19 then,print(least,cost=, U),20 while ans,0 do,21 print(ans,),22 ans,PARENT(ans,),23 repeat,24 return,25 endif,26 call LEAST(X),27 repeat,28end LCBB,效率分析,上下界函数的选择是决定分枝,-,限界算法效率的主要因素,对,U,选择一个更好的初值是否能减少所生成的结点数？（,否,，根据定理,7.4,）,扩展一些,c()U,的结点是否能减少所生成的结点数？（,否,，根据定理,7.5,）,假定有两个成本估计函数,c,1,(),和,c,2,(),，对于状态空间树的每一个结点,X,，若有,c,1,()=c,2,()=c(X,),，则称,c,2,(),比,c,1,(),好。是否用较好的成本估计函数生成的结点数要少呢？（,否,，根据定理,7.6,和定理,7.7,）,0/1,背包问题描述,极小化,约束条件,x,i,=0,或,x,i,=1,，,1=i=n,0/1,背包问题的函数定义,c(X,)=,（答案结点）,c(X,)=,（不可行的结点）,c(X)=minc(LCHILD(X), c(RCHILD(X,),c(X,)= - Bound( , , j-1, M),U(X) = - Bound( , , j-1, M),其中,j,是结点,X,所在的层级,例,7.2,n=4, M=15,(p,1, p,2, p,3, p,4,) = (10, 10, 12, 18),(w,1, w,2, w,3, w,4,) = (2, 4, 6, 9),例,7.2,的,LC,分枝,限界树,上面的数,c,下面的数,u,大小固定元组,LCBB,求解背包问题分析,状态空间树中结点的结构,如何生成一给定结点的儿子,如何识别答案结点,如何表示活结点表,状态空间树中结点的结构,PARENT,父结点链接指针,LEVEL,状态空间树中的级数,TAG,X,i,的取值,CU,背包的剩余空间,PE,已装入物品的效益值的和,UB,c(X,),如何生成一给定结点的儿子,左儿子生成,PARENT(Y) = X,LEVEL(Y) = LEVEL(X) + 1,CU(Y) = CU(X) W,LEVEL(X),PE(Y) = PE(X) + P,LEVEL(X),TAG = 1,UB(Y) = UB(X),如何识别答案结点,当且仅当,LEVEL(X) = n,1,X,是答案结点,如何表示活结点表,Min-,堆,测试活结点表是否为空,常量时间,加结点到活结点表,log(n,),删除最小,UB,值的结点,log(n,),计算上界和下界的算法,line procedure LUBOUND(P, W, rw, cp, N, k, LBB, UBB),1 LBB, cp; c rw,;,2 for i k to N do,3 if c=W(j) then c c-W(j,),6 LBB LBB+P(j,),7 endif,8 repeat,9 return,10 endif,11 c c-W(i); LBB LBB+P(i,),12 repeat,13 UBB LBB,14 end LUBOUND,生成一个新结点,line procedure NEWNODE(par, lev, t, cap, prof, ub,),1 call GETNODE(I),2 PARENT(I) par,；,LEVEL(i) lev,；,TAG(I) t,3 CU(I) cap,；,PE(I) prof,；,UB(I) ub,4 call ADD(I),5 end NEWNODE,背包问题的,LC,分枝,-,限界算法,line procedure LCKNAP(P, W, M, N,),/,大小固定元组表示状态空间树,/,假设,P(1)/W(1)=P(2)/W(2)=P(N)/W(N),real P(N), W(N), M, L, LBB, UBB, cap, prof,int,ANS, X, N,1 call INIT,2 call GETNODE(E),3 PARENT(E) 0; LEVEL(e,) 1; CU(E) M; PE(E) 0,4 call LUBOUND(P, W, M, N, 0, 1, LBB, UBB),5 L LBB -,; UB(E) UBB,6 loop,7 i LEVEL(E); cap CU(E); prof,PE(E),背包问题的,LC,分枝,-,限界算法,8 case,9 :i=N+1:,10 if profL then L prof,; ANS E,11 endif,12 :else:,13 if cap=W(i,) then,14 call NEWNODE(E,i+1,1,cap-W(i),prof+P(1)UB(E),15 endif,16 call LUBOUND(P,W,cap,prof,N,i+1,LBB,UBB),17 if UBBL then,18 call NEWNODE(E,i+1,0,cap,prof,UBB),19 L max(L,LBB,-,),20 endif,21 endcase,背包问题的,LC,分枝,-,限界算法,22 if,不再有活结点,then exit endif,23 call LARGEST(E),24 until UB(E)=P(2)/W(2)=P(N)/W(N),real P(N), W(N), M, L, LBB, UBB, E, cap, prof,int,ANS, X, N,1 call INIT; i,1,2 call LUBOUND(P,W,M,0,N,1,L,UBB),3 call NNODE(0,0,M,0,UBB),4 call ADDQ(#),5 while i=L:,11 cap CU(E); prof,PE(E),12 if cap=W(i,) then,13 call NNODE(E,1,cap-W(i), prof+P(i),UB(E,),14 endif,15 call LUBOUND(P,W,cap,prof,N,i+1, LBB,UBB),16 if UBB=L then,17 call NNODE(E,0,cap,prof,UBB),18 L max(L,LBB,),19 endif,20 endcase,21 repeat,22 call ADDQ(#),23 i i + 1,24 repeat,25 ANS PE(X)=L,的活结点,X,26 call FINISH(L,ANS,N),27 end FIFOKNAP,