回 溯 法.

Presentation on theme: "回 溯 法."— Presentation transcript:

1 回 溯 法

2 回溯法的直观印象 （1）回溯法有“通用的解题法”之称。用它可以系统地搜索一个问题的所有解或最优解。回溯法是一个既带系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发，搜索解空间树。 （2）算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统性搜索，逐层向其祖先结点回溯（称为剪枝）。否则，进入该子树，继续按深度优先的策略进行搜索。 （3）回溯法在用来求问题的所有解（或最优解？）时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而在求任一解时，只要搜索到一个解就结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适合于解一些组合数较大的问题。

3 主要内容 6.1 回溯法的算法框架 6.2 8-皇后问题 6.3 子集和数问题 6.4 图的m着色问题--? 6.5 哈密顿环问题--?
6.1 回溯法的算法框架 皇后问题 6.3 子集和数问题 6.4 图的m着色问题--? 6.5 哈密顿环问题--? 6.6 0/1货郎担问题

4 6.1 回溯法的算法框架 1.1 一般方法 回溯法的基本思路： 可用回溯法求解的问题P，通常 要能表达为：
6.1 回溯法的算法框架 1.1 一般方法 回溯法的基本思路： 可用回溯法求解的问题P，通常 要能表达为： 对已知的、由n元组 (x1，…，xn) 组成的状态空间E={(x1，…，xn)| xiSi,I=1,2,…n}， 给定关于n元组中的分量的一个约束集D，求满足D的全部约束条件的所有n元组。 Si 是 xi 的定义域且Si 是有穷集，称E中满足D的全部约束条件的所有n元组为问题P的解。

5 用回溯法求解的许多问题都要求所有的解满足一组综合的约束条件。对n元组(x1，…，xn)中的分量的约束，可分为两类：一类是显约束，一类是隐约束，显示约束条件是限定每个x只从一个给定的有限集合上取值。例如
xi≥ Si={所有非负实数} xi＝0或xi＝1 Si={0，1} li≤xi≤ui Si={a：li≤a≤ui } 隐式约束条件则规定解空间中那些实际上满足规范函数Bi(x1，…，xi)的元组。因此，隐式约束描述了xi必须彼此相关的情况。不过，显约束和隐约束不是绝对的。有时显约束可以表示成隐约束，隐约束也可以表示成显约束。

6 对于许多问题，所给定的约束集D具有完备性，即i元组 (x1，…，xi)满足D中仅涉及到x1，…，xi的所有约束意味着， j(j<i) 元组 (x1，…，xj) 也一定满足D。
换句话说，只要存在 l≤j≤n-1,使得(x1，…，xj) 违反了D，则以(x1，…，xj) 为前缀的任何n元组(x1，…，xj，…，xn) 也一定违反D。 回溯法利用这种完备性，所以回溯法是一个即带有系统性，有带有跳跃性的搜索方法。

7 6.1.2 问题的解空间 应用回溯法解问题时,首先应明确定义问题的解空间.问题的解空间应至少包含问题的一个(最优)解。
例如对于有n种物品的0/1背包问题，其解空间为长度为n的0-1向量组成。该解空间包含了对变量的所有可能的0-1赋值。当n=3时，其解空间(即满足显约束的所有n元组)是： {(0,0,0),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)} 定义了(求出)解空间后,还应将解空间很好地组织起来,使得回溯法能方便地搜索整个解空间。通常将解空间组织成树的形式。

8 解空间用树的形式组织 例如，对于n=3时0/1背包问题，其解空间用一棵完全二叉树表示。
解空间树的第i层到第i+1层边上标号 给出了变量的值。从树根到叶的任一路径表示解空间中的一个元素。如从根到H的路径表示解空间的元素(1,1,1) A B D H I E J K C F L M G N O 1

9 回溯法的基本思想 确定了解空间的组织结构后，回溯法从根结点出发，以深度优先的方式搜索解空间。这个开始结点称为一个活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点，这个新结点就成为活结点，并成为当前扩展结点。如果当前扩展结点不能再向下移动，则当前结点就成为死结点。此时，回溯至最近的一个活结点处，并使这个结点成为当前的扩展结点。直到回溯到根（或解空间中已无活结点），则找出了问题的解。 从根出发进行搜索，搜索到每个节点，先判断以该节点为根的子树是否肯定不包含问题的解，如果不包含，则跳过对该子树的搜索，一层一层向祖先节点回溯，直到遇上还未搜索过的子树，才搜索这棵子树。回溯到根节点时，则找出了问题的所有解。

