计算机算法设计与分析：第八章_回溯法

第八章第八章 回溯法回溯法Ø8.1 一般方法一般方法Ø8.2 8-皇后问题皇后问题Ø8.3 子集和数问题子集和数问题作业：作业： P215 1、、3、、8、、98.1 一般方法一般方法Ø什么是回溯什么是回溯回溯回溯§迷宫游戏迷宫游戏Ø什么是回溯法什么是回溯法§回溯法是一种回溯法是一种搜索搜索算法算法§回溯法是以回溯法是以深度优先深度优先的方式系统地搜索问题的方式系统地搜索问题的解的解, 它适用于解一些组合数较大的问题它适用于解一些组合数较大的问题回溯回溯入口入口出口出口回溯回溯回溯回溯§规范函数规范函数问题的解可以用一个问题的解可以用一个n元组元组(x1, … , xn)来表示，其中来表示，其中的的xi取自于某个取自于某个有穷集有穷集Si , 并且这些解必须使得某一并且这些解必须使得某一限界函数限界函数P(x1, … , xn)取极值或满足条件取极值或满足条件§硬性处理硬性处理构造，逐一测试构造，逐一测试§回溯法回溯法不断地用修改过的限界函数不断地用修改过的限界函数Pi(x1,…,xn)去测试正在构去测试正在构造的造的n元组的部分向量元组的部分向量, 看是否可能导致最优解看是否可能导致最优解, 如果如果不能不能, 就将可能要测试的就将可能要测试的mi+1 … mn个向量略去。

个向量略去Ø回溯法的基本概念回溯法的基本概念§回溯法的解需要满足一组综合的约束条件回溯法的解需要满足一组综合的约束条件, 通常分通常分为为: 显式约束和隐式约束显式约束和隐式约束§显式约束条件显式约束条件: 限定每个限定每个x只从一个给定的集合上取只从一个给定的集合上取值值, 满足显式约束的所有元组确定一个可能的解空间满足显式约束的所有元组确定一个可能的解空间 例例: xi>=0 , si={所有非负实数所有非负实数}§隐式约束条件隐式约束条件: 描述了描述了xi必须彼此相关的情况必须彼此相关的情况Ø回溯法的基本概念回溯法的基本概念§ 解空间：满足显式约束条件的元组解空间：满足显式约束条件的元组§ 解空间中满足隐式约束条件的决策序列称为可行解解空间中满足隐式约束条件的决策序列称为可行解§ 通常将解空间画成树的形状通常将解空间画成树的形状, ,称为解空间树称为解空间树Ø回溯法的基本概念回溯法的基本概念例例: 4-皇后问题皇后问题§在一个在一个4*4棋盘上放棋盘上放4个皇后个皇后, 使每两个皇后之间都不使每两个皇后之间都不能互相能互相“攻击攻击”, 即使得每两个皇后都不能在同一行、即使得每两个皇后都不能在同一行、同一列及同一条斜角线上。

同一列及同一条斜角线上§4皇后问题可以表示为皇后问题可以表示为4-元组元组(x1, … ,x4) ，其中，其中xi是放是放置皇后置皇后i所在的列号所在的列号§显式约束条件显式约束条件: si={1, 2, 3, 4}, 1≤i≤4§隐式约束条件隐式约束条件: 没有两个没有两个xi可以相同可以相同, 且没有两个皇后且没有两个皇后可以在同一条斜角线上可以在同一条斜角线上Q1Q2Q3Q4145674334101112942421415161732322021222343432526272841143031323331133813341924291342183450342………Ø4-皇后问题的解空间树皇后问题的解空间树x1=1x2=2§问题描述问题描述: 已知已知n+1个正数个正数: wi (1≤i≤n)和和M, 要求找出要求找出wi的和数是的和数是M的所有子集的所有子集 例例: n=4 , (w1, w2, w3, w4 )=(11,13,24,7) , M=31 满足要求的子集是满足要求的子集是(11, 13, 7)和和(24, 7)§用用wi的下标来表示解向量更为方便的下标来表示解向量更为方便, 因此这两个解向因此这两个解向量可以表示为量可以表示为: (1, 2, 4)和和(3, 4) §显式约束条件显式约束条件: xi∈∈{ j | j是是wi的下标值的下标值, 1≤j≤n }§隐式约束条件隐式约束条件: 要求没有两个要求没有两个xi是相同的是相同的, 且相应的且相应的wi的和数等于的和数等于M§为避免产生同一个子集的重复情况为避免产生同一个子集的重复情况(如如(1,2,4)和和(1,4,2)), 附加一个隐式约束条件附加一个隐式约束条件: xi

