递归回溯搜索

1、递归回溯搜索,几个简单的递归例题,例1，N!。N!=N*(N-1)!，因此求N!转化为求 (N-1)!。这就是一个递归的描述。,因此，可以编写如下递归程序： program Factorial; var N: Integer; T: Longint; function Fac(N: Integer): Longint; begin if N = 0 then Fac := 1 else Fac := N * Fac(N - 1) end; begin Write(N = ); Readln(N); T := Fac(N); Writeln(N! = ,T); end.,例2：裴波那契数列的定义

2、：,对应的递归程序为 function fib(n: Integer): Integer; begin if n = 0 then fib := 1 递归边界 else if n = 1 then fib := 2递归边界 else fib := fib(n 2) + fib(n 1);递归 end;,例3：汉诺塔问题：有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。输出总共移动的次数。,A,B,C,分析：在移动盘子的过程当中发现要搬动n个盘子，

3、必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。,program hannuota; var n:integer; procedure hnt(a,b,c,n:integer); begin if n=1 then writeln(a,-,c) else begin hnt(a,c,b,n-1);writeln(a,-,c);hnt(b,a,c,n-1);end; end; begin write(please input n:); read(n); h

4、nt(1,2,3,n); end.,汉诺塔问题的递推解法,设f(n)为n 个盘子从1柱移到3柱所需移动的最少盘次。当n=1时，f(1)=1。 当n=2时，f(2)=3。 以此类推，当1柱上有n(n2)个盘子时，我们可以利用下列步骤： 第一步：先借助3柱把1柱上面的n-1个盘子移动到2柱上，所需的移动次数为f(n-1)。 第二步：然后再把1柱最下面的一个盘子移动到3柱上，只需要1次盘子。 第三步：再借助1柱把2柱上的n-1个盘子移动到3上，所需的移动次数为f(n-1)。,由以上3步得出总共移动盘子的次数为：f(n-1)+1+ f(n-1)。 所以：f(n)=2 f(n-1)+1 现在就可以用递推

5、做了 f(1)=1 f(2)=3 f(3)=7 f(4)=15,f(n)= 2n-1,现在可以用数学方法做了,回溯法的基本思想为：在按某种搜索策略的搜索过程中，在某种状态，继续往前搜索已经确定不会得到正确答案的情况下，我们可以返回上一搜索状态，去沿新的可能性继续搜索。要回溯到上一状态，则说明我们在前进中的状态必须保存下来，我们采用“栈”来存放。,回溯与dfs的关系 在我们的实际生活和信息学奥赛当中很多问题是不能用数学公式去解决的，解决问题的过程，往往是通过一系列的步骤，在每一步中根据条件的不同，又有多种可能性，为了达到问题最终的要求，在解决过程中需要遵循某种控制策略。对于此类问题，我们往往采用

6、搜索的方法来解决，而我们要研究的回溯法就是搜索的控制策略之一。,回溯法的特点为： 1.搜索策略：符合递归算法，问题解决可以化为子问题，算法类似，规模减小。 2.控制策略：当遇到失败的搜索状态，需要返回上一状态，沿另外的路径搜索。 3.数据结构：用数组保存搜索过程中的状态、路径。,算法框架： 1针对所给问题，定义问题的解空间； 2确定易于搜索的解空间结构； 3以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法 。,参考结构： procedure try(i:integer); var b

7、egin if in then 输出结果 else for j:=下界 to 上界 do begin xi:=hj; if 可行满足限界函数和约束条件 then begin 置值；try(i+1); 取消置值；end; end; end;,说明： i是递归深度； n是深度控制，即解空间树的的高度； 可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；,搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式

