1、第8章 回溯法,回溯法概述,回溯法可以系统的搜索一个问题的所有解或任一个解 它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索到某一结点时，如果断定该结点肯定不包含问题的解，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯 这种以深度优先方式搜索问题的解的方法称为回溯法,可用回溯法求解的问题,问题的解可以用一个n元组(x1,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数P(x1,xn)（也称限界函数）取极值或满足该规范函数条件。 例子：A(1:n)个元素的分类问题 问题的解为n元组； xi取自有穷集； 规范函数P：A(xi
2、)=A(xi+1),问题求解的方法,硬性处理法 列出所有候选解，逐个检查是否为所需要的解 理论上，候选解数量有限，并且通过检查所有或部分候选解能够得到所需解时，上述方法可行 实际中则很少使用，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模较小的问题。 回溯或分枝限界法 避免对很大的候选解集合进行完全检查 大大减少问题的求解时间 通常用来求解规模较大的问题,回溯法思想,第一步：为问题定义一个状态空间(state space)，这个空间必须至少包含问题的一个解 第二步：组织状态空间以便它能被容易地搜索。典型的组织方法是图或树 第三步：按深度优先的方法
3、从开始结点进行搜索 开始结点是一个活结点（也是 E-结点：expansion node） 如果能从当前的E-结点移动到一个新结点，那么这个新结点将变成一个活结点和新的E-结点，旧的E-结点仍是一个活结点。 如果不能移到一个新结点，当前的E-结点就“死”了（即不再是一个活结点），那么便只能返回到最近被考察的活结点（回溯），这个活结点变成了新的E-结点。 当我们已经找到了答案或者回溯尽了所有的活结点时，搜索过程结束。,回溯法如何提高效率？,由开始结点到当前E-结点构成解向量(x1,xi) 如果判定(x1,xi)不能导致最优解，那么就将可能要测试的mi+1mn个向量略去。 因此回溯法的测试次数比硬性
4、处理作的测试次数要少得多。如何判定(x1,xi)能否导致最优解？,约束条件,回溯法的解需要满足一组综合的约束条件，通常分为：显式约束和隐式约束 显式约束条件限定每个xi只从一个给定的集合上取值，例如： xi=0 即si=所有非负实数 xi=0或xi=1 即 si=0,1 l=xi=u 即si=a:l=a=u 满足显式约束的所有元组确定一个可能的解空间 隐式约束描述了xi必须彼此相关的情况，如0/1背包问题中的背包重量M,回溯法求解的经典问题（1） 8-皇后问题,在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。 8皇后问
5、题的解可以表示为8-元组(x1,x8) ，其中其中xi是第i行皇后所在的列号。 显式约束条件是xi=1,2,3,4,5,6,7,8, 1i8 隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。,1 2 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）。,回溯法求解的经典问题（2） 子集和数问题,已知(w1, w2, , wn)和M，均为正数。要求找出wi的和数等于M的所有子集。例如：若n=4,(w1,w2,w3,w4)=(11,13
6、,24,7),M=31，则满足要求的子集是(11,13,7)和(24,7). 子集和数问题解的一种表示方法 若用Wi的下标表示解向量，这两个解向量为(1,2,4)和(3,4)。 子集和数问题的解可以表示为k-元组(x1, x2, , xk), 1kn并且不同的解可以是大小不同的元组。 显式约束条件是xij|j为整数且1jn。 隐式约束条件是 1)没有两个xi是相同的; 2)wxi的和为M; 3)xixi1,1in（避免产生同一个子集的重复情况）,子集和数问题解的另一种表达,解由n-元组(x1, x2, , xn)表示; 显式约束条件xi0,1 ，1in，如果没有选择Wi，则xi=0；如果选择了
7、Wi，则xi=1。于是上面的解可以表示为(1，1，0，1)和(0,0,1,1); 隐式约束条件(xi wi)的和数为M解空间的大小为2n个元组,解空间的树结构,回溯算法通过系统地检索给定问题的解空间来确定问题的解。这检索可以用这个解空间的树结构来简化。 为了便于讨论，引进一些关于解空间树结构的术语。 问题状态(problem state)：树中的每一个结点确定所求解问题的一个问题状态。 状态空间(state space)：由根结点到其它节点的所有路径则确定了这个问题的状态空间。 解状态(solution states)：解状态是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解
8、空间中的一个元组。 答案状态(answer states)：对于这些解状态而言，由根到S的这条路径确定了这问题的一个解(即，它满足隐式约束条件)。 状态空间树(state space tree)：解空间的树结构。,静态树：树结构与所求问题的实例无关，结构不变的解空间树动态树： 树结构是动态变化的，与所求问题有关。即，具体问题的数据发生变化，空间树的结构也会发生变化。 组织空间树就是根据元组的特点构造解空间,组织解空间（1）,4-皇后问题解空间的树结构(解空间由从根结点到叶结点的所有路径所定义),n-皇后问题的状态空间树？,组织解空间（2）,子集和数问题,解空间由树中的根结点到任何结点的所有路径
9、所确定，这些可能的路径是( )(这对应于由根结点到他自身的那条路径)；(1)；(1,2)；(1,2,3)；(1,2,3,4)；(1,2,4)；(1,3,4)；(1,4)；(2)；(2,3)等等,组织解空间（3）,子集和数问题,解空间由根结点到叶结点的所有路径确定,状态空间树,对于任何一个问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些是解状态，最后确定哪些解状态是答案状态从而将问题解出 生成问题状态的两种方法便于问题的描述，给出以下概念： 活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点（正在扩展的结点）：当前正在生成其儿子结点
10、的活结点。 死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。,生成问题状态的两种方法,在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当于问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到变成死结点为止。在这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。回溯法：使用限界函数的深度优先结点生成方法。 分枝-限界方法：E-结点一直保持到死为止的状态生成方法。,4-皇后问题-回溯解,1 2 3 4,1234,4-皇后问题回溯期间生成的树,上图显示了在4
11、-皇后问题中求上述一个解的树的实际生成部分。结点按它们生成的次序被编号。由限界函数所杀死的结点则在其下方写上B。,回溯算法的形式描述,假设回溯算法要找出所有的答案结点而不是仅仅只找出一个。 设(x1,x2,xi-1)是状态空间树中由根到一个结点(问题状态)的路径。 T(x1,x2,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)且使B
12、i为真的xi。,回溯的一般方法算法,procedure BACKTRACK(n)integer k, n; local X(1:n)k1while k0 doif 还剩有没检验过的X(k)使得X(k) T(X(1),X(k-1) and B(X(1),X(k)=truethenif(X(1),X(k) 是一条已抵达一答案结点的路径then print(X(1),X(k) endifk k+1elsek k-1endifrepeat end BACKTRACK,回溯算法的递归表示,procedure RBACKTRACK(k)global n, X(1:n)for 满足下式的每个X(k)X(k)
13、 T(X(1),X(k-1) and B(X(1),X(k)=true doif(X(1),X(k) 是一条已抵达一答案结点的路径then print(X(1),X(k) endifcall RBACKTRACK(k+1) repeat end RBACKTRACK,算法说明：基本上是一棵树的后根次序周游。这个递归模型最初由call RABCKTRACK(1)调用。,6.2 8-皇后问题,将n个皇后放置在一个nn的棋盘上，要求没有两个皇后可以互相攻击。攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。,8-皇后问题的一个解,该解的8元组表示: (4,6,8,2,7,
14、1,3,5),n-皇后问题,用n-元组(x1,x2,xn)表示棋盘上皇后的位置状态 下标表示皇后i (i=1,2,n) xi表示放置皇后i所在的列号 显式约束条件：每个xi只从集合Si=1,2,n取值 满足显式约束的所有元组确定一个可能的解空间 解空间由nn个n-元组组成 隐式约束条件 没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上 由前者得，所有解都是n-元组(1,2,n)的置换，因此，解空间缩小为 n！个元组,测试两个皇后在一条斜角线的方法,令(x1,xn)表示一个解，其中Xi是把第i个皇后放在第i行的列数。由于没有两个皇后可以放入同一列，因此这所有的Xi将是截然不同。如果设想棋
15、盘的方格像二位数组A(1:n,1:n)的下标那样标记，那么可以看到，对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的“行列”值，同样，在同一条斜角线上的由右上方到左下方的每一个元素则有相同的“行列”值。假设有两个皇后被放置在(i, j)和(k, l)位置上，那么根据以上所述，仅当i j = k - l 或 i + j = k + l时，它们才在同一条斜角线上。将这两个等式分别变换成j l = i - k 和 j l = k - i 因此，当且仅当| j l | = | i k |时，两个皇后在同一条斜角线上。,8-皇后问题检测放置新皇后的算法,过程PLACE(k)测试两种情况，即X(
16、k)是否不同于前面 X(1),X(k-1)的值以及在同一个斜角线上是否根本就没有别 的皇后。 procedure PLACE(k) /如果一个皇后可以放在第k行和X(k)列，则返回true；否则返回false/global X(1:k); integer i ,ki 1while ik doif X(i)=X(k)/在同一列有两个皇后or ABS(X(i)-X(k)=ABS(i-k)/在同一条斜角线上then return (false)i i + 1repeatreturn (true) End PLACE,8-皇后问题求解算法,过程NQUEENS求n-皇后问题的所有解 procedure
17、NQUEENS(n)integer k, n, X(1:n)X(1) 0; k 1 /K是当前行；X(k)是当前列while k0 do /对所有的行执行一下语句X(k) X(k)+1 /移到下一列while X(k) n and not PLACE(k) do /此处能放这个皇后吗X(k) X(k)+1repeatif X(k) n /找到一个位置then if k=n /是一个完整的解吗then print (X) /是，打印这个数组else k k+1 , X(k) 0 /转到下一行endifelse k k-1 /回溯endifrepeat End NQUEENS,8-皇后问题算法分析
18、, NQUEENS优于硬性处理 硬性处理：要求88的棋盘排出8块位置，有 种可能的方式。即要检查 将近4.4109个8-元组。 NQUEENS回溯法：只允许把皇后放置在不同的行和列上，至多需要作8！次检查，即至多只检查40320个8-元组。,64,8,6.3 子集和数问题,已知n个不同的正数(w1, w2, , wn)，通常称为权。要求找出wi的和数等于某个正数M的所有子集。 元组为大小固定 限界函数如下(W(i)按非降次排列）Bk(X(1),X(k)= true 当且仅当j=1k W(i)X(i)+j=k+1n W(i)=M 且 j=1k W(i)X(i)+ W(k+1)=M,子集和数的递归
19、回溯算法,procedure SUMOFSUB(s,k,r) /找W（1：n）中和数为M的所有子集。进入此过程时X(1),X(k-1)的值已确定。W(j)按非降次序排列。/ 1 global integer M,n; global real W(1:n); global boolean X(1:n) real r,s; integer k,j/生成左儿子/ 3 X(k)1 4 if s+W(k)=M then 5 print(X(j),j1 to k) 6 else 7 if s+W(k)+W(k+1)=M and s+W(k+1)=M 12 then X(k)0 13 call SUMOFS
20、UB(s,k+1,r-W(k) 14 endif end SUMOFSUB,SUMOFSUB的一个实例,n=6, M=30, W(1:6)=(5,10,12,13,15,18),8.4回溯法求解背包问题,问题描述 求解0/1背包问题 约束条件 显式约束条件：xi=0/1 隐式约束条件 目标函数：maxxipi,问题的解：n元组表示（x1xn） 解空间大小2n 为了进一步减少生成的状态结点的数量，设置限界函数杀死那些不能导致最优解的结点 如何设置限界函数？,限界函数设置原则,如果扩展给定的活结点和它的任意子孙结点所导致最好可行解的上界不大于迄今所确定的最好解，则杀死此活结点。 最好可行解的上界？
21、 限界函数：若结点Z处已经确定了xi的值，1ik，则Z结点处的上界值可以这样获得： 对其余物品k+1in，求一般背包问题贪心解作为上界。,proc Bound（p,w,k,M） /M背包容量，p当前效益值，w当前背包重/量，k上一个去掉的物品 b=p;c=w; for i=1to n doc=c+w(i)ifcm then b=b+p(i)else return (b+(1-(c-m)/w(i)*p(i)endif repeat return b endp,回溯算法执行一般步骤 一路向左，直到第一个不能放入的物品yk=0 调用上界函数与当前最优值比较， 小于当前最优解，杀死该结点，向上回溯 大于当前最优解，继续扩展其子孙结点,P=(11,21,31,33,43,53,55,65) w=(1 ,11,21,23,33,43,45,55) M=110,n=8 求解0/1背包问题,
