算法设计与分析八.ppt

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