8、的搜索。 回溯即是较简单、较常用的搜索策略。,基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,xi），in,则添加x(i+1)属于s(i+1)，检查(x1,x2,xi,x(i+1)是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,x(i-1)，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。,例4：N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。,八皇后的

9、两组解,分析： 由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。,下面是放置第I个皇后的的递归算法： Procedure Try(I:integer)； 搜索第I行皇后的位置 var j:integer; begin if I=n+1 then 输出方案； for j:=1 to n do if 皇后能放在第I行第J列的位置 then begin 放置第I个皇后； 对放置皇后的位置进行标记； Try（I+1） 对放置皇后的位置

10、释放标记； End; End;,N皇后问题的递归算法的程序如下： program N_Queens; const MaxN = 100;最多皇后数 var A:array 1.MaxN of Boolean; 同列-竖线被控制标记 B:array 2.MaxN * 2 of Boolean;i+j和相等-左下到右上斜线被控制标记 C:array 1MaxN.MaxN1 of Boolean;j-i差相等-左上到右下斜线被控制标记 X: array 1 . MaxN of Integer; 记录皇后的解 Total: Longint;解的总数 N: Integer;皇后个数 procedure

11、Out;输出方案 var I: Integer; begin Inc(Total); Write(Total: 3, :); for I := 1 to N do Write(XI: 3); Writeln; end;,procedure Try(I: Integer); 搜索第I个皇后的可行位置 var J: Integer; begin if I = N + 1 then Out; N个皇后都放置完毕，则输出解 for J := 1 to N do if AJ and BJ + I and CJ I then begin XI := J; AJ := False; BJ + I := Fa

12、lse; CJ I := False; Try(I + 1);搜索下一皇后的位置 AJ := True; BJ + I := True; CJ I := True; end; end;,begin Write(Queens Numbers = ); Readln(N); FillChar(A, Sizeof(A), True); FillChar(B, Sizeof(B), True); FillChar(C, Sizeof(C), True); Try(1); Writeln(Total = , Total); end.,上机练习题 1.添加自然数问题。（add.pas） 要求找出具有下列性

13、质的数的个数(包含输入的自然数n)： 先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理: . 不作任何处理; . 在它的左边加上一个自然数,但该自然数不能超过原数的一半; . 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 输入文件：add.in,一行，n的值。 输出文件：add.out，一行，按照规则可产生的自然数个数。,样例： 输入文件： 6 满足条件的数为 6 16 26 126 36 136 输出文件 6,var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x

14、0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) end end; begin readln(n); s:=0; qiu(n); writeln(s) end.,2. 跳马问题。（jump.pas） 在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。 输出文件：jump.out，一行，路径条数。,program jump; var h:array-1.7,-1.7 of integer; a,b:array1.8 of integer; i,j,num:int

15、eger; procedure print; var i,j:integer; begin num:=num+1; if num=5 then begin for i:=1 to 5 do begin for j:=1 to 5 do write(hi,j:4); writeln; end; writeln; end; end;,procedure try(x,y,i:integer); var j,u,v:integer; begin for j:=1 to 8 do begin u:=x+aj; v:=y+bj; if hu,v=0 then begin hu,v:=i; if i25 t

16、hen try(u,v,i+1) else print; hu,v:=0 end; end; end;,begin for i:=-1 to 7 do for j:=-1 to 7 do if (i=1)and(i=1)and(j=5) then hi,j:=0 else hi,j:=1; a1:=2;b1:=1; a2:=1;b2:=2; a3:=-1;b3:=2; a4:=-2;b4:=1; a5:=-2;b5:=-1; a6:=-1;b6:=-2; a7:=1;b7:=-2; a8:=2;b8:=-1; num:=0; h1,1:=1; try(1,1,2); writeln(num);

17、 end.,深度优先搜索 在信息学奥赛中，有的试题能在有限的时间内，用简明的数学模型揭示问题的本质，对于这类问题我们尽量用解析法求解；但也有些问题，很难建立数学模型，对于这类问题，我们只能采用模拟或搜索求解，尽管搜索的复杂度一般都是指数级的，但在缺乏解决问题的有效模型时，搜索却是一种最行之有效的解决问题的办法，而且在用搜索解决问题时，在实现过程中存在很大的优化空间，在信息学奥赛中考察搜索算法，除了考察选手的算法运用能力，更重要的是考察选手的算法优化能力，下面我们将介绍一些常用的搜索策略。,一：枚举策略（见枚举算法讲义）二：深度优先搜索。三：宽度优先搜索。,二：深度优先搜索,1.算法思想 深度优

