《算法设计与分析(八).ppt》由会员分享,可在线阅读,更多相关《算法设计与分析(八).ppt(54页珍藏版)》请在三一办公上搜索。
1、算法设计与分析2012.9,王多强,八 回溯法,8.1 一般方法,回溯法是算法设计的基本方法之一。用于求解问题的一组特定性质的解或满足某些约束条件的最优解。1.什么样的问题适合用回溯法求解呢?基本要求:1)问题的解可用一个n元组(x1,xn)来表示,其中 的xi取自于某个有穷集Si。2)问题的求解目标是求取一个使某一规范函数 P(x1,xn)取极值或满足该规范函数条件的向量(也可能是满足P的所有向量)。,例:分类问题 对A(1:n)的元素分类问题 用n元组表示解:(x1,x2,xn)xi:表示第i小元素在原始数组里的下标,取自有穷集Si=1.n。规范函数P:A(xi)A(xi+1),1in,如
2、何求取满足规范函数的元组?,1.硬性处理法枚举,列出所有候选解,逐个检查是否为所需要的解 假定集合Si的大小是mi,则候选元组个数为 mm1m2mn缺点:盲目求解,计算量大2.寻找其它有效的策略 回溯或分枝限界法,回溯(分枝限界)法带来什么样的改进?避免盲目求解,对可能的元组进行系统化搜索。在求解的过程中,逐步构造元组分量,并在此过程中,通过不断修正的规范函数(有时称为限界函数)去测试正在构造中的n元组的部分向量(x1,xi),看其能否导致最优解。如果判定(x1,xi)不可能导致最优解,则将可能要测试的mi+1mn个向量一概略去,相对于硬性处理可大大减少计算量。,概念1.约束条件:问题的解需要
3、满足的条件。可以分为显式约束条件和隐式约束条件。显式约束条件:一般用来规定每个xi的取值范围。如:xi0 即Si=所有非负实数 xi=0或xi=1 即 Si=0,1 lixiui 即Si=liaui 显式约束条件可以与所求解的问题实例I有关,也可以无关。解空间:实例I的满足显式约束条件的所有元组,即所有xi合 法取值的元组,构成I的解空间。隐式约束条件:用来规定I的解空间中那些满足规范函数的 元组,隐式约束将描述xi必须彼此相关的情况。,例8.1:8-皇后问题,在一个88棋盘上放置8个皇后,且使得每两个之间都不能互相“攻击”,也就是使得每两个皇后都不能在同一行、同一列及同一条斜角线上。,行、列
4、号:18 皇后编号:18,约定皇后i放到第i行的某一列上。解的表示:可以用8-元组(x1,x8)表示,其中xi是皇后i所在 的列号。显式约束条件:Si=1,2,3,4,5,6,7,8,1i8 解空间:所有可能的8元组,有88个。隐式约束条件:用来描述xi之间的关系,即没有两个xi可以相 同且没有两个皇后可以在同一条斜角线上。由隐式约束条件可知:可能解只能是(1,2,3,4,5,6,7,8)的 置换(排列),最多有8!个。,图中的解表示为一个8-元组为(4,6,8,2,7,1,3,5),例8.2 子集和数问题,已知n+1个正数w1,w2,wn和M。要求找出wi的和数等于M的所有子集。例:n4,(
5、w1,w2,w3,w4)(11,13,24,7),M=31。则满足要求的子集有:直接用元素表示:(11,13,7)和(24,7)用元素下标表示(k-元组):(1,2,4)和(3,4)用元素下标表示(n-元组):(1,1,0,1)和(0,0,1,1),解的表示:用下标的形式表示。形式一:问题的解为k-元组(x1,x2,xk),1kn。不同的解可以是大小不同的元组,如(1,2,4)和(3,4)。显式约束条件:xi j|j为整数且1jn。隐式约束条件:1)没有两个xi是相同的;2)wxi的和为M;3)xixi1,1in(避免重复元组),形式二:解由n-元组(x1,x2,xn)表示,其中xi0,1。如
6、果选择了wi,则xi1,否则xi0。例:(1,1,0,1)和(0,0,1,1)特点:所有元组具有统一固定的大小。显式约束条件:xi0,1,1in;隐式约束条件:(xi wi)=M 解空间:所有可能的不同元组,总共有2n个元组,解空间的组织形式 回溯法将通过系统地检索给定问题的解空间来求解,这需要有效地组织问题的解空间把元组表示成为有结构的组织方式。采用何种形式组织问题的解空间?可以用树结构组织解空间状态空间树。,例8.3 n-皇后问题。8皇后问题的推广,即在nn的棋盘 上放置n个皇后,使得它们不会相互攻击。解空间:由n!个n-元组组成.实例:4皇后问题的解空间树结构如下所示:,n-皇后问题,边
7、:从i级到i+1级的边用xi的值标记,表示将皇后i放到第i行的第xi列。如由1级到2级结点的边给出x1的各种取值:1、2、3、4。解空间:由从根结点到叶结点的所有路径所定义。注:共有4!24个叶结点,反映了4元组的所有可能排列 称为排列树。,例8.4 子集和数问题的解空间的树结构 两种元组表示形式:1)元组大小可变(xixi+1)树边标记:由i级结点到i1级结点的一条边用xi来表示,表示k-元组里的第i个元素是已知集合中下标 为xi的元素。,解空间由树中的根结点到任何结点的所有路径所确定:(),(1),(1,2),(1,2,3),(1,2,3,4),(1,2,4),(1,3,4),(1,4),
8、(2),(2,3)等。,2)元组大小固定,每个都是n-元组 树边标记:由i级结点到i1级结点的那些边用xi的值来 标记,xi1或0。,解空间由根到叶结点的所有路径所确定。共有16个可能的元组。,共有2416个叶子结点,代表所有可能的4元组。,同一个问题可以有不同形式的状态空间树。,关于状态空间树的概念,状态空间树:解空间的树结构称为状态空间树(state space tree)问题状态:树中的每一个结点确定问题的一个状态,称为 问题状态(problem state)。状态空间:由根结点到其他结点的所有路径确定了这个问 题的状态空间(state space)。解状态:是这样一些问题状态S,对于这
9、些问题状态,由根 到S的那条路径确定了这个解空间中的一个元组(solution states)。答案状态:是这样的一些解状态S,对于这些解状态而言,由根到S的这条路径确定了这问题的一个解(满 足隐式约束条件的解)(answer states)。,状态空间树的分解:在状态空间树的每个结点处,解空间被分解为一些子解空间,表示在一些分量取特定值情况下的解空间元素。,特点:被分解的子解空间互 不相交。但不是必须 条件。,静态树:树结构与所要解决的问题的实例无关(static trees)。,只要n=4,状态空间树都是这样,动态树:与实例有关的树称为动态树。(dynamic trees)对有些问题,根据
10、不同的实例使用不同的树结构可 能更好,如:是不是先考虑x2的取值更好呢?这就需要根据实例来动态构造状态空间树。,状态空间树的构造:以问题的初始状态作为根结点,然后系统地生成其它问题状态的结点。在生成状态空间树的过程中,结点根据被检测情况分为三类:活结点:自己已经生成,但其儿子结点还没有全部生成并 且有待生成的结点。E-结点(正在扩展的结点):当前正在生成其儿子结点 的活结点。死结点:不需要再进一步扩展或者其儿子结点已全部生 成的结点。,构造状态空间树的两种策略,1.深度优先策略 当E-结点R一旦生成一个新的儿子C时,C就变成一个新的E-结点,当完全检测了子树C之后,R结点再次成为E-结点。2.
11、宽度优先策略 一个E-结点一直保持到变成死结点为止。限界函数:在结点生成的过程中,定义一个限界函数,用 来杀死还没有全部生成儿子结点的一些活结点 这些活结点已无法满足限界函数的条件,不可能导致问题的答案。,回溯法:使用限界函数的深度优先结点生成方法 称为回溯法(backtracking)分枝-限界方法:E结点一直保持到死为止的状 态生成方法称为分枝-限界方法(branch-and-bound),深度优先策略下的结点生成次序(结点编号),利用队列的宽度优先策略下的结点生成次序(BFS),利用栈的宽度优先策略下的结点生成次序(D-Search),限界函数:如果(x1,x2,xi)是到当前E结点的路
12、径,那么xi的儿子结点xi+1是一些这样的结点,它们使得(x1,x2,xi,xi+1)表示没有两个皇 后正在相互攻击的一种棋盘格局。开始状态:根结点1,表示还没有放置任何皇后,空棋盘。结点的生成:依次考察皇后1皇后n的位置。,例:4-皇后问题的回溯法求解,根结点1,开始状态,唯一的活结点解向量:(),1,1,2,生成结点2,表示皇后1被放到第1行的第1列上,该结点是从根结点开始第一个被生成结点。解向量:(1)结点2变成新的E结点,下一步扩展结点2,按照自然数递增的次序生成儿子结点。,x1=1,1,2,由结点2生成结点3,即皇后2放到第2行第2列。利用限界函数杀死结点3。返回结点2继续扩展。(结
13、点4,5,6,7不会生成),3,x1=1,x2=2,B,1,2,由结点2生成结点8,即皇后2放到第2行第3列。结点8变成新的E结点。解向量:(1,8)从结点8继续扩展。,3,x1=1,x2=2,B,8,x2=3,1,2,由结点8生成结点9,即皇后3放到第3行第2列。利用限界函数杀死结点9。返回结点8继续扩展。(结点10不会生成),3,x1=1,x2=2,B,8,x2=3,9,x3=2,B,1,2,结点8的所有儿子已经生成,但没有导出答案结点,变成死结点。结点8被杀死。返回结点2继续扩展。,3,x1=1,x2=2,B,8,x2=3,9,x3=2,B,11,x3=4,B,由结点8生成结点11,即皇
14、后3放到第3行第4列。利用限界函数杀死结点11。返回结点8继续。(结点12不会生成),1,2,由结点2生成结点13,即皇后2放到第2行第4列。结点13变成新的E结点。解向量:(1,4)从结点13继续扩展。,3,x1=1,x2=2,B,8,x2=3,9,x3=2,B,11,x3=4,B,13,x2=4,1,2,由结点13生成结点14,即皇后3放到第3行第2列。结点14变成新的E结点。解向量:(1,4,2)从结点14继续扩展。,3,x1=1,x2=2,B,8,x2=3,9,x3=2,11,x3=4,13,x2=4,14,x3=2,1,2,由结点14生成结点15,即皇后4放到第4行第3列。利用限界函
15、数杀死结点15。返回结点14,结点14不能导致答案结点,变成死结点,被杀死。返回结点13继续扩展。,3,x1=1,x2=2,B,8,x2=3,9,x3=2,11,x3=4,13,x2=4,14,x3=2,B,B,15,x4=3,B,1,2,由结点13生成结点16,即皇后3放到第3行第3列。利用限界函数杀死结点16。返回结点13,结点13不能导致答案结点,变成死结点,被杀死。返回结点2继续扩展。结点2不能导致答案结点,变成死结点,被杀死。返回结点1继续扩展。由结点1生成结点18,即皇后1放到第1行第2列。,3,x1=1,x2=2,B,8,x2=3,9,x3=2,11,x3=4,13,x2=4,1
16、4,x3=2,B,B,15,x4=3,B,16,B,x3=3,由结点1生成结点18,即皇后1放到第1行第2列。结点18变成E结点。,扩展结点18生成结点19,即皇后2放到第2行第1列。,返回结点18,生成结点29,即皇后2放到第2行第4列。结点29变成E结点。,利用限界函数杀死结点19。,返回结点18,生成结点24,即皇后2放到第2行第3列。,利用限界函数杀死结点24。,结点31是答案结点。解向量:(2,4,1,3)算法终止(找到了一个解)。,扩展结点29生成结点30,即皇后3放到第3行第1列。结点30变成E结点。,扩展结点30生成结点31,即皇后4放到第4行第3列。,4-皇后问题的回溯法求解
17、动画,1 2 3 4,1234,4-皇后问题回溯期间生成的树,回溯算法的描述,设(x1,x2,xi-1)是由根到一个结点的路径。T(x1,x2,xi-1)是下述所有结点xi的集合,它使得对于每一个xi,(x1,x2,xi-1,xi)是由根到结点xi的路径。限界函数Bi:如果路径(x1,x2,xi)不可能延伸到一个答案 结点,则Bi(x1,x2,xi)取假值,否则取真值。解向量X(1:n)中的每个xi即是选自集合 T(x1,x2,xi-1)且使Bi为真的xi。,回溯法思想,第一步:为问题定义一个状态空间,这个空间必须至少包含问题 的一个解第二步:组织状态空间以便它能被容易地搜索。典型的组织方法是
18、图或树第三步:按深度优先的方法从开始节点进行搜索 开始节点是第一个活节点(也是 E-节点:expansion node)如果能从当前的E-节点移动到一个新节点,那么这个新节点将变成一个活节点和新的E-节点,旧的E-节点仍是一个活节点。如果不能移到一个新节点,当前的E-节点就“死”了(即不再是一个活节点),那么便只能返回到最近被考察的活节点(回溯),这个活节点变成了当前的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时,搜索过程结束。,回溯的一般方法,procedure BACKTRACK(n)integer k,n;local X(1:n)k1 while k0 do if 还剩有没检
19、验过的X(k)使得 X(k)T(X(1),X(k-1)and B(X(1),X(k)=true then if(X(1),X(k)是一条已抵达一答案结点的路径 then print(X(1),X(k)endif k k+1/考虑下一个集合/else k k-1/回溯到先前的集合/endif repeatend BACKTRACK,回溯方法的抽象描述。该算法求出所有答案结点。在X(1),X(k-1)已经被选定的情况下,T(X(1),X(k-1)给出X(k)的所有可能的取值。限界函数B(X(1),X(k)判断哪些元素X(k)满足隐式约束条件。,回溯算法的递归表示,procedure RBACKTR
20、ACK(k)global n,X(1:n)for 满足下式的每个X(k):X(k)T(X(1),X(k-1)and B(X(1),X(k)=true do if(X(1),X(k)是一条已抵达一答案结点的路径 then print(X(1),X(k)endif call RBACKTRACK(k+1)repeatend RBACKTRACK,回溯方法的递归程序描述。调用:RBACKTRACK(1)。进入算法时,解向量的前k-1个分量X(1),X(k-1)已赋值。,说明:当kn时,T(X(1),X(k-1)返回一个空集,算法不再进入for循环。算法印出所有的解,元组大小可变。,效率分析应考虑的因
21、素效率分析应考虑的因素,(1)生成下一个X(k)的时间(2)满足显式约束条件的X(k)的数目(3)限界函数Bi的计算时间(4)对于所有的i,满足Bi的X(k)的数目权衡:限界函数生成结点数和限界函数本身所需的计算时间,重新排列方法,用于检索效率的提高基本思想:在其它因素相同的情况下,从具有最少元素的集合中作下一次选择。该策略已证明对n-皇后问题及其它一些问题无效,效率分析,效率分析中应考虑的因素(1)(3)与实例无关(4)与实例相关有可能只生成O(n)个结点,有可能生成几乎全部结点最坏情况时间O(p(n)2n),p(n)为n的多项式O(q(n)n!),q(n)为n的多项式,Monte Carl
22、o效率估计,一般思想在状态空间中生成一条随机路径X为该路径上的一个结点,且X在第i级mi为X没受限界的儿子结点数目从mi随机选择一个结点作为下一个结点路径生成的结束条件:1)叶子结点;或者2)所有儿子结点都已被限界所有这些mi可估算出状态空间树中不受限界结点的总数m,效率估计算法,procedure ESTIMATE m1;r 1;k 1 loop TkX(k):X(k)T(X(1),X(k-1)and B(X(1),X(k)if SIZE(Tk)=0 then exit endif rr*SIZE(Tk)mm+r X(k)CHOOSE(Tk)KK+1 repeat return(m)end
23、ESTIMATE估算的条件限制:使用固定的限界函数,8.2 n-皇后问题,怎么判断是否形成了互相攻击的格局?,不在同一行上:约定不同的皇后在不同的行不在同一列上:xixj,(i,j1:n)不在同一条斜角线上:如何判定?,n元组:(x1,x2,xn),1)棋盘行、列用1n编号2)在由左上方到右下方同一斜角线上的每一个元素有相同 的“行列”值3)在由右上方到左下方同一斜角线上的每一个元素有相同 的“行列”值,左上方右下方相同的“行列”值122334,右上方左下方相同的“行列”值132231,判别条件:假设两个皇后被放置在(i,j)和(k,l)位置上,则仅当:i-j=k-l 或 i+j=k+l 时,
24、它们在同一条斜角线上。,即:j-l=i-k 或 j-l=k-i亦即:当且仅当|j-l|=|i-k|时,两个皇后在同一斜角线上。,过程PLACE(k)根据以上判别条件,判定皇后k是否可以放置在X(k)的当前值处:不等于前面的X(1),X(k-1)的值,且 不能与前面的k-1个皇后在同一斜角线上。,Place算法,procedure PLACE(k)/如果皇后k可以放在第k行第X(k)列,则返回true,否则返回false/global X(1:k);integer i,k i 1 while i k do if X(i)=X(k)/在同一列上/or ABS(X(i)-X(k)=ABS(i-k)/
25、在同一斜角线上/then return(false)endif i i1 repeat return(true)end PLACE,NQUEENS算法对算法8.1用PLACE过程改进后得到求解n-皇后问题的算法:NQUEENS,procedure NQUEENS(n)/在nn棋盘上放置n个皇后,使其不能相互攻击。算法求出所有可能的位置/integer k,n,X(1:n);X(1)0;k1/k是当前行,X(k)是当前列/while k0 do/对所有的行执行以下语句/X(k)X(k)+1/移到下一列/while X(k)n and not PLACE(k)do/检查是否能放置皇后/X(k)X(
26、k)+1/当前X(k)列不能放置,后推一列/repeat if X(k)n/找到一个位置/then if k=n/是一个完整的解吗?/then print(X)/是,打印解向量/else kk+1;X(k)0/否,转下一皇后/endif else kk-1 endif repeatend NQUEENS,算法分析,PLACE算法:O(k-1)NQUEENS算法:,8!,8.3 子集和数问题,元组大小固定:n元组(x1,x2,xn),xi1或0结点:对于i级上的一个结点,其左儿子对应于xi=1,右儿子对应于xi0。限界函数的选择 约 定:W(i)按非降次序排列条件一:条件二:仅当满足上述两个条件
27、时,限界函数B(X(1),X(k)=true注:如果不满足上述条件,则X(1),X(k)根本不可能导致一个答案结点。,/W(i)按非降次序排列,W(1)M,/,子集和数的递归回溯算法,procedure SUMOFSUB(s,k,r)global integer M,n;global real W(1:n);global boolean X(1:n),real r,s;integer k,j X(k)1/生成左儿子,Bk-1=true,s+W(k)M/if s+W(k)=M then/找到答案/print(X(j),j1 to k)/输出答案/else if s+W(k)+W(k+1)=M and s+W(k+1)=M/确保Bktrue/then X(k)0 call SUMOFSUB(s,k+1,r-W(k)endifend SUMOFSUB,向前看两步,可以的话才进行下一步处理,SUMOFSUB的一个实例,n=6,M=30,W(1:6)=(5,10,12,13,15,18)方形结点:s,k,r,圆形结点:输出答案的结点,共生成20个结点,