要遍历树才能结束§回溯法在回溯法在求问题的任一解求问题的任一解时时, 只要搜索到问题的一个只要搜索到问题的一个解就可以结束解就可以结束§回溯法在包含问题所有解的回溯法在包含问题所有解的解空间树解空间树中中, 按深度优按深度优先的策略先的策略, 从根结点出发搜索解空间树从根结点出发搜索解空间树§回溯法搜索至解空间树的任一结点时回溯法搜索至解空间树的任一结点时, 先判断该结先判断该结点是否肯定不包含问题的解如果肯定不包含点是否肯定不包含问题的解如果肯定不包含, 则跳则跳过以该结点为根的子树过以该结点为根的子树, 逐层向其祖先结点回溯否逐层向其祖先结点回溯否则就进入该子树则就进入该子树, 继续按深度优先的策略进行搜索继续按深度优先的策略进行搜索Ø回溯法的基本概念回溯法的基本概念Ø解空间树解空间树(状态空间树状态空间树)的术语的术语§问题状态问题状态(problem state): 树中的每一个结点确定所求树中的每一个结点确定所求解问题的一个问题状态解问题的一个问题状态§状态空间状态空间(state space): 由根结点到其他结点的所有路由根结点到其他结点的所有路径确定了这个问题的状态空间径确定了这个问题的状态空间§解状态解状态(solution states): 是这样一些问题状态是这样一些问题状态S, 对于对于这些问题状态这些问题状态, 由根到由根到S的那条路径确定了这个解空间的那条路径确定了这个解空间中的一个元组中的一个元组§答案状态答案状态(answer states): 是这样的一些解状态是这样的一些解状态S, 对于对于这些解状态而言这些解状态而言, 由根到由根到S的这条路径确定了这问题的的这条路径确定了这问题的一个解一个解§静态树静态树(static trees): 树结构与所要解决问题的实例树结构与所要解决问题的实例无关无关§动态树动态树(dynamic trees): 树结构是与实例相关的树结构是与实例相关的, 且且树结构是动态确定的树结构是动态确定的§活结点活结点: 自己已经生成而其所有的儿子结点还没有自己已经生成而其所有的儿子结点还没有全部生成的结点全部生成的结点§E-结点结点(正在扩展的结点正在扩展的结点): 当前正在生成其儿子结点当前正在生成其儿子结点的活结点的活结点§死结点死结点: 不再进一步扩展或者其儿子结点已全部生不再进一步扩展或者其儿子结点已全部生成的生成结点成的生成结点Ø解空间树解空间树(状态空间树状态空间树)的术语的术语Ø问题状态的生成问题状态的生成§第一种状态生成方法第一种状态生成方法: 当前的当前的E-结点结点R 一旦生成一一旦生成一个新的儿子结点个新的儿子结点C, 这个这个C结点就变成一个新的结点就变成一个新的E-结结点点, 当检测完了子树当检测完了子树C后后, R结点就再次成为结点就再次成为E-结点结点, 生成下一个儿子结点。

