N皇后问题 回溯法

1、回溯Backtracking,回溯 N皇后问题 跳马问题 迷宫问题 图的着色问题 0-1背包问题 装载问题 批处理作业调度 填数问题 组合输出问题 算24点问题 ACM应用,学习要点,掌握回溯的概念 掌握经典问题的回溯解决方法 掌握回溯与其它方法的异同,有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题

2、的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,回溯法,回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。,算法思想： 采用了一种“走不通就掉头”的思想。搜索时往往有多分支，按某一分支为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。,回溯法,回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。,

3、回溯法,搜索的方式 主要采用深度优先搜索的方式,回溯三要素： 1) 解空间：该空包含问题的解 2) 约束条件 3) 状态树,问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。,n=3时的0-1背包问题用完全二叉树表示的解空间,生成问题状态的基本方法,扩展结点:一个正在产生

4、儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点 死结点:一个所有儿子已经产生的结点称做死结点 深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在） 宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度

5、优先生成法称为回溯法,回溯法的基本思想,(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。,递归回溯,回溯法对解空间作深度

6、优先搜索，因此，在一般情况下用递归方法实现回溯法。,void backtrack (int t) if (tn) output(x); else for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,迭代回溯,采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。,void iterativeBacktrack () int t=1; while (t0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,在一个n

7、*n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上。 输出N，求N皇后问题的一种放法； 求N皇后问题的所有放法,分析： N=4时，右图是一组解,要素一： 解空间,一般想法：利用二维数组，用i,j确定一个皇后位置！,优化：利用约束条件，只需一维数组即可！ x:array1.n of integer; xi：i表示第i行皇后 xi表示第i行上皇后放第几列,x3,1,4,2,N皇后问题,要素二：约束条件,不同行：数组x的下标保证不重复 不同列：xixj (ij) 不同对角线：,abs(xi-xj)abs(i-j),要素三：状态树,将搜索

8、过程中的每个状态用树的形式表示出来！ 画出状态树对书写程序有很大帮助！,填到第K行时，就与前1(K-1)行都进行比较,Function Place(k:integer):boolean; place:=true; for j1 to k-1 do if |k-j|=|xj-xk| or xj=xk then place:= false,N皇后问题,K=0,K=1,*,*,*,*,*,*,*,*,*,*,*,*,*,*,回溯,*,*,*,*,*,*,*,*,*,*,回溯,*,*,*,*,*,*,*,*,*,*,*,K=3,K=2,K=4,*,*,*,*,出解后可以继续刚才的做法,过程：进入新一行

9、，该行上按顺序逐个格子尝试，直到能放为止（不冲突、不越界）,算法描述： 产生一种新放法 冲突，继续找，直到找到不冲突-不超范围 if 不冲突 then knk+1 k=n一组解 if 冲突 then 回溯,N皇后问题,回溯部份： 即状态恢复，使其恢复到进入该分支前的状态，继续新的分支 xk:=0; Dec(k);,程序结束条件： 一组解：设标志，找到一解后更改标志，以标志做为结束循环的条件所有解：k=0,程序实现： 回溯算法可用非递归和递归两种方法实现！,判断约束函数,Function Place(k:integer):boolean; place:=true; for j1 to k-1 d

10、o if |k-j|=|xj-xk| or xj=xk then place:= false,N皇后问题,Nqueens() begin x1 0 k 1 while k0 do begin xk xk +1 while xk=n and (not place(k) do xk xk +1 if xk=n then if k=n then sum sum+1 else begin k k+1 xk 0 end else k k-1 end end,非递归写法：,if k=n then print;flag false,算法描述： 产生一种新放法 冲突，继续找，直到找到不冲突-不超范围 if 不

11、冲突 then knk+1 k=n一组解 if 冲突 then 回溯,Flag true,While flag do,N皇后问题,procedure try(k:byte); var i:byte; begin for i:=1 to n do每层均有n种放法 if place(k) then 寻找放置皇后的位置 begin xk:=i; 放置皇后) if k=n then print 个皇后都放置好,输出 若只想找一组解，halt else try(k+1);继续递归放置下一个皇后 end; end;,递归写法：,分析：状态恢复（回溯）在什么地方实现？,N皇后问题,在nm棋盘上有一中国象棋中

12、的马： 马走日字； 马只能往右走。 请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。 输入：9 5 输出：(1,1)-(3,2)-(5,1)-(6,3)-(7,1)-(8,3)-(9,5),跳马问题,分析： 按题意，马每一步可以有4种走法！,搜索过程： 当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。,当到达A1点后，又有三条线路可以 选择，于是再任意选择一条，到达B1。 从B1再出发，又有两条线路可以选择，先选一条，到达C1。,跳马问题,4. 从C1出发，可以有三条路径，选择

13、D1。但到了D1以后，我们无路可走且D1也不是最终目标点，因此，选择D1是错误的，我们退回C1重新选择D2。同样D2也是错误的。再回到C1选择D3。D3只可以到E1，但E1也是错误的。返回D3后，没有其他选择，说明D3也是错误的，再回到C1。此时C1不再有其他选择，故C1也是错误的，退回B1，选择C2进行尝试。,5. 从C2出发，有四条路径可以选择，选择D4，从D4出发又有两条路径，选择E1错误，返回D4选择E2，从E2出发有两条路径，先选择F1错误，返回E2选择B，而B恰好是我们要到达的目标点，至此，一条路径查找成功。,跳马问题,从上面的分析我们可以得知： 在无法确定走哪条线路的时候，任选一

14、条线路进行尝试；为方便路径表示，对马可以走到的四个点（方向）都编上号； 当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试。,解空间: 为了描述路径，我们最直接的方法就是记录路径上所有点的坐标。,优化：每一个方向上两个坐标和原位置对应关系,若马所处的位置为(x,y)，则其下一步可以到达的四个位置分别是(x+1, y-2)，(x+2, y-1)，(x+2, y+1)，(x+1, y+2)。,增量数组：dx = (1, 2, 2, 1)dy = (-2, -1, 1, 2),方向t，下一步的位置就是(x+dxt, y+dyt)。

15、,x,y,path:array1.m of integer; 其中，pathi：表示第i个节点所走的方向,跳马问题,约束条件：,不越界： (x + dxi 0) and (y + dyi = n),状态树：,算法描述： 产生一种新走法 越界，继续用新走法，直到找到一种走法不越界-不超过4种走法 if 不越界 then knk+1 k=n一组解 if 越界 then 回溯,跳马问题,Horse() begin path1 0，k 1，x 1，y 1 while (xm) and (yn) do begin pathk pathk +1 while (x + dxi 0) and (y + dyi

16、 m) and (yn) then print else begin k k+1 pathk 0 end end else pathk 0，k k-1 end end,跳马问题（非递归）,跳马问题,跳马问题（递归）,跳马问题,procedure search(k: integer); / 递归查找 begin for i := 1 to 4 do / 依次尝试四个方向 if (x + dxi 0) and (y + dyi = n) then / 在棋盘上 begin pathk := i; / 记录下当前方向 x := x + dxi; y := y + dyi; / 修改扩展节点坐标 if

17、 (x = n) and (y = m) then / 是否是目标点 begin output(k); halt; / 是目标点，输出结果并终止程序 end else search(k+1); / 不是目标点，继续尝试下一步 / 扩展出的点是死点，回溯 x := x - dxi; y := y - dyi; / 恢复扩展节点坐标，状态恢复 end; end;,Begin read(n,m); x:=1; y:=1; search(1); End.,思考:,1. 在本例中，我们只要求输出一条可行路径，如果我们需要输出所有的可行路径，怎样改动此程序呢？ 2. 如果我们把问题改成“在nm的棋盘上有一

18、骑士，开始时，骑士在点(x,y)，现在请你找出一条可行的路径，使得骑士可以不重复的走遍棋盘上的每一个点。”的话，又要如何编写此程序呢？,跳马问题,设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角，迷宫格子中分别放有0和1，0表示可走，1表示不能走，迷宫走的规则如图。当迷宫给出之后，找出一条从入口到出口的通路。 输入：N N*N的迷宫 输出：具体路径,输入样例： 8,输出样例： (1,1)-(2,1)-(3,1)-(2,2)-(1,3)-(2,4)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1),迷宫问题,x,y,分析：,增量和方向表示 dx=(1,1

19、,-1,-1,1,-1,0,0) dy=(-1,0,1,0,1,-1,1,-1),path:array1.maxn*maxn of integer; 其中，pathi：表示第i个节点所走的方向,解空间,约束条件,不越界且该点可走 (x=1) and (x=1) and (y=N) and Ax,y=1,迷宫信息用二维数组表示 A:array1.maxn,1.maxn of 0.1; 入口（1,1）；出口（n,1）,状态树,迷宫问题,给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题

20、。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。,图的着色问题,有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出一种符合条件的填色方案。,图的存储 R:array1.n,1.n of 0.1; 其中，RI,j =0-省i和省j不相邻 =1-省i和省j相邻,将实际地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的。,四色问题,图的着色问题,解

21、向量：(x1, x2, , xn)表示顶点i所着颜色xi 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。,void Color:Backtrack(int t) if (tn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k) / 检查颜色可用性 for (int j=1;j=n;j+) if (akj=1) ,图的着色问题,算法思想：,从编号1的省开始，按4种颜色的排列顺序，首先选

22、择第一种颜色，然后检查是否矛盾，即相邻的区域中是否已有该颜色，若不矛盾，则涂色，若矛盾，则选择下一个颜色，再判断，当4种颜色都不可能时，则需回溯。 当第一个省的颜色确定之后，依次对第二个省、第三个省进行处理，当所有省都涂上颜色之后，得到一种解法。,color:array1.maxn of integer; 其中，colork：表示第k个省所填的颜色,解空间,Color(1,2,1,3,1,3,4),迷宫问题,Function pd(k:integer):boolean; Var m:integer; Begin m:=1; 从第一个省份开始检查是否冲突 pd:=true; 不冲突 while

23、(m colorm) do inc(m); if k=m then pd:=false; 冲突 End;,约束条件,该点k涂的颜色(colork)与和k相邻的点m(1=m=k-1)的颜色(colorm)相同 colork * gm, k =colorm,状态树,迷宫问题,procedure search(k: integer); 递归搜索第m个省份 begin if k n then 是否所有省份都已经填色 begin write(color1); 已全部填色，输出结果，终止程序 for j := 2 to n do write( , colorj); writeln; halt end el

24、se 还未全部填色 for j := 1 to 4 do begin 依次用四种颜色对当前省份填色 if (k = n) and pd(k) then 没有冲突 begin colork := j; 记录当前省份颜色 search(k + 1); 递归检查下一个省份 end; end; end;,四色问题（递归）,迷宫问题,输入：第一行一个整数，为背包的容量M；第二行一个整数，为物品的种数；第三行个整数为各物品的重量；第四行个整数分别为个物品的价值 输出：第一行为最大总价值；第二行为装入的各物品的重量（未装的物品用）；第三行为装入的各物品的价值 （未装的物品用）,已知一个容量大小为M重量的背包

25、和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大,输入样例：50310 20 3060 100 120输出样例：2200 20 300 100 120,测试数据：输入：1052 2 6 5 46 3 5 4 6输出：?,0-1背包问题,bag:array1.maxn of 0.1; 其中，bagk=1表示第k个物品要取 0表示第k个物品不取,解空间,约束条件,第k个物品确定放置方法后，背包所剩重量足够放第K个物品,wei-bagk*wk=0wei：背包还能装的重量,Best:=0; 表示最大价值 当一组解产生后，得到当前总价值count， if

26、countbest then best:=count 利用这种方法记录最优解！如果还要记录最优时的物品取法应： if countbest then begin best:=count; for i:=1 to n do yi:=bagi;,状态树,求最优值,0-1背包问题,本题可以用递归求解：,本题可用方法很多！非递归写法与前几题相似，请自己写出！,算法分析：,设当前有N个物品，容量为M； 这些物品要么选，要么不选，我们假设选的第一个物品编号为i（1i-1号物品不选），问题又可以转化为有N-I个物品（即第I+1N号物品），容量为M-Wi的子问题如此反复下去，然后在所有可行解中选一个效益最大的便

27、可。,回溯（状态恢复）后，需恢复的状态有：,Bagk 背包可装的物品重量：wei:=wei+wk*i 已装物品的价值总和：count:=count:-ck*i,0-1背包问题,procedure work(k,wei:integer); var i,j:integer; begin for i:=1 downto 0 do if (wei-wk*i=0) then begin bagk:=i; count:=count+ck*i; if (k=n) and (countbest) then begin best:=count; for j:=1 to n do yj:=bagj; end; i

28、f kn then work(k+1,wei-wk*i); count:=count-ck*i; 状态恢复 end; end;,(k),(k,wei,count),work(k+1) wei:=wei+wk*i,work(k+1,wei-wk)*i,count),0-1背包（递归）,wei:=wei-wk*i,0-1背包问题,有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将

