计算机算法基础[第七章].ppt

计算机设计与分析,分枝限界法,0 预备知识,问题状态解状态状态空间答案状态,状态空间树活结点E-结点死结点,等等本节主要目的通过对n-皇后问题的分析，学习以上概念，并且了解回溯法,n-皇后问题描述,将n个皇后放置在一个nn的棋盘上，要求没有两个皇后可以互相攻击。攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。,8-皇后问题的一个解,该解的8元组表示:(4,6,8,2,7,1,3,5),n-皇后问题,用n-元组(x1,x2,xn)表示棋盘上皇后的位置状态下标表示皇后i(i=1,2,n)xi表示放置皇后i所在的列号显式约束条件：每个xi只从集合Si=1,2,n取值满足显式约束的所有元组确定一个可能的解空间 解空间由nn个n-元组组成隐式约束条件没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上 由前者得，所有解都是n-元组(1,2,n)的置换，因此，解空间缩小为 n！个元组,4-皇后问题解空间的树结构,结点按深度优先检索编号叶子结点有4！24个,解空间树结构的术语,树中每个结点确定求解问题的一个问题状态(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-结点一直保持到变成死结点为止限界函数以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点,4-皇后问题的限界函数,如果(x1,x2,xi)是到当前E-结点的路径，那么具有父-子标记xi+1的所有儿子结点是一些这样的结点，它们使得(x1,x2,xi+1)表示没有两个皇后正在互相攻击的一种棋盘格局。,4-皇后问题-回溯解,1 2 3 4,1234,4-皇后问题回溯法vs状态空间树,结点按深度优先检索编号叶子结点有4！24个,4-皇后问题回溯期间的生成树,分枝限界法,在生成当前E-结点全部儿子之后再生成其它活结点的儿子并且，用限界函数帮助避免生成不包含答案结点子树的状态空间FIFO检索：活结点表采用队LIFO检索：活结点表采用栈,FIFO分枝限界法例7.1（4-皇后问题）,4-皇后问题回溯 vs FIFO分枝-限界,回溯Win！,LC-检索（Least Cost）,分枝-限界失败的原因对下一个E-结点的选择规则过于死板如何解决？排序，让答案结点排在前面！寻找一种“有智力”的排序函数C()，该函数能够让答案结点尽早生成排序的标准下一个E-结点应当是生成答案结点花费成本最小的结点，因此C()又称作结点成本函数。LC：Least Cost,LC-检索（结点成本）,一：在生成一个答案结点之前，子树X需要生成的结点数。二：在子树X中离X最近的那个答案结点到X的路径长度。以图7.1为例节点1、18、34、29、35、30、38可计算其他结点可得到一个范围生成结点（12 18 34 5019 24 2930 3231）,LC-检索（结点成本函数）,C()定义如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本（即花费的代价，可以是级数、计算复杂度等）如果X不是答案结点且子树X不包含任何答案结点，则C(X)如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本,LC-检索（成本估计函数）,从前面的两个成本度量标准看，计算C()的工作量与原问题的解具有相同复杂度。因此需要成本估计函数g(X)出现的新问题仅利用g(X)会导致算法偏向纵深检查，无法有效处理下面这种情况：即g(W)g(Z)，但Z比W更接近答案结点,LC分枝-限界检索,c(X)f(h(X)+g(X)h(X)为根结点到结点X的成本LC-限界检索：选择c()值最小的活结点作为下一个E-结点BFS：g(X)0；f(h(X)X的级数D-Search：f(h(X)0；每当Y是X的一个儿子时，总有g(X)=g(Y)，LC分枝-限界检索：伴之有限界函数的LC-检索,15-谜问题（问题描述）,通过一系列合法移动将初始排列转换成目标排列。合法移动：将邻接于空格的牌移动到空格。,目标排列,一种初始排列,15-谜问题（是否有解）,棋盘存在16！种不同排列任一初始状态，可到达的状态为这些排列中的一半在求解问题前，需要判定目标状态是否在初始状态的状态空间中,15-谜问题（判定方法）,按目标状态给牌编号，空格为16用POSITION(i)记录编号为i的牌在初始状态中的位置；POSITION(16)表示空格图7.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)是偶数时，目标状态可由此初始状态到达,X1：空格恰好在上图棋盘中的蓝色格子上X0：空格在棋盘中的白色格子上,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,LC-检索的抽象化控制,line procedure LC(T,c)/为找答案结点检索T0 if T是答案结点 then 输出T;return endif1 E T2 将活结点表初始化为空3 loop4 for E的每个儿子X do5 if X是答案结点 then 输出从X到T的路径6 return7 endif8 call ADD(X)/X是新的活结点9 PARENT(X)E/指示到根的路径10 repeat(Continue),X加入到活结点表中,LC-检索的抽象化控制,loop11 if 不再有活结点 then print(“no answer code”)12 stop13 endif14 call LEAST(E)15 repeat16 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 endif1 E T2 将活结点表初始化为空3 loop3 if E是答案结点 then 输出从E到T的路径 return end if4 for E的每个儿子X do5 if X是答案结点 then 输出从X到T的路径6 return7 endif8 call ADD(X)/X是新的活结点9 PARENT(X)E/指示到根的路径10 repeat(Continue),LC-检索的特性 找最小成本答案结点,loop11 if 不再有活结点 then print(“no answer code”)12 stop13 endif14 call LEAST(E)15 repeat16 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对应一个三元组（pi,di,ti）ti表示作业i需要的单位处理时间di表示完成期限pi表示期限内未完成招致的罚款目标：从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);,下界函数m=maxi|iSX上界U,状态空间树动态元组,状态空间树静态元组,找最小成本答案结点的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 T3 else U u(T)+;ans 04 Endif5 将队列置初值为空（Continue）,FIFO分枝-限界算法(续1),6 loop7 for E的每个儿子X do8 if c(X)U then call ADDQ(X);PARENT(X)E 9 case10:X是解结点 and cost(X)U:11 U min(cost(T),u(T)+);12 ans X13:u(X)+U:U u(X)+14 endcase15 endif16 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 repeat23 return24 endif 25 call DELETEQ(X)26 if c(X)U then exit27 repeat28 repeat29end FIFOBB,LC分枝-限界的抽象化控制LCBB,18 if 不再有活结点or下一个E结点有c(X)=U19 then print(least cost=,U)20 while ans0 do21 print(ans)22 ans PARENT(ans)23 repeat24 return 25 endif26 call LEAST(X)27 repeat28end LCBB,效率分析,上下界函数的选择是决定分枝-限界算法效率的主要因素对U选择一个更好的初值是否能减少所生成的结点数？（否，根据定理7.4）扩展一些c()U的结点是否能减少所生成的结点数？（否，根据定理7.5）假定有两个成本估计函数c1()和c2()，对于状态空间树的每一个结点X，若有c1()=c2()=c(X)，则称c2()比c1()好。是否用较好的成本估计函数生成的结点数要少呢？（否，根据定理7.6和定理7.7）,0/1背包问题描述,极小化约束条件 xi=0 或xi=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(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9),例7.2的LC分枝 限界树,上面的数c下面的数u,大小固定元组,LCBB求解背包问题分析,状态空间树中结点的结构如何生成一给定结点的儿子如何识别答案结点如何表示活结点表,状态空间树中结点的结构,PARENT父结点链接指针LEVEL状态空间树中的级数TAGXi的取值CU背包的剩余空间PE已装入物品的效益值的和UBc(X),如何生成一给定结点的儿子,左儿子生成PARENT(Y)=XLEVEL(Y)=LEVEL(X)+1CU(Y)=CU(X)WLEVEL(X)PE(Y)=PE(X)+P LEVEL(X)TAG=1UB(Y)=UB(X),如何识别答案结点,当且仅当LEVEL(X)=n 1X是答案结点,如何表示活结点表,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 endif8 repeat9 return10 endif11 c c-W(i);LBB LBB+P(i)12 repeat13 UBB LBB14 end LUBOUND,生成一个新结点,line procedure NEWNODE(par,lev,t,cap,prof,ub)1 call GETNODE(I)2 PARENT(I)par；LEVEL(i)lev；TAG(I)t3 CU(I)cap；PE(I)prof；UB(I)ub4 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,N1 call INIT2 call GETNODE(E)3 PARENT(E)0;LEVEL(e)1;CU(E)M;PE(E)04 call LUBOUND(P,W,M,N,0,1,LBB,UBB)5 L LBB-;UB(E)UBB 6 loop7 i LEVEL(E);cap CU(E);prof PE(E),背包问题的LC分枝-限界算法,8 case9:i=N+1:10 if profL then L prof;ANS E11 endif12:else:13 if cap=W(i)then14 call NEWNODE(E,i+1,1,cap-W(i),prof+P(1)UB(E)15 endif16 call LUBOUND(P,W,cap,prof,N,i+1,LBB,UBB)17 if UBBL then18 call NEWNODE(E,i+1,0,cap,prof,UBB)19 L max(L,LBB-)20 endif21 endcase,背包问题的LC分枝-限界算法,22 if 不再有活结点 then exit endif23 call LARGEST(E)24 until UB(E)=L repeat25 call FINISH(L,ANS,N)26 end LCKNAP,FIFO分枝限界树,背包问题FIFO分枝-限界算法,line procedure FIFOKNAP(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,E,cap,prof int ANS,X,N1 call INIT;i 12 call LUBOUND(P,W,M,0,N,1,L,UBB)3 call NNODE(0,0,M,0,UBB)4 call ADDQ(#)5 while i=N do6 loop7 call DELETEQ(E),背包问题FIFO分枝-限界算法,8 case9:E=#:exit10:UB(E)=L:11 cap CU(E);prof PE(E)12 if cap=W(i)then13 call NNODE(E,1,cap-W(i),prof+P(i),UB(E)14 endif15 call LUBOUND(P,W,cap,prof,N,i+1,LBB,UBB)16 if UBB=L then17 call NNODE(E,0,cap,prof,UBB)18 L max(L,LBB)19 endif20 endcase21 repeat22 call ADDQ(#)23 i i+124 repeat25 ANS PE(X)=L的活结点X26 call FINISH(L,ANS,N)27 end FIFOKNAP,