生成下一个儿子结点该方法也称为深度优先结点该方法也称为深度优先结点生成法生成法)§第二种状态生成方法第二种状态生成方法: 一个一个E-结点一直保持到变成结点一直保持到变成死结点为止它又分为两种方法死结点为止它又分为两种方法: 宽度优先生成方法宽度优先生成方法(队列方法队列方法)和和D-检索方法检索方法(栈方法栈方法)§第一种状态生成方法对应回溯法第一种状态生成方法对应回溯法 第二种状态生成方法对应分枝第二种状态生成方法对应分枝-限界法限界法§结点结点2变成变成E-结点结点, 它再生成结点它再生成结点3, 路路径变为径变为(1, 2), 即皇后即皇后1在第在第1列上列上, 皇后皇后2在第在第2列上列上, 所以结点所以结点3被杀死被杀死, 此时此时应回溯应回溯13x2= 22x1=1§开始把根结点作为唯一的活结点开始把根结点作为唯一的活结点, 根结点就成根结点就成为为E-结点而且路径为结点而且路径为( ); 接着生成儿子结点接着生成儿子结点, 假假定按自然数递增的次序来生成儿子定按自然数递增的次序来生成儿子, 那么结点那么结点2被生成被生成, 这条路径为这条路径为(1), 即把皇后即把皇后1放在第放在第1列上列上kill112例例: 4-皇后问题皇后问题8x2= 3§回溯到结点回溯到结点2生成结点生成结点8, 路径变为路径变为(1, 3), 则结点则结点8成为成为E-结点结点, 它生成结点它生成结点9和结点和结点11都会被杀死都会被杀死(即即它的儿子表示不可能导致答案的棋盘格局它的儿子表示不可能导致答案的棋盘格局), 所以结所以结点点8也被杀死也被杀死, 应回溯应回溯13x2= 22x1=1kill11x3=49x3=2112123killkill例例: 4-皇后问题皇后问题12313x2= 415x4=3§回溯到结点回溯到结点2生成结点生成结点13, 路径变为路径变为(1, 4), 结点结点13成为成为E-结点结点, 由于它的儿子表示的是由于它的儿子表示的是一些不可能导致答案结点的棋盘格局一些不可能导致答案结点的棋盘格局, 因此因此结点结点13也被杀死也被杀死, 应回溯应回溯8x2= 313x2= 22x1=1kill11x3=49x3=2killkill14x3=2kill112123412316x3=3kill例例: 4-皇后问题皇后问题18x1= 213x2= 415x4=313x2= 22x1=1kill11x3=49x3=2killkill8x2= 314x3=2kill16x3=3kill§结点结点2的所有儿子表示的都是不的所有儿子表示的都是不可能导致答案的棋盘格局可能导致答案的棋盘格局, 因此因此结点结点2也被杀死也被杀死; 再回溯到结点再回溯到结点1生成结点生成结点18, 路径变为路径变为(2)19x2= 124x2= 3killkill§结点结点18的儿子结点的儿子结点19、、结点结点24被杀死被杀死, 应回溯应回溯例例: 4-皇后问题皇后问题11212131x4=3§结点结点18生成结点生成结点29, 结点结点29成为成为E-结点结点, 路径变为路径变为(2,4);18x1= 213x2= 415x4=313x2= 22x1=1kill11x3=49x3=2killkill8x2= 314x3=2kill16x3=3kill19x2= 124x2= 3killkill121231234§结点结点29生成结点生成结点30, 路径变为路径变为(2,4,1)§结点结点30生成结点生成结点31, 路径变为路径变为(2,4,1,3), 找到一个找到一个4-皇后问皇后问题的可行解题的可行解29x2= 430x3=1可可行行解解1、针对所给问题定义问题的解空间、针对所给问题定义问题的解空间, 解空间应解空间应至少包含问题的一个最优解至少包含问题的一个最优解 2、确定易于搜索的解空间结构、确定易于搜索的解空间结构3、以深度优先方式搜索解空间、以深度优先方式搜索解空间, 并在搜索过程并在搜索过程中使用限界函数避免无效搜索中使用限界函数避免无效搜索Ø回溯算法的三个步骤回溯算法的三个步骤§从根结点出发从根结点出发, 以深度优先方式搜索整个解空间。

