1、第8章 回溯法,回溯法概述,回溯法可以系统的搜索一个问题的所有解或任一个解它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索到某一结点时，如果断定该结点肯定不包含问题的解，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯这种以深度优先方式搜索问题的解的方法称为回溯法,可用回溯法求解的问题,问题的解可以用一个n元组(x1,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数P(x1,xn)（也称限界函数）取极值或满足该规范函数条件。例子：A(1:n)个元素的分类问题问题的解为n元组；xi取自有穷集；规范函数P：A(xi)=0 即s
2、i=所有非负实数xi=0或xi=1 即 si=0,1l=xi=u即si=a:l=a0 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,回溯算法的递归表示,procedure RBACKTRACK(k) global n, X(1:n) for 满足下式的每个X(k) X(k) T(X(1),X(k-1) and B(X
3、(1),X(k)=true do if(X(1),X(k) 是一条已抵达一答案结点的路径 then print(X(1),X(k) endif call RBACKTRACK(k+1) repeatend RBACKTRACK,算法说明：基本上是一棵树的后根次序周游。这个递归模型最初由call RABCKTRACK(1)调用。,6.28-皇后问题,将n个皇后放置在一个nn的棋盘上，要求没有两个皇后可以互相攻击。攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。,8-皇后问题的一个解,该解的8元组表示:(4,6,8,2,7,1,3,5),n-皇后问题,用n-元组(x1
4、,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将是截然不同。如果设想棋盘的方格像二位数组A(1:n,1:n)的下标那样标记，那
5、么可以看到，对于在同一条斜角线上的由左上方到右下方的每一个元素有相同的“行列”值，同样，在同一条斜角线上的由右上方到左下方的每一个元素则有相同的“行列”值。 假设有两个皇后被放置在(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(k)是否不同于前面X(1),X(k-1)的值以及在
6、同一个斜角线上是否根本就没有别的皇后。procedure PLACE(k)/如果一个皇后可以放在第k行和X(k)列，则返回true；否则返回false/ global X(1:k); integer 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 repeat if X(k) n /找到一个位置 then if k=n /是一个完整的解吗 then print (X) /是，打印这个数组 else k k+1 , X(k) 0
7、 /转到下一行 endif else k k-1 /回溯 endif repeatEnd NQUEENS,8-皇后问题算法分析, 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 当且仅当
8、j=1.k W(i)X(i)+j=k+1.n W(i)=M 且j=1.k W(i)X(i)+ W(k+1)=M,子集和数的递归回溯算法,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)14 if s+W(k)=M then5 print(X(j),j1 to k)6 else7 if s+
9、W(k)+W(k+1)=M and s+W(k+1)=M12 then X(k)013 call SUMOFSUB(s,k+1,r-W(k)14 endifend SUMOFSUB,SUMOFSUB的一个实例,n=6, M=30, W(1:6)=(5,10,12,13,15,18),8.4回溯法求解背包问题,问题描述求解0/1背包问题约束条件显式约束条件：xi=0/1隐式约束条件目标函数：maxxipi,问题的解：n元组表示（x1.xn）解空间大小2n为了进一步减少生成的状态结点的数量，设置限界函数杀死那些不能导致最优解的结点如何设置限界函数？,限界函数设置原则,如果扩展给定的活结点和它的任意
10、子孙结点所导致最好可行解的上界不大于迄今所确定的最好解，则杀死此活结点。最好可行解的上界？限界函数：若结点Z处已经确定了xi的值，1ik，则Z结点处的上界值可以这样获得：对其余物品k+1in，求一般背包问题贪心解作为上界。,proc Bound（p,w,k,M）/M背包容量，p当前效益值，w当前背包重/量，k上一个去掉的物品b=p;c=w;for i=1to n do c=c+w(i) ifcm then b=b+p(i) else return (b+(1-(c-m)/w(i)*p(i) endifrepeatreturn bendp,回溯算法执行一般步骤一路向左，直到第一个不能放入的物品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背包问题,
