资源描述：
《noip讲义6-回溯法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、回溯搜索回溯是一种模拟人类思维过程的算法思想。它的基本方法是：按照深度优先的顺序向下一层扩展结点；扩展到某一层时，若已无法继续扩展且仍未找到解，则退回到父结点，从父结点的下一个分支开始，按同样的策略继续扩展……，直到找到问题的解或证明无解。四皇后问题的递归实现constn=４; vari,j,k:integer; x:array[1..n]ofinteger;{保存第i个皇后的列号}functionplace(k:integer):boolean; vari:integer; begin place:=true; fori:=1tok-1do if(x[i]
2、=x[k])or(abs(x[i]-x[k])=abs(i-k))thenplace:=false; end;procedureprint; vari:integer; begin fori:=1tondowrite(x[i]:4); writeln; end;proceduretry(k:integer); vari:integer; begin if()thenbeginprint;()end; fori:=()do begin (); ifplace(k)then();end; end; begintry(1);{摆放第一个皇后}end.k=n+1x
3、[k]:=itry(k+1)1tonexit皇后序号摆放下一个皇后因为从第i个皇后到第i+1个皇后的摆放方法是相同的,所以可以用递归的方法.vari,k,n:integer;x:array[1..9]ofinteger;functionplace(k:integer):boolean;vari:integer;beginplace:=true;fori:=1tok-1doif()thenbeginplace:=false;breakend;end;procedureprint;vari:integer;beginfori:=1tondowrite(x[i],'');write
4、ln;end;数字排列问题的递归实现x[i]=x[k]proceduretry(k:integer);vari:integer;beginif()thenbeginprint;exit;end;fori:=1tondobegin();if()thentry(k+1)endend;beginreadln(n);try(1);end.k>nx[k]:=iplace(k)骑士游历问题的递归实现constx:array[1..4,1..2]ofinteger=((1,2),(2,1),(2,-1),(1,-2));varn,m:integer;a:array[1..30,1..2]o
5、finteger;procedureprint(ii:integer);vari:integer;beginfori:=1toii-1dowrite(a[i,1],',',a[i,2],'->');writeln(n,',',m);()end;proceduretry(i:integer);varj:integer;beginforj:=1to4doif(a[i-1,1]+x[j,1]<=n)and(a[i-1,2]+x[j,2]>=0)and(a[i-1,2]+x[j,2]<=m)thenbegina[i,1]:=a[i-1,1]+x[j,1];a[i,2]:=a[i-1,
6、2]+x[j,2];if(a[i,1]=n)and(a[i,2]=m)then()else();()end;end;beginread(n,m);try(2);writeln(‘NO’);end.print(i)a[i,1]:=0;a[i,2]:=0try(i+1)halt回溯法的递归算法框架：procedurerun（当前状态);vari:integer;beginif当前状态为目标状态thenbeginif当前状态为最佳目标状态then记下最优结果；exit;end;fori←算符最小值to算符最大值dobegin算符i作用于当前状态，扩展出一个子状态;if(子状态满足约
7、束条件)and(子状态满足最优性要求)thenrun(子状态);end;end；二种方式的区别:1、递归方式实现简单，非递归方式比较复杂。2、递归方式需要利用栈空间，如果搜索量过大，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归方式实现较好。回溯法的剪枝回溯搜索的进程可以看作是从树根出发，遍历一棵搜索树的过程．所谓剪枝，就是通过某种判断条件，避免一些不必要的遍历过程，形象地说，就是剪去了搜索树中的某些“枝条”．下图是一个求最短路径扩展的搜索树，描述了剪枝的过程．A(0)B(10)C(20)D(