以深度优先方式搜索整个解空间§首先根结点成为一个活结点首先根结点成为一个活结点, 同时也成为当前的扩展同时也成为当前的扩展结点在当前扩展结点处在当前扩展结点处, 搜索向纵深方向移至一个新搜索向纵深方向移至一个新结点结点, 该新结点成为一个新的活结点该新结点成为一个新的活结点, 并成为当前扩展并成为当前扩展结点§如果在当前扩展结点处不能再向纵深方向移动如果在当前扩展结点处不能再向纵深方向移动, 则当则当前扩展结点就成为死结点此时应回溯至最近的一个前扩展结点就成为死结点此时应回溯至最近的一个活结点处活结点处, 并使该活结点成为当前的扩展结点并使该活结点成为当前的扩展结点§回溯法以这种方式递归地在解空间中搜索回溯法以这种方式递归地在解空间中搜索, 直至找到直至找到所要求的解或解空间中已没有活结点时为止所要求的解或解空间中已没有活结点时为止Ø回溯法搜索过程回溯法搜索过程24回溯算法的形式化描述回溯算法的形式化描述§假设回溯法要找出所有的答案结点；假设回溯法要找出所有的答案结点；§设设(x1, x2,, xi 1)是状态空间树中由根是状态空间树中由根到一个结点的路径；到一个结点的路径；§T(x1,, xi 1)是下述所有结点是下述所有结点xi的集合的集合，，它使得对于每一个它使得对于每一个xi，，(x1, x2,, xi)是一是一条由根到结点条由根到结点xi的路径；的路径；§假定存在一些假定存在一些限界函数限界函数Bi，如果路径，如果路径(x1, x2,, xi)不可能延伸到一个答案结不可能延伸到一个答案结点，则点，则Bi(x1, x2,, xi)取假值，否则取真取假值，否则取真值。

值§解向量解向量X(1:n)中的第中的第i个分量个分量就是那些就是那些选自集合选自集合T(x1, x2,, xi 1)且使且使Bi为真的为真的xi 131513211981416Ø回溯算法的形式化描述回溯算法的形式化描述procedure BACKTRACK(n)int k, n; local X(1: n);k=1;while (k>0) 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) ); k=k+1; } else k=k-1;}end BACKTRACK//回溯回溯//打印数组打印数组X//考虑下一个集合考虑下一个集合在在X(1)…X(k-1)已经被选定已经被选定的情况下的情况下, T(X(1)…X(k-1))给出给出X(k)的所有可能的取值的所有可能的取值,限界函数限界函数B(X(1)…X(k))判断判断哪些哪些X(k)满足隐式约束条件满足隐式约束条件procedure RBACKTRACK(k)global X(1:n); int k, n;for ( 满足下式的每个满足下式的每个X(k), X(k) ∈∈T(X(1)…X(k-1)) and B(X(1),…B(k))==true) do { if (X(1),…,X(k))是一条抵达答案结点的路径是一条抵达答案结点的路径 then print (X(1)…X(k)); call RBACKTRACK(k+1); }end RBACKTRACK Ø回溯算法的递归描述回溯算法的递归描述进入算法时进入算法时, 解向量解向量X中的中的前前k-1个分量个分量X(1) …X(k-1)已经被赋值已经被赋值对于所有可以由根结点对于所有可以由根结点到达到达, 并可能使限界函数并可能使限界函数B为真的结点为真的结点X(k), 判断判断(X(1)…X(k))是否是一条是否是一条能抵达答案结点的路径能抵达答案结点的路径27procedure BACKTRACK(n) int k, n; local X(1: n); k1; while (k 0) 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若只需要一个解若只需要一个解,怎样修改算法？怎样修改算法？131513211981416k 2k 3k 4Ø回溯法的效率估计回溯法的效率估计§回溯法的效率主要取决于四种因素回溯法的效率主要取决于四种因素:•生成下一个生成下一个X(k)的时间的时间•满足显式约束条件的满足显式约束条件的X(k)的数目的数目•限界函数限界函数Bi的计算时间的计算时间•对于所有的对于所有的i，满足，满足Bi的的X(k)的数目的数目§一旦选定了一种状态空间树结构一旦选定了一种状态空间树结构, 前三种因素对于前三种因素对于所要解决的实例没有多大的关系所要解决的实例没有多大的关系, 只有第四种因素只有第四种因素,对于问题的不同实例对于问题的不同实例, 生成的结点数是不相同的生成的结点数是不相同的29回溯法的效率估计n回溯法的效率主要取决于四种因素：生成下一个生成下一个X(k)的时间的时间满足显式约束条件的满足显式约束条件的X(k)的数目的数目限界函数限界函数Bi的计算时间的计算时间满足满足Bi的的X(k)的数目的数目n限界函数能够大大减少生成的结点数，但在计算时间和减少程度上要进行折中。

