noip讲义6-回溯法课件.ppt

noip讲义6-回溯法课件.ppt

ID:57058428

大小:251.00 KB

页数:38页

时间:2020-07-30

noip讲义6-回溯法课件.ppt_第1页
noip讲义6-回溯法课件.ppt_第2页
noip讲义6-回溯法课件.ppt_第3页
noip讲义6-回溯法课件.ppt_第4页
noip讲义6-回溯法课件.ppt_第5页
资源描述:

《noip讲义6-回溯法课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、回溯搜索回溯是一种模拟人类思维过程的算法思想。它的基本方法是:按照深度优先的顺序向下一层扩展结点;扩展到某一层时,若已无法继续扩展且仍未找到解,则退回到父结点,从父结点的下一个分支开始,按同样的策略继续扩展……,直到找到问题的解或证明无解。四皇后问题的递归实现constn=4; 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(

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。