29、第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。,用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。,装载问题,解空间：子集树 可行性约束函数(选择当前元素)： 上界函数(不选择当前元素)： 当前载重量cw+剩余集装箱的重量r当前最优载重量bestw,void backtrack (int i) / 搜索第i层结点 if (i n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi

30、; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; ,装载问题,给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。,这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成

31、时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。,批处理作业问题,解空间：排列树,void Flowshop:Backtrack(int i) if (i n) for (int j = 1; j f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; ,class Flowshop friend Flow(int*, int, int ); private: void Backtrack(

32、int i); int *M, / 各作业所需的处理时间 *x, / 当前作业调度 *bestx, / 当前最优作业调度 *f2, / 机器2完成处理时间 f1, / 机器1完成处理时间 f, / 完成时间和 bestf, / 当前最优值 n; / 作业数;,批处理作业问题,【问题描述】 从整数1到10中任取9个不同的数，填入下面的9个格子中，使所有相邻（左、右、上、下）两个格子中的数的和是素数。 【输出】 一行3个数，共3行。 【样例】 1 2 5 4 3 8 7 10 9 【说明】 输出所有本质不同的解。（通过某个解的旋转、上下翻转、左右翻转得到的是本质相同的）,填数问题,【问题描述】 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且rn)，我们可以简单地将n个元素理解为自然数1，2，n，从中任取r个数。 现要求你不用递归的方法输出所有组合。 例如n5，r3，所有组合为： 1 2 3 1 2 4 1