第5章--搜索与回溯算法.ppt

《第5章--搜索与回溯算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章搜索与回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走

2、，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。递归回溯法算法框架[一]procedureSearch(k:integer);beginfori:=1to算符种数Doif满足条件thenbegin保存结果if到目的地then输出解elseSearch(k+1);恢复：保存结果之前的状态{回溯一步}end;end;递归回溯法算法框架[二]procedureSearch(k:integer);beginif到目的地then输出解elsefori:=1to算符种数Doif满足条件thenbegin保存结果Search(k+1,参数表);

3、end;end;【例1】奇数环:从1到6这6个数摆成一个环，要求相邻的两个数的和是一个奇数。【算法分析】非常明显，这是一道回溯的题目。从1开始，每个空位有6种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个奇数。第6个数还要判断和第1个数的和是否奇数。【算法流程】1、数据初始化；2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（6个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】programex5_1;框架[一]vara:array[0..20]ofinteger;b:array[0..20

4、]ofboolean;total:longint;procedureprint;//输出方案varj:integer;begininc(total);write('<',total,'>:');forj:=1to6dowrite(a[j],'');writeln;end;procedureSearch(t:integer);//回溯过程vari:integer;beginfori:=1to6do//有20个数可选ifodd(a[t-1]+i)andb[i]then//判断与前一个数是否构成奇数及该数是否可用begina[t]:=i;b[i]:=false;ift=6thenbe

5、ginifodd(a[6]+a[1])thenprint;endelseSearch(t+1);b[i]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);//b数组赋初值为Truetotal:=0;Search(1);write('total:',total);//输出总方案数END.【例1】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否

6、素数。【算法流程】1、数据初始化；2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】programex5_1;框架[一]vara:array[0..20]ofinteger;b:array[0..20]ofboolean;total:longint;functionpd(x,y:integer):boolean;//判断素数vark,i:integer;begink:=2;i:=x+y;pd:=false;while(k<=trunc(sqrt(i)))and

7、(imodk<>0)doinc(k);ifk>trunc(sqrt(i))thenpd:=true;end;procedureprint;//输出方案varj:integer;begininc(total);write('<',total,'>:');forj:=1to20dowrite(a[j],'');writeln;end;procedureSearch(t:integer);//回溯过程vari:integer;beginfori:=1to20do//有20个数可选ifpd(a[t-