第六章 回溯法.ppt

1、第六章 回溯法,什么是回溯法,回溯法有“通用的解题法”之称。 应用回溯法解问题时，首先应该明确问题的解空间。 一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。 解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标达到最优的可行解称为该问题的最优解。,什么是回溯法,例：迷宫游戏,6.1 一般方法,什么是回溯法： 问题的解可以用一个n元组(x1,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数P(x1,xn)

2、取极值。 假设集合Si的大小是mi，于是就有m= m1 m2 mn个n-元组可能满足函数P。 所谓硬性处理就是构造出这m个n-元组并逐一测试它们是否满足函数P，从而找出该问题的所有最优解。,6.1 一般方法,回溯法的基本思想：不断地用修改过的规范函数Pi(x1,xi)去测试正在构造的n元组的部分向量(x1,xi) ，看是否可能导致最优解。 如果判定(x1,xi)不能导致最优解，那么就将可能要测试的mi+1mn个向量略去。 因此回溯法的测试次数比硬性处理作的测试次数要少得多。,6.1 一般方法,回溯法的解需要满足一组综合的约束条件，通常分为：显式约束和隐式约束 显式约束条件限定每个x只从一个给定

3、的集合上取值，例如： xi=0 即si=所有非负实数 xi=0或xi=1 即 si=0,1 l=xi=u即si=a:l=a=u 满足显式约束的所有元组确定的一个可能的解空间。 隐式约束描述了xi必须彼此相关的情况。,6.1 一般方法,例：8皇后问题 在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。 8皇后问题可以表示为8-元组(x1,x8) ，其中xi是放置皇后i所在的列号。 显式约束条件是si=1,2,3,4,5,6,7,8, 1i8 隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。,1 2

4、3 4 5 6 7 8,1 2 3 4 5 6 7 8,由于解向量之间不能相同，所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即（4，6，8，2，7，1，3，5）。,6.1 一般方法,子集和数问题：已知n+1个正数，wi 1in和M。要求找出wi的和数是M的所有子集。 例如，若n=4 , (w1, w2, w3, w4 )=(11,13,24,7) , M=31 ,则满足要求的子集是（11，13，7）和（24，7）。 如果通过给出其和数为M的那些wi的下标来表示解向量比直接用这些wi表示解向量更为方便。因此这两个解就由向量（1，2，4）和（3，4）所描述。,子集和数

5、问题,显式约束条件要求xij|j是wi的下标值，1jn。 隐式约束条件则要求没有两个xi是相同的且相应的wi和数等于M。 为了避免产生同一个子集的重复情况（例如：(1,2,4)和(1,4,2)表示同一个子集），附加另一个隐式约束条件：xixi+1 ，1jn。,子集和数问题,子集和数问题的另一种列式表示是，每一个解的子集由这样一个n-元组(x1,xn)所表示，它使得xi0,1,1in。如果没有选择wi，则xi=0；否则xi=1。 于是上例的解可以表示为(1,1,0,1)和(0,0,1,1)。 这种列式表示使用大小固定的元组表示所有的解。 一个问题的解可以有多种表示形式，而这些表示形式都使得所有的

6、解是满足某些约束条件的多元组。,6.1 一般方法,回溯法是一个既带有系统性又带有跳跃性的的搜索算法。 它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。 算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。,什么是回溯法,回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。 回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。 回溯法是以深度优先的方式系统地搜索问题的解的算法，它适用

7、于解一些组合数较大的问题。,状态空间树,4-皇后问题的状态空间树（图6.2） 树的边由xi的可能值所标记。 由1级到2级结点的边给出x1的值。 最左子树包含着x1=1的所有解；这棵子树的最左子树则包含着x1=1且x2=2的所有解。 由i级到i+1级的边用xi的值标记。 解空间则由从根结点到叶结点的所有路径所定义。,状态空间树,子集和数问题的状态空间树 图6.3和图6.4显示了在n=4的情况下两种表示的树结构形式。 图6.3所示的树对应于元组大小可变的列式表示，树边的标记方式是，由i级到i+1级的一条边用xi来表示，在每一个结点处，解空间被分成一些子解空间，解空间则由树中的根结点到任何结点的所有

8、路径所确定。 最左子树确定了包含w1的所有子集，下一棵子树则确定了包含w2但不包含w1的所有子集。,状态空间树,图6.4所示的树对应于元组大小固定的列式表示。由i级到i+1级结点的那些边用xi的值来标记，xi的值为或者为1或者为0。 由根到叶结点的所有路径确定了这个解空间，根的左子树确定包含w1的所有子集，而根的右子树则确定不包含w1的所有子集。 有24个叶结点，所以表示有16个可能的元组。,状态空间树,几个概念： 问题状态(problem state)：树中的每一个结点确定所求解问题的一个问题状态。 状态空间(state space)：由根结点到其他结点的所有路径则确定了这个问题的状态空间。

9、 解状态(solution states)：是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。在图6.3中所有的结点都是解状态，而图6.4中只有叶结点才是解状态。 答案状态(answer states)：是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解。,状态空间树,静态树(static trees)：树结构与所要解决的问题的实例无关。 动态树(dynamic trees)：根据不同的实例而使用不同的树结构。 活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点（正在扩展的结点）：当前正在生成其儿子结点的活结

10、点。 死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。,问题状态的生成,解决问题可采用两种不同的方法： 1、问题状态的深度优先生成(回溯法)：当前的E-结点R 一旦生成一个新的儿子结点C，这个儿子结点就变成一个新的E-结点，当检测完了子树C后，R结点就再次成为E-结点，生成下一个儿子结点。 2、分枝-限界法：一个E-结点一直保持到变成死结点为止。,例： 4-皇后问题,如果(x1,xi)是到当前E-结点的路径，那么具有父-子标记xi+1的所有儿子结点是一些这样的结点，它们使得(x1,xi+1)表示没有两个皇后正在相互攻击的一种棋盘格局。 开始把根结点作为唯一的活结点。这个根结点就成为E

11、-结点而且路径为（）。接着生成儿子结点，如果假定按自然数递增的次序来生成儿子，那么结点2被生成，这条路径为（1）。 这相当于把皇后1放在第1列上。结点2变成E-结点，生成结点3，但立即被杀死。,4-皇后问题解空间的树结构（图6.2）中，结点2生成结点3，路径变为（1，2），此时皇后1放在第1列上，若皇后2在第2列上，则皇后2立即被杀死。,回溯到结点2生成结点8，路径变为（1，3），则结点8成为E-结点，由于它的儿子表示的是一些不可能导致答案结点的棋盘格局，因此结点8也被杀死。,再回溯到结点2生成结点13，路径变为（1，4），则结点13成为E-结点，由于它的儿子表示的是一些不可能导致答案结点的棋

12、盘格局，因此结点13也被杀死。,现在结点2的所有儿子表示的都是一些不可能导致答案的棋盘格局，因此结点2也被杀死。再回溯到结点1生成结点18，路径变为（2）。 结点18的儿子结点19、24立即被杀死，所以只能将皇后2放在第4列上。由结点18生成结点29，结点29成为E-结点, 路径变为（2,4）。结点29生成儿子结点30, 路径变为（2,4,1），结点30再生成儿子结点31,路径变为（2,4,1,3），从而找到了一个4-皇后问题的可行解。,回溯法的算法,算法的三个步骤： 针对所给问题，定义问题的解空间； 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。

13、 确定易于搜索的解空间结构； 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；,回溯法的基本思想,确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。 在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。,回溯法的基本思想,如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。 回溯法即以这种工作方

14、式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。,算法的实现,假设回溯法要找出所有的答案结点 。 设(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,算法,Procedure BACKTRACK(k) global

15、 X(1:n); integer 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) end if call BACKTRACK(k+1) repeat End BACKTRACK,对于所有可以由根结点到达，并可能使界限函数B为真的结点X(k) ，判断X(1),X(k)是否是一条已抵达一答案结点的路径,6.2 8-皇后问题,8-皇后问题实际上很容易一般化为n-皇后问题，即要求找出一个n*n棋盘上放置n个皇后并使其不

16、能互相攻击的所有方案。 令(x1,x2,xn)表示一个解，由于没有两个皇后可以放入同一列，因此所有的xi将是互不相同的。 那么关键是应如何去测试两个皇后是否在同一条斜角线上呢？,6.2 8-皇后问题,如果用二维数组A(1:n,1:n)的下标来标记每个皇后的位置，那么可以看到，对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的“行-列”值，同样，在同一条斜角线上的由右上方到左下方的每一个元素则有相同的“行+列”值。,6.2 8-皇后问题,假设有两个皇后被放置在(i，j)和(k，l)位置上，那么根据以上所述，仅当 i j = k - l 或 i + j = k + l 时，它们才在同一条斜

17、角线上。 将这两个等式分别变换成 j - l = i - k 或 j - l = k - i 因此，当且仅当 |j- l| = |i-k| 时（即两个皇后所在位置的行差距等于列差距时），两个皇后在同一条斜角线上。,算法6.4：可以放置一个新皇后吗？,Procedure PLACE(k) /如果一个皇后能放在第k行和X(k)列，则返回true，否则返回false。X是一个全程数组，进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/ global X(1:k); integer i,k; i1 while ik do if X(i)=X(k) or ABS(X(i)-X(k)=ABS(i

18、-k) then return (false) end if ii+1 repeat return (true) End PLACE,判断是否有其它的皇后与之在同一列或同一斜对角线上,算法6.5：n-皇后问题的所有解,Procedure NQUEENS(n) /此过程使用回溯法求出一个n*n棋盘上放置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)

19、do /此处能放这个皇后吗/ X(k)X(k)+1 /不能放则转到下一列/ repeat if X(k)=n then /找到一个位置/ if k=n then print (X) /是一个完整的解则打印这个数组/ else kk+1;X(k)0 /否则转到下一行/ end if else kk-1 /回溯/ end if repeat End NQUEENS,6.3 子集和数问题,假定有n个不同的正数，要求找出这些数中所有使得某和数为M的组合。 前面已经说明了如何用大小固定或变化的元组来表示这个问题。本节将利用大小固定的元组来研究一种回溯解法，解决这一问题。 对于i级上的一个结点，其左儿子对

20、应于X(i) =1，右儿子对应于X(i) =0。,6.3 子集和数问题,限界函数 当且仅当W(i)X(i) (i=1 to k) +W(i) (i=k+1 to n) =M 时，B(X(1),X(2),X(k)=True 当W(i)以递增次序排列，则界限函数可强化： 若W(i)X(i) (i=1 to k) + W(k+1) M，则X(1),X(2),X(k)就不能导致一个答案结点。 因此将要使用的界限函数是： Bk(X(1),X(2),X(k)=True 当且仅当 W(i)X(i) (i=1 to k) +W(i) (i=k+1 to n) =M 并且 W(i)X(i) (i=1 to k)

21、 + W(k+1) = M,算法6.6：子集和数问题的递归算法,Procedure SUMOFSUB(s,k,r) /找W(1:n)中的和数为M的所有子集。进入此过程时X(1),X(2),X(k)的值已确定。S= W(j)X(j) (j=1 to k-1)且r = W(j) (j=k to n) 。这些W(j)按非降次序排列。假定W(1)=M (i=1 to n) / global integer M,n;global real W(1:n);global boolean X(1:n) real r,s;integer k,j; /生成左儿子。注意由于Bk-1=true, 因此s+W(k)0,

22、1=j=n,因此不存在递归调用/,算法6.6：子集和数问题的递归算法,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,6.4 图的着色,已知一个图G和m0种颜色，在只准使用这m种颜色对G的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢？ 这个问题称为m-着色判定问题。 在m着色最优化问题则是求可对图G着色的最小整数m。这个整数称为图G的色数。,6.4 图的着色,对于图着色的研究是从m-可着色性问题的

23、著名特例四色问题开始的。四色问题要求证明平面或球面上的任何地图的所有区域都至多可用四种颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。 四色问题可以转换成对一平面图的4-着色判定问题。 将地图的每一个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。下面的图6.10显示了一幅有5个区域的地图以及与该地图相应的平面图。,图6.10 一幅地图和它的平面表示,多年来虽然已经证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。 直到1976年这个问题才由科学家利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。 我们所考虑的不只是

24、由地图产生的图，而是所有的图。讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同的方法。,6.4 图的着色,假定用图的邻接矩阵GRAPH(1:n,1:n)来表示一个图G，其中若(i,j)是G的一条边，则GRAPH (i,j)=true，否则GRAPH (i,j)=false。 因为要拟制的算法只关心一条边是否存在，所以使用布尔值。颜色用整数1,2,m表示，解用n-元组X(1),X(2),X(n)来给出。其中X(i)是结点i 的颜色。,6.4 图的着色,算法MCOLORING使用的基本状态空间树是一棵度数为m，高为n+1的树。在i 级上的每一个结点有m个儿子，它们与X(i)的m种可能的赋值相对应，1=i=n。在n+1级上的结点都是叶结点。 下面的图给出了n=3,m=3时的状态空间树。,6.4 图的着色,算法6.7 找一个图的所有m-着色方案 Procedure MCOLORING(k) /这是图着色的一个递归回溯算法。图G用它的布尔邻接矩阵GRAPH(1:n,1:n)表示。/ /它计算并打印出符合以下要求的全部解，把整数1,2,m分配给图中/ /各个结点且使相邻近的结点的有不同的整数。K是下一个要着色结点的下标/ Global