资源描述：
《递归回溯搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、递归—回溯—搜索几个简单的递归例题例1，N!。N!=N*(N-1)!，因此求N!转化为求(N-1)!。这就是一个递归的描述。因此，可以编写如下递归程序：programFactorial;varN:Integer;T:Longint;functionFac(N:Integer):Longint;beginifN=0thenFac:=1elseFac:=N*Fac(N-1)end;beginWrite('N=');Readln(N);T:=Fac(N);Writeln('N!=',T);end.例2：裴波那契数列的定义：对应的递归程序为functionfi
2、b(n:Integer):Integer;beginifn=0thenfib:=1{递归边界}elseifn=1thenfib:=2{递归边界}elsefib:=fib(n–2)+fib(n–1);{递归}end;例3：汉诺塔问题：有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。输出总共移动的次数。ABC分析：在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一
3、个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。programhannuota;varn:integer;procedurehnt(a,b,c,n:integer);beginifn=1thenwriteln(a,'->',c)elsebeginhnt(a,c,b,n-1);writeln(a,'->',c);hnt(b,a,c,n-1);end;end;beginwrite('pleaseinputn:');read(n);hnt(1,2,3,n);end.汉诺塔问
4、题的递推解法设f(n)为n个盘子从1柱移到3柱所需移动的最少盘次。 当n=1时，f(1)=1。当n=2时，f(2)=3。以此类推，当1柱上有n(n>2)个盘子时，我们可以利用下列步骤：第一步：先借助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)=1f
5、(2)=3f(3)=7f(4)=15f(n)=2n-1现在可以用数学方法做了回溯法的基本思想为：在按某种搜索策略的搜索过程中，在某种状态，继续往前搜索已经确定不会得到正确答案的情况下，我们可以返回上一搜索状态，去沿新的可能性继续搜索。要回溯到上一状态，则说明我们在前进中的状态必须保存下来，我们采用“栈”来存放。回溯与dfs的关系在我们的实际生活和信息学奥赛当中很多问题是不能用数学公式去解决的，解决问题的过程，往往是通过一系列的步骤，在每一步中根据条件的不同，又有多种可能性，为了达到问题最终的要求，在解决过程中需要遵循某种控制策略。对于此类问题，我们往往
6、采用搜索的方法来解决，而我们要研究的回溯法就是搜索的控制策略之一。回溯法的特点为：1.搜索策略：符合递归算法，问题解决可以化为子问题，算法类似，规模减小。2.控制策略：当遇到失败的搜索状态，需要返回上一状态，沿另外的路径搜索。3.数据结构：用数组保存搜索过程中的状态、路径。算法框架：1针对所给问题，定义问题的解空间；2确定易于搜索的解空间结构；3以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。参考结构：proceduretry(i:integ
7、er);varbeginifi>nthen输出结果elseforj:=下界to上界dobeginx[i]:=h[j];if可行{满足限界函数和约束条件}thenbegin置值；try(i+1);取消置值；end;end;end;说明：i是递归深度；n是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提
8、高搜索的效率，即启发式的搜索。回溯即是较简单、较常用的搜索策略。基本思路：若已有满足约束条件的
