递归回溯搜索

递归—回溯—搜索几个简单的递归例题例1，N!。N!=N*(N-1)!，因此求N!转化为求(N-1)!。这就是一个递归的描述。010)!1(*!nnnnn因此，可以编写如下递归程序：programFactorial;varN:Integer;T:Longint;functionFac(N:Integer):Longint;beginifN=0thenFac:=1elseFac:=N*Fac(N-1)end;beginWrite('N=');Readln(N);T:=Fac(N);Writeln('N!=',T);end.例2：裴波那契数列的定义：2120121nffnnfnnn对应的递归程序为functionfib(n:Integer):Integer;beginifn=0thenfib:=1{递归边界}elseifn=1thenfib:=2{递归边界}elsefib:=fib(n–2)+fib(n–1);{递归}end;例3：汉诺塔问题：有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。输出总共移动的次数。ABC分析：在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。programhannuota;varn:integer;procedurehnt(a,b,c,n:integer);beginifn=1thenwriteln(a,'-',c)elsebeginhnt(a,c,b,n-1);writeln(a,'-',c);hnt(b,a,c,n-1);end;end;beginwrite('pleaseinputn:');read(n);hnt(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)=2f(n-1)+1{现在就可以用递推做了}f(1)=1f(2)=3f(3)=7f(4)=15f(n)=2n-1现在可以用数学方法做了回溯法的基本思想为：在按某种搜索策略的搜索过程中，在某种状态，继续往前搜索已经确定不会得到正确答案的情况下，我们可以返回上一搜索状态，去沿新的可能性继续搜索。要回溯到上一状态，则说明我们在前进中的状态必须保存下来，我们采用“栈”来存放。回溯与dfs的关系在我们的实际生活和信息学奥赛当中很多问题是不能用数学公式去解决的，解决问题的过程，往往是通过一系列的步骤，在每一步中根据条件的不同，又有多种可能性，为了达到问题最终的要求，在解决过程中需要遵循某种控制策略。对于此类问题，我们往往采用搜索的方法来解决，而我们要研究的回溯法就是搜索的控制策略之一。回溯法的特点为：1.搜索策略：符合递归算法，问题解决可以化为子问题，算法类似，规模减小。2.控制策略：当遇到失败的搜索状态，需要返回上一状态，沿另外的路径搜索。3.数据结构：用数组保存搜索过程中的状态、路径。算法框架：1针对所给问题，定义问题的解空间；2确定易于搜索的解空间结构；3以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。参考结构：proceduretry(i:integer);varbeginifinthen输出结果elseforj:=下界to上界dobeginx[i]:=h[j];if可行{满足限界函数和约束条件}thenbegin置值；try(i+1);取消置值；end;end;end;说明：i是递归深度；n是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。回溯即是较简单、较常用的搜索策略。基本思路：若已有满足约束条件的部分解，不妨设为（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个皇后），编程求解所有的摆放方法。八皇后的两组解分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。下面是放置第I个皇后的的递归算法：ProcedureTry(I:integer)；{搜索第I行皇后的位置}varj:integer;beginifI=n+1then输出方案；forj:=1tondoif皇后能放在第I行第J列的位置thenbegin放置第I个皇后；对放置皇后的位置进行标记；Try（I+1）对放置皇后的位置释放标记；End;End;N皇后问题的递归算法的程序如下：programN_Queens;constMaxN=100;{最多皇后数}varA:array[1..MaxN]ofBoolean;{同列-竖线被控制标记}B:array[2..MaxN*2]ofBoolean;{i+j和相等-左下到右上斜线被控制标记}C:array[1–MaxN..MaxN–1]ofBoolean;{j-i差相等-左上到右下斜线被控制标记}X:array[1..MaxN]ofInteger;{记录皇后的解}Total:Longint;{解的总数}N:Integer;{皇后个数}procedureOut;{输出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureTry(I:Integer);{搜索第I个皇后的可行位置}varJ:Integer;beginifI=N+1thenOut;{N个皇后都放置完毕，则输出解}forJ:=1toNdoifA[J]andB[J+I]andC[J–I]thenbeginX[I]:=J;A[J]:=False;B[J+I]:=False;C[J–I]:=False;Try(I+1);{搜索下一皇后的位置}A[J]:=True;B[J+I]:=True;C[J–I]:=True;end;end;beginWrite(‘QueensNumbers=‘);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）要求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理:①.不作任何处理;②.在它的左边加上一个自然数,但该自然数不能超过原数的一半;③.加上数后,继续按此规则进行处理,直到不能再加自然数为止.输入文件：add.in,一行，n的值。输出文件：add.out，一行，按照规则可产生的自然数个数。样例：输入文件：6满足条件的数为6162612636136输出文件6varn,i:integer;s:real;procedureqiu(x:integer);vark:integer;beginifx0thenbegins:=s+1;fork:=1toxdiv2doqiu(k)endend;beginreadln(n);s:=0;qiu(n);writeln(s)end.2.跳马问题。（jump.pas）在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。输出文件：jump.out，一行，路径条数。programjump;varh:array[-1..7,-1..7]ofinteger;a,b:array[1..8]ofinteger;i,j,num:integer;procedureprint;vari,j:integer;beginnum:=num+1;{ifnum=5thenbeginfori:=1to5dobeginforj:=1to5dowrite(h[i,j]:4);writeln;end;writeln;end;}end;proceduretry(x,y,i:integer);varj,u,v:integer;beginforj:=1to8dobeginu:=x+a[j];v:=y+b[j];ifh[u,v]=0thenbeginh[u,v]:=i;ifi25thentry(u,v,i+1)elseprint;h[u,v]:=0end;end;end;beginfori:=-1to7doforj:=-1to7doif(i=1)and(i=5)and(j=1)and(j=5)thenh[i,j]:=0elseh[i,j]:=1;a[1]:=2;b[1]:=1;a[2]:=1;b[2]:=2;a[3]:=-1;b[3]:=2;a[4]:=-2;b[4]:=1;a[5]:=-2;b[5]:=-1;a[6]:=-1;b[6]:=-2;a[7]:=1;b[7]:=-2;a[8]:=2;b[8]:=-1;num:=0;h[1,1]:=1;try(1,1,2);writeln(num);end.深度优先搜索在信息学奥赛中，有的试题能在有限的时间内，用简明的数学模型揭示问题的本质，对于这类问题我们尽量用解析法求解；但也有些问题，很难建立数学模型，对于这类问题，我们只能采用模拟或搜索求解，尽管搜索的复杂度一般都是指数级的，但在缺乏解决问题的有效模型时，搜索却是一种最行之有效的解决问题的办法，而且在用搜索解决问题时，在实现过程中存在很大的优化空间，在信息学奥赛中考察搜索算法，除了考察选手的算法运用能力