生成结点的时间生成结点的时间子结点的数量子结点的数量检验结点的时间检验结点的时间通过检验的结点数量通过检验的结点数量30一旦选定了一种状态空间树结构，前三种因素与所要解决问题的实例无关，只有第四种因素，对于问题的不同实例，生成的结点数是不相同的易知，回溯算法最坏情况下的时间复杂度为O(p(n)2n)或O(q(n)n)，其中p(n)和q(n)为n的多项式尽管回溯法对同一问题不同实例在计算时间上出现巨大差异，但在n很大时，对某些实例仍然十分有效用回溯算法处理一棵树所要生成的结点数，可以用蒙特卡罗方法估算出来效率估计31效率估计---估计满足Bi的X(k)的数目蒙特卡罗方法Ø在状态空间树中生成一条在状态空间树中生成一条随机路径随机路径Ø设设X是这条路径上是这条路径上第第i级级的一个结点的一个结点Ø在结点在结点X处处用限界函数确定用限界函数确定没受限界的儿子结点没受限界的儿子结点数目数目mi Ø在这在这mi个儿子结点中个儿子结点中随机选择随机选择一个作为下一个结一个作为下一个结点Ø这条路径在以下结点处结束：或者它是一个这条路径在以下结点处结束：或者它是一个叶子叶子结点结点，或者该结点的，或者该结点的所有儿子结点都已被限界所有儿子结点都已被限界。

Ø用这些用这些mi可以估算出这棵状态空间树中不受限界可以估算出这棵状态空间树中不受限界结点的总数结点的总数m不受限界结点的估计数不受限界结点的估计数m 1 m1 m1 m2 m1 m2 m3 ，， mi表示第表示第i级结点平均没受限界的儿子结点数级结点平均没受限界的儿子结点数32效率估计---估计满足Bi的X(k)的数目蒙特卡罗方法Ø优点：优点： 找到找到所有答案结点所有答案结点的情况非常有用，的情况非常有用， 限界函数固定不变限界函数固定不变，计算方便，对状态空间树，计算方便，对状态空间树中同一级结点都适用中同一级结点都适用Ø缺点：缺点： 只求只求一个解一个解时，生成的结点数远小于时，生成的结点数远小于m，， 随着检索的进行，限界函数应该更强，使得随着检索的进行，限界函数应该更强，使得m的值更小的值更小 33效率估计Procedure ESTIMATE //程序沿着状态空间树中一条随机路径产生这棵树中不受限界结点的估计数// m 1; r 1; k 1 loop Tk {X(k): X(k)  T(X(1), , X(k1) ) and Bk (X(1), , X(k1))} if SIZE(Tk)0 then exit endif r rSIZE(Tk) m mr X(k) CHOOSE(Tk) k k1 repeat return(m)end ESTIMATE//第第k级的结点数级的结点数//从从Tk中随机地挑选一个元素中随机地挑选一个元素//前第前第k级的结点总数级的结点总数8.2 8-皇后问题皇后问题Ø问题描述问题描述:在一个在一个8*8棋盘上放置棋盘上放置8个皇后个皇后, 使得每两个皇后之间使得每两个皇后之间都不能互相都不能互相“攻击攻击”, 即每两个皇后都不能在同一行、即每两个皇后都不能在同一行、同一列及同一条斜角线上同一列及同一条斜角线上Q1Q2Q3Q4Q5Q6Q7Q8Ø8皇后问题可以表示皇后问题可以表示为为8- -元组元组(x1, …, x8) ,其中其中xi是放置皇后是放置皇后i所所在的列号在的列号Ø图中的可行解表示为图中的可行解表示为一个一个8- -元组元组即即(4, 6, 8, 2, 7, 1, 3, 5)a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61a62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二维数组用二维数组A(1:8,1:8)的的下标来标记每个皇后的下标来标记每个皇后的位置，那么可以看到位置，那么可以看到: 对于在对于在由左到右由左到右的同一的同一条斜角线上的每个元素条斜角线上的每个元素具有具有相同的相同的“行行- -列列”值值;对于在对于在由右到左由右到左的同一的同一条斜角线上的每个元素条斜角线上的每个元素则具有则具有相同的相同的“行行+列列”值值设有两个皇后被放置在设有两个皇后被放置在(i, j )和和(k, l )位置上位置上, 那么当且仅当那么当且仅当 i–j = k- -l 或或 i+j = k+l 时时, 它们才在同一条斜角线上。