18、先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止。,2.深度优先搜索的基本算法结构 （1）递归实现。 Procedure dfs_try(i); For i:=1 to maxr do begin if 子结点mr符合条件 then begin 产生的子结点mr入栈； if子结点mr是目标结点 then 输出； else dfs_try(i+1); 栈顶元素出栈； End; End;,非递归实现

19、Procedure dfs(dep); Dep:=0; Repeat dep:=dep+1; J:=0;p:=false; repeat j:=J+1; if mr 符合条件 then begin 产生子结点并将其记录； if 子结点mr是目标结点 then 输出并出栈； else p:=true; End,Else if j=maxj then begin dep:=dep-1; if dep0 then 取回栈顶元素； else p:=true; End else p:=false; Until p=true Until dep=0;,例3、问题描述 迷宫问题 设有一个N*N方格的迷宫，入

20、口和出口分别在左上角和右上角。迷宫格子中分别放有0和1，0表示可通，1表示不能，迷宫走的规则如下图所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可通过，要另找路径。 输入例子：（从文件中读取数据） 8 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 输出要求：找出一条 从入口（左上角）到出口（右上角）的路径(不能重复)。 (1,1)-(2,1)-(3,1)

21、-(2,2)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1),分析: a:array1.maxn,1.maxnof 0.1; 记录迷宫坐标 c:array1.maxn,1.maxnof 0.1; 访问标志:0:没走;1:已走 b:array0.maxn*maxn of integer;记录路径方向 dx,dy:array1.8of integer; 方向位移,8个方向的位移: dx1:=0; dy1:=-1; dx2:=1; dy2:=-1; dx3:=1; dy3:=0; dx4:=1; dy4:=1; dx5:=0; dy5:=1; dx6:=-1; d

22、y6:=1; dx7:=-1; dy7:=0; dx8:=-1; dy8:=-1;,读入数据: 坐标 procedure readdata; begin assign(input,a.in); reset(input); readln(n); for i:=1 to n do for j:=1 to n do begin read(aj,i);i:纵坐标;j:横坐标 cj,i:=0; end; close(input);,递归算法: procedure try(i:integer);搜索第i步应到达的位置 var k:integer; begin for k:=1 to 8 do begin

23、if (x+dxk=1)and(x+dxk=1)and(y+dyk=n)and (ax+dxk,y+dyk=0)and(cx+dxk,y+dyk=0) then begin x:=x+dxk; y:=y+dyk; cx,y:=1; bi:=k; if (x=n)and(y=1) then begin print(i); halt; end else try(i+1); cx,y:=0; x:=x-dxk; y:=y-dyk; end; end; end;,输出一组解: procedure print(i:integer); var j:integer; begin x:=1; y:=1; wr

