算法设计与分析(八).ppt

算法设计与分析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,如何求取满足规范函数的元组？,1.硬性处理法枚举，列出所有候选解，逐个检查是否为所需要的解 假定集合Si的大小是mi，则候选元组个数为 mm1m2mn缺点：盲目求解，计算量大2.寻找其它有效的策略 回溯或分枝限界法,回溯（分枝限界）法带来什么样的改进？避免盲目求解，对可能的元组进行系统化搜索。在求解的过程中，逐步构造元组分量，并在此过程中，通过不断修正的规范函数（有时称为限界函数）去测试正在构造中的n元组的部分向量（x1,xi），看其能否导致最优解。如果判定（x1,xi）不可能导致最优解，则将可能要测试的mi+1mn个向量一概略去，相对于硬性处理可大大减少计算量。,概念1.约束条件：问题的解需要满足的条件。可以分为显式约束条件和隐式约束条件。显式约束条件：一般用来规定每个xi的取值范围。如：xi0 即Si=所有非负实数 xi=0或xi=1 即 Si=0,1 lixiui 即Si=liaui 显式约束条件可以与所求解的问题实例I有关，也可以无关。解空间：实例I的满足显式约束条件的所有元组，即所有xi合 法取值的元组，构成I的解空间。隐式约束条件：用来规定I的解空间中那些满足规范函数的 元组，隐式约束将描述xi必须彼此相关的情况。,例8.1：8-皇后问题,在一个88棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个皇后都不能在同一行、同一列及同一条斜角线上。,行、列号：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，（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。如果选择了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-皇后问题,边：从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),(2),(2,3)等。,2）元组大小固定，每个都是n-元组 树边标记：由i级结点到i1级结点的那些边用xi的值来 标记，xi1或0。,解空间由根到叶结点的所有路径所确定。共有16个可能的元组。,共有2416个叶子结点，代表所有可能的4元组。,同一个问题可以有不同形式的状态空间树。,关于状态空间树的概念,状态空间树：解空间的树结构称为状态空间树(state space tree)问题状态：树中的每一个结点确定问题的一个状态，称为 问题状态(problem state)。状态空间：由根结点到其他结点的所有路径确定了这个问 题的状态空间(state space)。解状态：是这样一些问题状态S，对于这些问题状态，由根 到S的那条路径确定了这个解空间中的一个元组(solution states)。答案状态：是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（满 足隐式约束条件的解）(answer states)。,状态空间树的分解：在状态空间树的每个结点处，解空间被分解为一些子解空间，表示在一些分量取特定值情况下的解空间元素。,特点：被分解的子解空间互 不相交。但不是必须 条件。,静态树：树结构与所要解决的问题的实例无关(static trees)。,只要n=4，状态空间树都是这样,动态树：与实例有关的树称为动态树。(dynamic trees)对有些问题，根据不同的实例使用不同的树结构可 能更好，如：是不是先考虑x2的取值更好呢？这就需要根据实例来动态构造状态空间树。,状态空间树的构造：以问题的初始状态作为根结点，然后系统地生成其它问题状态的结点。在生成状态空间树的过程中，结点根据被检测情况分为三类：活结点：自己已经生成,但其儿子结点还没有全部生成并 且有待生成的结点。E-结点（正在扩展的结点）：当前正在生成其儿子结点 的活结点。死结点：不需要再进一步扩展或者其儿子结点已全部生 成的结点。,构造状态空间树的两种策略,1.深度优先策略 当E-结点R一旦生成一个新的儿子C时，C就变成一个新的E-结点，当完全检测了子树C之后，R结点再次成为E-结点。2.宽度优先策略 一个E-结点一直保持到变成死结点为止。限界函数：在结点生成的过程中，定义一个限界函数，用 来杀死还没有全部生成儿子结点的一些活结点 这些活结点已无法满足限界函数的条件，不可能导致问题的答案。,回溯法：使用限界函数的深度优先结点生成方法 称为回溯法（backtracking）分枝-限界方法：E结点一直保持到死为止的状 态生成方法称为分枝-限界方法（branch-and-bound）,深度优先策略下的结点生成次序（结点编号）,利用队列的宽度优先策略下的结点生成次序(BFS),利用栈的宽度优先策略下的结点生成次序（D-Search）,限界函数：如果（x1,x2,xi）是到当前E结点的路径，那么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继续扩展。（结点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，即皇后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。返回结点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,14,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-皇后问题的回溯法求解动画,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。,回溯法思想,第一步：为问题定义一个状态空间，这个空间必须至少包含问题 的一个解第二步：组织状态空间以便它能被容易地搜索。典型的组织方法是图或树第三步：按深度优先的方法从开始节点进行搜索 开始节点是第一个活节点（也是 E-节点：expansion node）如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了当前的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。,回溯的一般方法,procedure BACKTRACK(n)integer k,n;local X(1:n)k1 while k0 do if 还剩有没检验过的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 RBACKTRACK(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循环。算法印出所有的解，元组大小可变。,效率分析应考虑的因素效率分析应考虑的因素,（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 Carlo效率估计,一般思想在状态空间中生成一条随机路径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 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 时，它们在同一条斜角线上。,即：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)/在同一斜角线上/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(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)按非降次序排列条件一：条件二：仅当满足上述两个条件时，限界函数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个结点,