它们才在同一条斜角线上将这两个等式分别变换成将这两个等式分别变换成: j- -l = i- - k 或或 j- -l = k- - i因此当且仅当因此当且仅当 |j- -l| = |i- -k| 时时( 即两个皇后所在位置的行差距即两个皇后所在位置的行差距等于列差距时等于列差距时), 两个皇后在同一条斜角线上两个皇后在同一条斜角线上procedure PLACE(k)int i , k;i=1;while ( i0) do { X[k]=X[k]+1; while ( X[k]<=n and Not PLACE(k) ) do { X[k]=X[k]+1; } if (X[k]<=n) then { if (k==n) then print (X); else { k=k+1; X[k]=0; } } else k=k- -1; }end NQUEENS//若是一个完整的解则打印数组若是一个完整的解则打印数组X// k是当前行是当前行; X(k)是当前列是当前列 // 对所有的行执行循环语句对所有的行执行循环语句//移到下一列移到下一列当该位置不当该位置不能放皇后时能放皇后时转到下一列转到下一列//找到一个位置找到一个位置//否则转到下一行否则转到下一行// 没有合适的位置没有合适的位置, 回溯回溯1234X001Q1PLACE(1)i=1;while ( i0) do { X[k]=X[k]+1; while (X[k]<=n and Not PLACE(k)) do1<=n and Not true , 循环不执行循环不执行if (X[k]<=n) then if (k≠n) then 不执行不执行 else { k=k+1=2; X[2]=0; } } end whilek=2; while (k>0) do { X[k]=X[k]+1; while ( X[k]<=n and Not PLACE(k) ) do1<=n and Not false , X[k]=X[k]+1=2; 2<=n and Not false , X[k]=X[k]+1=3; 3<=n and Not true , 循环不执行循环不执行1 2 3if (X[k]<=n) then if (k≠n) then 不执行不执行 else { k=k+1=3; X[3]=0; } 0} end whileQ2PLACE(2)i=1;while ( i0) do { X[k]=X[k]+1; while (X[k]<=n and Not PLACE(k)) doif (X[k]≮ ≮n) then 不执行不执行 else k=k- -1=2; //回溯回溯 } end whilek=2; while (k>0) do { X[k]=X[k]+1=3+1=4; while ( X[k]<=n and Not PLACE(k) ) do1<=n and Not false , X[k]=X[k]+1=2; 2<=n and Not false , X[k]=X[k]+1=3; 4<=n and Not true , 循环不执行循环不执行if (X[k]<=n) then if (k≠n) then 不执行不执行 else { k=k+1=3; X[3]=0; } } end whileQ213<=n and Not false , X[k]=X[k]+1=4; 4<=n and Not false , X[k]=X[k]+1=5; 2 3 4 5405≮ ≮n , 循环不执行循环不执行40估算估算NQUEENS所生成结点数所生成结点数p硬性处理法：硬性处理法： C(64,8) 4.4 109pNQUEENS（不考虑限界函数（不考虑限界函数PLACE()时）时） 840320p考虑限界函数，估算结点数（蒙特卡罗方法）：考虑限界函数，估算结点数（蒙特卡罗方法）：ü假设使用固定的限界函数且在检索进行时函数不改假设使用固定的限界函数且在检索进行时函数不改变。