24、ite(,x,y,); 初始位置 for j:=1 to i do 输出路线 begin x:=x+dxbj; y:=y+dybj; write(-,(,x,y,); end; writeln; end;,主程序: begin readdata; x:=1; y:=1; try(1); end.,1.由键盘输入正整数N，生成1到N 的全排列。（1= N =9）例如：输入2时，输出：1 11 22 12 2,应用之一： 排列组合问题,2.由键盘输入正整数N，生成1到N 的不重复全排列。（1= N =9）例如：输入2时，输出：1 22 1,3.输出从N个元素中选取M个元素的各种排列（1N、M9）。

25、 例如：N=3 M=2 输出： 1 2 1 3 2 1 2 3 3 1 3 2,4.输出从N个元素中选取M个元素的各种组合 （1N、M9）。 例如：N=3 M=2 输出： 1 2 1 3 2 3,5.已知两个自然数n和k（n,k=100），从1，2，n中任取k个数，要求所取的k个数中，任意两个数不能相差1。编程求有多少种取法。 如：n=6 ，k=3,，从1，2，3，4，5，6中取3个数，任意两个数不能相差1，取法如下： （1 3 5） （1 3 6） （1 4 6） （2 4 6） 共有4种取法。 提示：（1 3 5）和（3 1 5）属于一种取法。 输入（b.in）：一行，n和k，中间用空格隔

26、开。 输出（b.out）：一行，取法的种数。 样例： 输入：6 3 输出：4,三：广度优先搜索BFS,1.基本思路,广度优先搜索的思想是按层次遍历。以树为例，广度优先搜索就是：访问根节点，依次访问根结点的每一个子结点（第二层），再通过这些结点访问第三层结点，依次类推。,2.Bfs与dfs的比较,广度优先搜索与深度优先搜索相比较，时间复杂度相同，不同之处在于访问结点的顺序不同，本质都是遍历树（图）中的所有结点。 那么在具体题目中究竟选择哪种搜索策略呢？ 一般来说，广度优先搜索按层搜索，在求解初始状态到目标状态的最优解时，一般用Bfs； 而深度优先多用于求可行解，尤其是搜索树中的重复结点较多，且重

27、复不容易判断时经常使用。,例1：在一个8*4的棋盘中从左下角（0，0）点按照中国象棋中马的走法，走到有上角（8，4）点。规定每一步只能往右跳，不许往左跳。 问题1：请编程打印出所有可能的走法。 问题2：请编程打印出最短路径。,分析: 对于问题1，题目要求输出所有路径，而从棋盘的左下角到右上角的步骤不能确定，由于每一步只能往右走，所以最多不超过9步。因此可以用二位数组a1.9,1.2记录每一步跳到的位置。 移动规则：依题意，马最多有4个方向。设原来的位置为（I,j），则四个方向的移动可表示为(i+1,j+2）,(i+2,j+1),(i+2,j-1),(i+1,j-2)。 搜索策略为：从（0，0）

28、点出发，按移动规则依次选定某个方向，如果达到的是（8，4）则输出路径，否则继续搜索下一个到达的顶点。（dfs）。,参考程序： Program tiaoma1; Const X:array1.4,1.2 of integer=(2,1),(1,2),(2,-1),(1,-2); Var a:array1.9,1.2 of integer; Procedure try(i:integer); Var j:integer; Begin If (aI,1=8) and (aI,2=4) then begin for j:=1 to I do write(aj,1, ,aj,2, ); writeln;

29、 end,Else for i:=1 to 4 do begin if (aI,1+xj,1=0) and (aI,2+xj,2=0) then begin ai+1,1:=aI,1+xj,1; ai+2,1:=aI,2+xj,2; try(i+1); end; End; End; Begin AI,1:=0;aI,2:=0; Try1; End.,对于问题2，由于要求最短路径，用广度优先搜索。从（0，0）出发，先把移动一步后的布局全部找到，检查是否达到目标布局；如果没有，再从这些移动一步的布局出发，找到移动两步后的所有布局，再判断是否达到目标状态，如此继续，一直到目标状态出现为止，输出结果。

30、由于是按移动步数从少到多产生新布局，所以找到的第一个目标一定是移动步数最少的一个，即最优解。（注意，最优解可能不唯一）。,参考程序： Program tiaoma2; Const m=100; x:array1.4,1.2 of integer=(2,1),(1,2),(2,-1),(1,-2); Type nodetype=record x:integer; y:integer; parent:integer; end; Queuetype=array1.m of nodetype; Var Q:queuetype; R,f:integer; X1,x2,parent,i:integer;

31、Reach:boolean;,Procedure add(var q:queuetype;x,y,parent:integer;var r:integer); Begin if r=m then writeln(overflow) else begin qr.x:=x;qr.y:=y;qr.parent:=parent;将这一步的信息加入到队列，x,y是这一步的坐标，parent是这一步的上一步信息所在单元格的下标。 r:=r+1;end;end;,Procedure del(var q:queuetype;var x,y,parent:integer;var f:integer;); Beg

32、in if f=r then writeln(overflow) else begin x:=qf.x;y:=qf.y;parent:=qf.parent;从队列数组q中取出一个单元中的信息分别给x,y，parent同时修改队尾指针。 f:=f+1;end;end;,Begin r:=1f:=1;将队首指针指向1 add(q,0,0,0,r);将第一个点的信息入队，同时将第一个点的parent设为0 Reach:=false; While(fr) and not reach do Begin Del(q,x1,y1,parent,f);从队列中取出一个单元格，将这个单元格的信息分别给x1,y1

33、，将父单元格的信息给parent，同时修改队首指针f。 If (x1=8) and (y1=4) then reach:=true Else for i:=1 to 4 do begin if (x1+xI,1=0) and (y1+xI,2=0) then 不出界 begin parent:=f-1;新到达的点入队 Add(q,x1+xI,1,y1+xI,2,parent,r);end;end;end;,If reach then while parent0 do begin writeln(q.parent.x:5,qparent.y:5); parent:=qparent.parent;

34、 End; end;.,上机练习题： 1.写出图的深度优先搜索(DFS)算法和广度优先搜索(BFS)算法。 program dfsbfs(input,output); const n=8; var a:array0.n,0.nof integer;图的邻接矩阵 visited,come:array1.nof integer;访问标志 queue:array0.nof integer;队列 t:array1.nof char;结点信息 i,head,tail:integer;,procedure init; var i,j,e,k:integer; begin for i:=1 to n do

35、read(ti);顶点信息 fillchar(a,sizeof(a),0); read(e);边数 for k:=1 to e do读入边的点信息,建立邻接矩阵 begin read(i,j); ai,j:=1; aj,i:=1; end; end;,procedure dfs(i:integer); var j:integer; begin write(ti);输出结点信息 visitedi:=1;访问标志 for j:=1 to n do深度优先搜索i的邻接点 if (ai,j=1) and (visitedj=0) then dfs(j); end;,procedure bfs(i:in

36、teger);广搜 var j:integer; begin write(ti); visitedi:=1; tail:=tail+1;尾指针加1 queuetail:=i;入队列 while head =tail do队列非空 begin for j:=1 to n do搜索i的所有邻接点,如果没访问,入队列 if (aqueuehead,j=1 ) and (visitedj=0) then begin write(tj); visitedj:=1; tail:=tail+1; queuetail:=j; end; head:=head+1;出队列,访问队首元素 end; end;,Beg

37、in writeln; init; for i:=1 to n do visitedi:=0; for i:=1 to n do if visitedi=0 then dfs(i); writeln; head:=0; tail:=0; for i:=1 to n do visitedi:=0; for i:=1 to n do if visitedi=0 then bfs(i); end.,2.细胞 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 输入：整数m,n(m行，n列) （1=m=80,1=n=50）

38、 矩阵 输出：细胞的个数。 样例: 输入: 4 100234500067103456050020456006710000000089 输出:4,0234500067103456050020456006710000000089,共4个细胞,算法步骤： 1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入pic数组中； 2、沿pic数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队h，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(picI,j=1)则将其位置入队，入队后的位置picI,j数组置为0； 3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置

39、入队，入队后的位置pic数组置为0； 4、重复3，直至h队空为止，则此时找出了一个细胞； 5、重复2，直至矩阵找不到细胞； 6、输出找到的细胞数。,const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1); var s:string; pic:array1.80,1.50 of 0.1; 0:无细胞；1：有细胞 m,n,i,j,num:integer; h:array1.4000,1.2 of byte; 队列：存细胞的坐标，1：行；2：列,procedure doing(p,q:integer); 处理坐标（p,q）的细胞 var i,t,w,x,y:integer; begin inc(num); 细胞数量加1 picp,q:=0; t:=1; 队列头 w:=1; 队列尾 h1,1:=p;h1,2:=q;遇到的第一个细胞入队 repeat for i:=1 to 4 do 沿细胞的上下左右四个方向搜索细胞 begin x:=ht,1+dxi;y:=ht,2+dyi; if (x0) and (x0) and (yw;直至队空为止 end;,begin fillchar(pic,sizeof(pic),0)