10 例1：n=3时的0/1背包问题，考虑下面实例，W=[16,15,15], P=[45,25,25],M=30.
从下图的根结点开始搜索解空间： 首先，A点成为活结点，也是扩展结点，扩展到B，由B扩展到D,不能再扩展,使D成为死结点,回溯到最近的活结点B处,扩展到E(E成为活结点),再继续扩展到J处,不满足约束条件,成为死结点,返回E,扩展到K处,是一个可行解(效益值为45),往上回溯到E,E不再能扩展,成为死结点,回溯到B,B也成为死结点,再回溯到A,扩展到C,C成为活结点,且扩展到F,F成为活结点,扩展到L,…… A B D H I E J K C F L M G N O 1

11 解空间树的举例 例2 4-皇后问题的解空间树—P160 图6.2 (其中xi =k 表示第i行的皇后放在第i列)
很显然，其解空间包含4！=24个元素（4元组），这种树称为排列树。但只有部分是可行解。（满足约束条件）。 例3 子集和数问题的解空间树----P161 图6.4 (xi=1,表示xi 在子集中，xi=0表示不在子集中，这类似于0/1背包问题，只是它求可行解，而背包问题是求最优解）

12 应用回溯法求解的步骤 在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。其一是约束函数在扩展结点处剪去不满足约束的子树(如前面例子中的D和J）；其二是用限界函数剪去不能得到最优解的子树（如前面的M点和G点）。这两类函数统称为剪枝函数。 综上所述，应用回溯法求解通常包含以下三个步骤： （1）针对所给问题，定义问题的解空间。 （2）确定易于求解的解空间结构； （3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

13 回溯算法的形式描述 假设1：回溯法要找出所有可行解（即答案结点）而不是仅只一个解。
假设2: (x1,x2,…,x i-1)是解空间树中由根到一个结点的路径,而T(x1,x2,…,x i-1)是下述所有结点xi的集合,它使得对于每一个xi, (x1,x2,…,x i-1)是一条由根到结点xi 的路径. 假设3:一些限界函数Bi(约束函数),如果Bi (x1,x2,…,x i)为假, 表示路径(x1,x2,…,x i)不能延伸到一个答案结点(可行解)。反之，表示可能延伸，于是解向量X(1:n)中第i个分量就是那些选自集合T (x1,x2,…,x i-1) 且使Bi为真的xi

14 算法6.1 回溯法的形式描述： procedure BACAKTRACE(n) k =1 ; while (k>0) do if T (x1，x2，…， x k-1)的值还未取遍 then {xk = T (x1，x2，…， x k-1)中未取过的值； if Bk (x1，x2，…， x k) then { (x1，x2，…， x k)被激活； if k ==n then 输出(x1，x2，…， x n)； else k =k+1；} // 深度扩展搜索 } else k = k -1 // 试探完了所有的x k，回溯 end BACAKTRACE 设对于任意的 l≤ki≤n ，状态节点(x1，x2，…， x k-1)被激活以后，满足显约束的xk的全体即为Tk(x1，x2，…， x k-1)，而满足隐约束的xk当且仅当逻辑表达式Bk(x1，x2，…， x k)为真。

15 算法6.2 回溯法的一般方法递归形式描述： procedure RBACAKTRACE(k) if k 〉n then return ； else for x k  T (x1，x2，…， x k-1) and Bk(x1，x2，…， x k) do { if k ==n then 输出(x1，x2，…， x n)； RBACAKTRACE(k+1)；// 深度扩展搜索 } end BACAKTRACE n是全局变量，控制递归深度

16 6.2 n-皇后问题 用4元组(x1，…，x4)，i=1,2,3,4，表示问题的解，其中xi表示把第i个皇后放在第i行的第xi列。所以
即要求找出在一个n×n棋盘上放置n个皇后并使其不能互相攻击(不在同行同列、不在同斜角线上) 的所有方案。用n元组(x1， x2， …，xn)，为了方便，可以讨论n=4，即4皇后问题。 用4元组(x1，…，x4)，i=1,2,3,4，表示问题的解，其中xi表示把第i个皇后放在第i行的第xi列。所以 xi  Si ={1,2,3,4}，i=1,2,3,4。(显约束) 4皇后问题的状态空间E可以表示为 图6.2(P160)所示的状态空间树，在状态空间树上搜索的约束为： xixj ，i  j (即不在同一列) 且｜j－1 |  | i－k | ： (不在同斜角线上) (在同一对角线上,则两个元素有相同的“行+列”值,即如果一个在(I,k)位置,另一个在(k,l)位置,则当且仅当I+j=k+l, 即｜j－1 | = | i－k |,才在同一斜角线上)

17 考察4后问题的状态空间树可以发现有许多节点时可以不要搜索的，例如x1=1,x2=1的子树。因此，对于每个节点需要用判定函数（衔接函数）进行考察，不能使判定函数为真的节点就处死(使其变为死节点)。
4皇后问题的状态空间树

18 X1=4 X1=1 X1=2 X1=3 X2=3 X2=3 X2=4 X2=4 X2=1 X2=1 X3=3 X3=2 X3=1 X3=4 用过程PLACE(k) 测试待确定的第k皇后是否和前面已确定的k -1个皇后是否在同一条斜角线，第k个皇后只要与任一皇后在同一条斜角线，就返回false，当第k个皇后能放置于X(k)的当前值处时，这个返回值为真。 X4=2 X4=3 4皇后的部分状态空间树

19 算法6.4 测试X(K)是否合理 procedure PLACE(k) //如果一个皇后能放在第k行和X(k)列，则返 回true；否则返回false。X是一个全程数 组，进入此过程时已置了k个值。// 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←i+1 repeat return(true) //满足约束// end PLACE

20 算法6.5 n皇后问题的所有解 { X(k)←X(k)+1 //移到下一列//
procedure NQUEENS(n) //此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其能互相攻击的所有可能位置// X(1)←0；k←1 //k是当前行；X(k)是当前列// While k>0 do //对所有的行执行以下语句// { X(k)←X(k)+1 //移到下一列// While X(k)≤n and not PLACE(k) do {X(k)←X(k)十l;} // 如果第k个皇后的列X(k)不合理// if X(k)≤n //找到一个位置// then if k=n //是一个完整的解吗// then print(X) //是，打印这个数组// 3) else {k←k+1；X(k)←0；} endif //扩展，搜索下一个皇后// 4) else k←k－1 //回溯// endif 　 } end NQUEENS

21 X(1) = X(1) +1=2, PACE(k)=ture X(2) = 4 , PLACE(2)=ture
用算法6.5 解4皇后问题步骤如下： 1）X(1) = 1, PLACE(k)=ture k←k+1=2，X(2) = 0 X(2) = 3, PLACE(2)=ture k←k+1=3，X(3) = 0 直到X(3) = 5 没找到合适的位置 k←k－1=2 2） X(2) = 4, PLACE(2)=ture k←k+1=3，X(3) = 0 X(3) = 2, PLACE(3)=ture k←k+1=4，X(4) = 0 X(4) = 5 ， 没找到合适的位置 k←k－1=3 X(3) = 5 ， 没找到合适的位置 k←k－1=2， X(2) ←X(2) +1= 5, k←k－1=1 X(1) = X(1) +1=2, PACE(k)=ture X(2) = 4 , PLACE(2)=ture X(3) = 2, PLACE(3)=ture X(4) = 3 , PLACE(4)=ture

22 (1)如果用蛮力处理,即在8×8的棋盘上安排出8个位置, 这有 种安排法,逐一测试,即要检查将近4.4×109个8元组.
复杂度分析 (1)如果用蛮力处理,即在8×8的棋盘上安排出8个位置, 这有 种安排法,逐一测试,即要检查将近4.4×109个8元组. (2)用回溯法最多只要作8!次检查,即最多只要查40320个8-元组。 （3）应用限界函数，实际还少得多，对于8-皇后问题，不受限结点是8-皇后解空间树的结点总数的2.34% 因此,用回溯法处理比用枚举法好得多!

23 6.3 子集和数问题 问题：给定由n个不同的正整数的集合 W={wi| wi >0，i=1，2，…，n}
6.3 子集和数问题 问题：给定由n个不同的正整数的集合 W={wi| wi >0，i=1，2，…，n} 和正整数M，要求找出所有使得其中所有之和为M的子集S。 该问题的状态空间树是一棵高度为n的满二叉树，其中深度为k的一个状态节点对应着一个k元组 (x1，x2，…， x k)，根节点对应着空元组()。 ……….. ……… X(1)=1 X(1)=0 X(2)=1 X(2)=0

24 例如给定n = 4，W={11，13，24，7}，M = 31， 则相应的子集和数问题的解是(0,0,1,1), (1,1,0,1)。这种固定长度的解向量表示问题的解含义是很容易理解的： xi{0,1}，它表示S是否包含了wi。 约定: (x1,x2,…, x k-1,1) 和(x1，x2，…， x k-1，0) 所对应的状态节点分别是(x1，x2，…， x k-1) 所对应的状态节点的 左儿子和右儿子。对于i级上的一个结点，其左儿子对应于X(i)=1，右儿子对应于X(i)＝0。

25 子集和数问题的限界函数(约束函数) 1.为了提高搜索效率，又不失一般性，可以假定这些w(I)一开始就是按非降次序排列的，即有
0≤W(1) ≤W(2) ≤……≤ W(n)，且 2. (x1,x2,…,xk)能导致一个答案结点(可行解),即 限界函数 Bk(x1,x2,…,xk)=true 当且仅当

26 若记 设s<M，s+r≥M和s+W(K) ≤M。如果在这个假设下测试问题的解，那么(x1，x2，…， x k-1，1)很可能是问题的解，进入测试的第一件事就应该是检测(x1，x2，…， xk-1，1)是否为问题的解，如果是，则输出并回溯；如果不是，则分别测试以(x1，x2，…， x k-1，1)和(x1，x2，…， x k-1，0)为根的左子树和右子树。 s<M，s+r≥M和 s+W(K)≤M s+W(k)+W(k+1)≤M s+W(k+1)≤M 且 s+r-W(k) ≥ M Xk=1 Xk=0 在上述前提下，搜索左子树的条件是： s+W(k)+W(k+1)≤M 搜索右子树的条件是： s+W(k+1)≤M and s+r-W(k) ≥M

27 procedure SUMOFSUB(s，k，r)
算法5.5 子集和数问题的递归回溯算法 procedure SUMOFSUB(s，k，r) //找W(1：n)中和数为M的所有子集。进入此过程时X(1)，…，X(k－1)的值已确定，W(j)按非降次序排列。W(1)≤M 且 X(k)←1 if s+W(k)＝M then //子集找到// print //此处由于W(j)>0，1≤j≤n，因此不存在递归调用// else if s+W(k)+W(k+1)≤M then //Bk＝true// call SUMOFSUB(s+W(k)，k+1，r－W(k)) endif //生成右儿子和计算Bk的值// if s+r－W(k)≥M and s＋W(k+1)≤M //Bk＝true// then X(k)←0 call SUMOFSUB(s，k+1，r－W(k)) end SUMOFSUB

28 例n＝6，M＝30和W(1：6)＝(5，10，12，13，15，18)。 S=0,r=73 ,k=1
0,1,73 5,2,68 15,3,58 15,4,46 15,5,33 X(1)=1 X(2)=1 X(3)=0 X(4)=0 X(5)=1 5, 3,58 17,4,46 17, 5,33 (1,0,1,1) (1,1,0,0,1) 0,2,68 10,3,58 0,3,58 10,4,46 10,5,33 12,4,46 12,5,33 12,6,18 (0,0,1,0,0,1) ……. X(1)=0 0,4,46

29 6.4 图的m着色判定问题 问题描述: 已知一个图G和m种颜色，在只准使用这m种颜色对G的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢？这个问题称为m-着色判定问题。可对图G着色的最小正整数m，称为图G的色数。

30 图着色问题的现状 很早以前就已知道用5种颜色就中以为任何一个地图着色，（即用5种颜色可对连通平面图着色）。另一方面又一直没找到一个需要4种以上颜色才能着色的地图，由此引出了四色猜想（定理）。（1976依靠计算机得到证明） 我们将要研究的是一般的图，而不仅是平面图。

31 解空间结构 1.设一个图有n个顶点，给定一个图和m种颜色，如果这个图不是m可着色的，就给出否定的回答，否则，要找出所有不同的着色方案。
2.颜色用整数1,2,…,m表示,解用n元组(x1,x2,…,xn)表示,xi是结点I的颜色,所以解空间用树表示为一棵完全m元的树,树高为n+1。 3.例P171 图6.11 (n=3,m=3时的状态空间树(解空间树)

32 找一个图的所有m-着色方案算法 前提:图用邻接矩阵GRAPH(1:n,1:n)表示,若邻接,则为true, 否则为false.
Procedure Mcoloring(k) Global integer m,n,X(1:n) ,boolean GRAPH(1:n,1:n) Integer k Loop call NEXTVALUE(k) if x(k)=0 then exit endif //第k点无法着色,说明这个图无法着色. if k=n then print (X) else call Mcoloring(k+1) //第k点能着色,考虑下一个点,递归调用 endif repeat End Mcoloring 从call Mcoloring(1)开始执行。X赋初值0

33 生成下一种颜色的算法 算法6.7 生成下一种颜色 Procedure NEXTVALUE(k)
Global integer m,n,X(1:n),boolean GRAPH(1:n,1:n) Loop x(k)=(x(k)+1)mod (m+1) if x(k)=0 then return endif //表示m种都试过,不行! for j=1 to n do if GRAPH(k,j) and x(k)=x(j) then exit endif //退出FOR循环 Repeat If j=n+1 then return endif //表示第k点可着色返回x(k) end

34 复杂度分析 由于解空间树的内结点数有： 且在每个内部结点，为了确定其儿子结点的合法着色，要花费Ｏ(mn) 的时间（过程NEXTVALUE）。所以，总的复杂度为：

35 6.5 哈密顿环

36

37 0/1背包问题 在第四章中,我们用动态规划的方法讨论了背包问题。这里，我们将用回溯的方法求解背包问题。
问题的解空间：由各分量 xi(取值0或1）的2n个不同的n元向量组成。与子集和数问题的解空间相同。也用树结构表示（满二叉树）。 限界函数：取能产生某些值的上界函数。如果扩展给定活结点和它的任一子孙所导致最好可行解的上界不大于迄今所确定的最好解的值，就可杀死此活结点。

38 上界函数的取法 如果在Z点处已确定了xi的值，1≤i≤k,则Z的上界可这样取:
对k+1≤i≤n,将xi=0或1改为: 0≤xi≤1,假定物品已按单位重量的效益值降序排序。用前面用到的贪习方法求背包问题求取上界值。

39 限界函数（用贪心方法求取上界值） Procedure BOUND(p,w,k,M)
Global n,P(1:n),W(1:n);integer k,i;real b,c,p,w,M b=p; c=w; For i=k+1 to n do c=c+W(i) if c<M then b=b+P(i) else return b+(1-(c-M)/W(i))*P(i) // 把背包装满则返回 endif Repeat Return (b) End Bound

40 关于限界函数的几点说明 由算法BOUND可知，状态空间树中结点Z的可行左儿子的上界与Z的上界是一样的。
因此，在向左儿子移动时，不需调用限界函数。 每次扩展时，最好首先试左儿子，（因无需调用限界函数） 在一系列的左儿子移动之后（直到不能再移），需要移向右儿子时，才需调用限界函数。

41 0/1背包问题的回溯法求解 Procedure BKNAP1(M,n,W,P,fw,fp,X) // fw:背包最后重量fp:背包取得的最大效益。 Integer n,k,Y(1:n);real M,W(1:n),P(1:n),fw,fp,cw,cp; cw=0;cp=0;k=1;fp=-1 // cw：背包当前重量，cp:当前效益 Loop while k≤n and cw+W(k) ≤M Do cw=cw+W(k);cp=cp+P(k);Y(k)=1;k=k+1; repeat if k>n then fp=cp;fw=cw;k=n;X=Y //修改解// else Y(k)= // cw+W(k) >M ,超出M，不装物品K end if While BOUND(cp,cw,k,M) ≤fp do //移向右儿子，调用BOUND while k≠0 and Y(k) ≠1 do k=k-1 If k=0 then return endif Y(k)=0;cw=cw-W(k);cp=cp-P(k) Repeat K=k+1 End BKNAP1

42 例1：n=3时的0/1背包问题，考虑下面实例，W=[16,15,15], P=[45,25,25],M=30. 从下图的根结点开始搜索解空间：
A B D H I E J K C F L M G N O 1 从A出发，移向B，从B点移向D点（左儿子），但不满足约束条件，立即杀死D；转向右儿子E，调用BOUND，继续移向J点，由于不满足约束条件，立即杀死J点，移向右儿子K点，满足约束条件，且K=n,记录值；修改fp ,回溯，直到（k=1),移向C（即Y(k)=0),(执行15行))。调用BOUND后， 移向左儿子F（满足约束条件），再到L，也满足约束条件，放入背包，是解，记录值，修改fp。移向M，调用BOUND，杀死M，向上回溯，移向G，调用BOUND，立即杀死G，向上回溯，直到A点（k=0)结束。

43 回溯法小结 回溯法要求问题P的状态能表达为n元组(x1，…，xn)，要求xiSi，i=1,2,…n， Si是一个有穷集，对于给定关于n元组中的分量的一个约束集D，满足D 的全部约束条件的所有n元组为问题P的解。 从k=1开始构造k元组，如果k元组满足约束，k=k+1，扩展搜索；如果试探了X(k)的所有值，仍不能满足约束，则k=k-1,回溯到上一层重新选择X(k-1)的值。这种扩展回溯的搜索方法可以表示为状态空间树上的带约束条件的深度优先的搜索。