资源描述：
《较好的深搜课件搜索与回溯》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、搜索与回溯对于某个问题，如果没有高效的算法，或者用高效的算法解决有一定的困难，我们常用搜索算法来求解，即通过枚举每一种可行的方案来找到题目的答案。深度优先搜索只要当前枚举到的状态可行，就继续枚举下去。当找到一种方案或者无法继续枚举下去时，就退回到上一状态。退回到上一状态的过程叫做回溯。给定n（n≤10），求1,2,3,…,n的全排列个数。如果一个数列包含这n个数，并且这n个数都仅出现一次，符合该条件的所有数列叫做这n个数的全排列。如1,2,3三个元素的全排列为:1,2,31,3,22,1,32,3,13,1,23,2,1看一个简单的问题什么是
2、全排列？可能有的同学已经注意到了这个问题的答案就是n！=1×2×3×……×n如果要输出所有方案呢？我们可以用一个布尔数组used来表示每个数字是否用过，用过为true，未用过为false。用ans[i]记录第i个位置的数是多少fori:=1tondoifnotused[i]then//若i未出现过则在第k个位置放ibeginans[k]:=i;used[i]:=true;//标记dfs(k+1);//继续搜索used[i]:=false;//回溯end;end;beginread(n);dfs(1);end.programquanpailie
3、;varn:longint;ans:array[0..10]oflongint;used:array[0..10]ofboolean;proceduredfs(k:longint);vari:longint;beginifk>nthenbeginfori:=1ton-1dowrite(ans[i],'');writeln(ans[n]);exit;end;ABProceduresearch(k:integer）;beginif到目的地then输出解;exit;forI:=1to算符种数dobegin保存结果search(k+1）；恢复到保存结
4、果之前的状态end;end;深度优先搜索的一般框架：Proceduredfs(k,……);var……beginif已找到一种方案thenbeginprint;exit;end;枚举每种选择if该选择可行thenbegin更改该选择标记dfs(k+1,……）；回溯end;end;AB例：设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如表所示：J1J2J3J4J5A13111047B13101085C59774D151210115E1011884求最佳安排使效益最高。分析：每人选择五项工作中的一项
5、，在各种选择的组合中，找到效益最高的一种组合输出。constdata:array[1..5,1..5]ofinteger=((13,11,10,4,7),(13,10,10,8,5),(5,9,7,7,4),(15,12,10,11,5),(10,11,8,8,4));vari,max:integer;g,f:array[1..5]ofinteger;p:array[1..5]ofinteger;procedurego(step,t:integer);vari:integer;beginifstep>5thenbeginift>maxthen
6、beginmax:=t;g:=f;end;exit;end;fori:=1to5doifp[i]=0thenbeginf[step]:=i;p[i]:=1;t:=t+data[step,i];go(step+1,t);t:=t-data[step,i];p[i]:=0;end;end;beginmax:=0;fori:=1to5dop[i]:=0;go(1,0);writeln;fori:=1to5dowrite(chr(64+i),':j',g[i],'':3);writeln;writeln('supply:',max);end.学校放寒
7、假时，信息学竞赛辅导教师有A，B，C，D，E五本书，要分给参加培训的张、王，刘、孙、李五位学生，每人只能一本书。教师事先让每个人将自己喜爱的书填写在如下的表中。然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出所有可能的分书方案，使每个学生都满意。ABCDE张同学YY王同学YYY刘同学YY孙同学Y李同学YYconstlike:array[1..5,1..5]ofinteger=((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));name:array[1..5]o
8、fstring=('zhang','wang','liu','sun','li');varp,f:array[1..5]ofinteger;t:integer;pr