变ü在状态空间树的在状态空间树的同一级的所有结点都有相同的度同一级的所有结点都有相同的度静态的状态空间树结点个数为：静态的状态空间树结点个数为： 1 8 8 7 8 7 6  8 7 6 5 4 3 2 1 18(8 j) 1 (8 i) 69281j 07j 07i 0j4112345854321 8 8 5 8 5 4 8 5 4 3 8 5 4 3 2 164912345678642111 1401这这5次试验的平均值是次试验的平均值是1625不受限节点的估计数大约是不受限节点的估计数大约是8-皇后状态空间树的结点总数的皇后状态空间树的结点总数的1625 69281 2.348-皇后问题的不受限节点的估计值皇后问题的不受限节点的估计值m 1 m1 m1 m2 m1 m2 m3  8.3 子集和数问题子集和数问题Ø子集和数问题子集和数问题: 假定有假定有n个不同的正数个不同的正数, 要求找出这些要求找出这些数中所有使得某和数为数中所有使得某和数为M的组合的组合问题描述问题描述: 已知已知n+1个正数个正数: wi (1≤i≤n)和和M, 要求找出要求找出wi的和数是的和数是M的所有子集的所有子集Ø本节将利用大小固定的元组来研究一种回溯算法，本节将利用大小固定的元组来研究一种回溯算法，解决这一问题解决这一问题 例例: n=4 , (w1, w2, w3, w4 )=(7, 11, 13, 24) , M=31 满足要求的子集是满足要求的子集是(1, 1, 1, 0)和和(1, 0, 0, 1)Ø生成图中任一结点的儿子生成图中任一结点的儿子: 对于对于i级上的一个结点级上的一个结点, 其左儿子对应于其左儿子对应于X(i)=1, 右儿子对应于右儿子对应于X(i)=0Ø对于限界函数的一种简单选择是对于限界函数的一种简单选择是:当且仅当当且仅当∑W(i)X(i)+∑W(i)≥M 时时, B(X(1)…X(k))=truei=1ki=k+1nØ若若W(i)按升序排列按升序排列, 则限界函数可以被强化则限界函数可以被强化:1x1=1x1=023111612 13101415478956x2=1x3=1101010x2=0x3=0x3=1x3=01021171825192223 2420x2=1x2=0x3=1x3=01010……当且仅当当且仅当∑W(i)X(i)+∑W(i)≥Mi=1ki=k+1nB(X(1)…X(k))=true且且∑W(i)X(i)+W(k+1)≤M 时时i=1kprocedure SUMOFSUB(s, k, r)global float W(1:n); global int X(1:n); float r, s; int k, j;X[k]=1;if (s+W[k]==M) then { print(X[j], j=1 to k); print(X[j]=0, j=k+1 to n); return; }else if (s+W[k]+W[k+1]<=M) then call SUMOFSUB(s+W[k], k+1, r- -W[k]);if (s+r- -W[k]>=M and s+W[k+1]<=M) then { X[k]=0; call SUMOFSUB(s, k+1,r- -W[k]); }end SUMOFSUBØ子集和数问题的递归回溯算法子集和数问题的递归回溯算法//进入此过程时进入此过程时X(1)…X(k)的值已确定的值已确定; W(j)按非降次按非降次序排列序排列; 假定假定W(1)≤M, ∑W(i) ≥M (i=1…n); j=1j=kk- -1ns= ∑W(j)X(j) ; r = ∑W(j)//生成左儿子生成左儿子//若找到子集若找到子集, 则打印则打印// 否则当否则当Bk=true时时, 递归递归生成左儿子生成左儿子//当当Bk=true时递归生成右儿子时递归生成右儿子实例实例: n=6, M=30,W(1:n)=(5,10,12,13,15,18)j=1j=kk- -1ns= ∑W(j)X(j) ; r = ∑W(j)SUMOFSUB(s, k, r)开始调用时开始调用时 k=1, 由公式算出由公式算出s=0, r=73( 注注: 为书写简便将为书写简便将SUMOFSUB缩写为缩写为SB)①① SB(0, 1, 73) //s=0, k=1, r=73X[1]=1;if (s+W[k]==M) then0+5=5≠300+5+10=15<300+5=5,1+1=2,73-5=68等待执行的部分等待执行的部分:if (s+r- -W[k]>=M and s+W[k+1]<=M) then { X[k]=0; call SB(s, k+1, r- -W[k]); }end ①①SB 0, 1, 735, 2, 68X[1]=1不执行不执行else if (s+W[k]+W[k+1]<=M) thencall ②② SB(s+W[k], k+1, r- -W[k]);②② SB(5, 2, 68) //s=5, k=2, r=68X[2]=1;if (s+W[k]==M) then 5+10=15≠305+10+12=27<305+10=15,2+1=3,68-10=58等待执行的部分等待执行的部分:if (s+r- -W[k]>=M and s+W[k+1]<=M) then { X[k]=0; call SB(s, k+1,r- -W[k]); }end ②②SB 不执行不执行else if (s+W[k]+W[k+1]<=M) thencall ③③ SB(s+W[k], k+1, r- -W[k]);0, 1, 735, 2, 68X[1]=115, 3, 58X[2]=1else if (s+W[k]+W[k+1]<=M) then③③ SB(15, 3, 58) //s=15, k=3, r=58X[3]=1;if (s+W[k]==M) then 15+12=27≠3015+12+13=40>3015+58-12=61>30 and 15+13=28<30不执行不执行不执行不执行if (s+r- -W[k]>=M and s+W[k+1]<=M) then{ X[3]=0; call ④④ SB(s, k+1,r- -W[k]); }15, 3+1=4, 58-12=46end ③③SB15, 4, 46X[3]=0 0, 1, 735, 2, 68X[1]=115, 3, 58X[2]=1④④ SB(15, 4, 46) //s=15, k=4, r=46X[4]=1;if (s+W[k]==M) then 15+13=28≠3015+13+15=43>30不执行不执行else if (s+W[k]+W[k+1]<=M) then不执行不执行if (s+r- -W[k]>=M and s+W[k+1]<=M) then{ X[4]=0; call ⑤⑤ SB(s, k+1,r- -W[k]); }15, 4+1=5, 46-13=33end ④④SB15+46-13=48>30 and 15+15=30=300, 1, 735, 2, 68X[1]=115, 3, 58X[2]=115, 4, 46X[3]=0 15, 5, 33X[4]=0⑤⑤ SB(15, 3, 33) //s=15, k=5, r=33X[5]=1;if (s+W[k]==M) then 15+15=30==M{ for j=1 to k do print(X[j]); for j=k+1 to n do print(X[j]=0); return; }打印打印X=(1,1,0,0,1,0)end ⑤⑤SBX[5]=1A0, 1, 735, 2, 68X[1]=115, 3, 58X[2]=115, 4, 46X[3]=0 15, 5, 33X[4]=05, 3, 58X[2]=0 实例实例: n=6, M=30,W(1:n)=(5,10,12,13,15,18)从从⑤⑤ SB(15, 3, 33)返回到返回到④④ SB(15, 4, 46), 再返回到再返回到③③ SB(15, 3, 58), 最后返回到最后返回到②② SB(5, 2, 68),执行剩余的代码执行剩余的代码 ②② SB(5, 2, 68) //s=5, k=2, r=685+68-10=63>30 and 5+12=17<30if (s+r- -W[k]>=M and s+W[k+1]<=M) then{ X[2]=0; call ⑥⑥ SB(s, k+1,r- -W[k]); }5, 2+1=3, 68-10=58end ②②SB已经执行的部分已经执行的部分:X[2]=1;if (s+W[k]==M) thenelse if (s+W[k]+W[k+1]<=M) then call ③③ SB(s+W[k], k+1, r- -W[k]);X[5]=1A0, 1, 735, 2, 68X[1]=115, 3, 58X[2]=115, 4, 46X[3]=0 15, 5, 33X[4]=0else if (s+W[k]+W[k+1]<=M) then17, 4, 46X[3]=1⑥⑥ SB(5, 3, 58) //s=5, k=3, r=58X[3]=1;if (s+W[k]==M) then 5+12=17≠305+12+13=30=305+12=17,3+1=4,58-12=46等待执行的部分等待执行的部分:if (s+r- -W[k]>=M and s+W[k+1]<=M then { X[k]=0; call SB(s, k+1,r- -W[k]); }end ⑥⑥SB 不执行不执行call ⑦⑦ SB(s+W[k], k+1, r- -W[k]);0, 1, 735, 2, 68X[1]=115, 3, 58X[2]=115, 4, 46X[3]=0 15, 5, 33X[4]=0X[5]=1A5, 3, 58X[2]=0 X[4]=1B⑦⑦ SB(17, 4, 46) //s=17, k=4, r=46X[4]=1;if (s+W[k]==M) then 17+13=30==M打印打印X=(1,0,1,1,0,0)end ⑦⑦SB17, 4, 46X[3]=10, 1, 735, 2, 68X[1]=115, 3, 58X[2]=115, 4, 46X[3]=0 15, 5, 33X[4]=0X[5]=1A5, 3, 58X[2]=0 { for j=1 to k do print(X[j]); for j=k+1 to n do print(X[j]=0); return; }。