递归回溯搜索教学教材.ppt

《递归回溯搜索教学教材.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归回溯搜索递归的概念由函数或者过程调用引起。一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。例3：汉诺塔问题：有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。输出总共移动的次数。ABC分析：在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一

2、样的，当盘子搬到只剩一个时，递归结束。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.汉诺塔问题的递推解法设f(n)为n个盘子从1柱移到3柱所需移动的最少盘次。当n=1时，f(1)

3、=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(2)=3f(3)=7f(4)=15f(n)=2n-1现在可以用数学方法做了练习

4、1：简单背包问题。有一个背包容量为s，现有n件物品，重量分别为s1、s2、s3。。。Si（1<=i<=n）,假设si均为正数，从这n件物品中选择若干件物品放入背包，使得放入总重量恰好为s，请输出一种解，若无解输出“NOANSWER”。练习2快速排序vara:array[1..10000]oflongint;n,i:longint;procedureqsort(s,t:longint);vari,j,x:longint;begini:=s;j:=t;x:=a[i];while(i

5、dec(j);a[i]:=a[j];while(i

6、数学公式去解决的，解决问题的过程，往往是通过一系列的步骤，在每一步中根据条件的不同，又有多种可能性，为了达到问题最终的要求，在解决过程中需要遵循某种控制策略。对于此类问题，我们往往采用搜索的方法来解决，而我们要研究的回溯法就是搜索的控制策略之一。参考结构：proceduretry(i:integer);varbeginifi>nthen输出结果elseforj:=下界to上界dobeginx[i]:=h[j];if可行{满足限界函数和约束条件}thenbegin置值；try(i+1);取消置值；end;end;end;例4：N皇后问题在N*N

7、的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。八皇后的两组解分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。下面是放置第I个皇后的的递归算法：ProcedureTry(I:integer)；{搜索第I行皇后的位置}varj:integer;beginifI=n+1then输出方案；forj:=1ton

8、doif皇后能放在第I行第J列的位置thenbegin放置第I个皇后；对放置皇后的位置进行标记；Try（I+1）对放置皇后的位置释放标记；End;En