《《搜索与回溯》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《搜索与回溯》PPT课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、搜索与回溯对于某个问题，如果没有高效的算法，或者用高效的算法解决有一定的困难，我们常用搜索算法来求解，即通过枚举每一种可行的方案来找到题目的答案。深深度度优优先先搜搜索索只要当前枚举到的状态可行，只要当前枚举到的状态可行，就继续枚举下去。当找到一种就继续枚举下去。当找到一种方案或者无法继续枚举下去时，方案或者无法继续枚举下去时，就退回到上一状态。退回到上就退回到上一状态。退回到上一状态的过程叫做回溯一状态的过程叫做回溯。给定给定n（n10），求），求1,2,3,n的全排列个的全排列个数。数。如果一个数列含包含这如果一个数列含包含这n个数，并且这个数，并且这n个数个数都仅出现一次，符合该条件的所
2、有数列叫做这都仅出现一次，符合该条件的所有数列叫做这n个数的全排列。个数的全排列。如如1,2,3三个元素的全排列为三个元素的全排列为:1,2,3 1,3,2 2,1,32,3,1 3,1,2 3,2,1看一个简单的问题什么是全排列？什么是全排列？可能有的同学已经注意到了可能有的同学已经注意到了这个问题的答案就是这个问题的答案就是n！=123n如果要输出所有方案呢？如果要输出所有方案呢？先确定放先确定放在第在第1个个位置的是位置的是哪个数哪个数当当n个位个位置的数都置的数都确定下来确定下来后，我们后，我们就得到了就得到了一个方案一个方案依次确定第依次确定第2个个位置，第位置，第3个位个位置，置，
3、第，第n个位置个位置我们可以用一个布尔数组我们可以用一个布尔数组usedused来表来表示每个数字是否用过，用过为示每个数字是否用过，用过为truetrue，未用过为，未用过为falsefalse。用。用ansiansi记录记录第第i i个位置的数是多少个位置的数是多少 for i:=1 to n dofor i:=1 to n do if not usedi then if not usedi then /若若i i未出现过则在未出现过则在 第第k k个位置放个位置放i i begin begin usedi:=true;usedi:=true;/标记标记 ansk:=i;ansk:=i;d
4、fs(k+1);/dfs(k+1);/继续搜索继续搜索 usedi:=false;/usedi:=false;/回溯回溯 end;end;end;end;begin begin read(n);read(n);dfs(1);dfs(1);end.end.program quanpailie;program quanpailie;var var n:longint;n:longint;ans:array 0.10 of longint;ans:array 0.10 of longint;used:array 0.10 of boolean;used:array 0.10 of boolean;p
5、rocedure dfs(k:longint);procedure dfs(k:longint);var var i:longint;i:longint;begin begin if kn then if kn then begin begin for i:=1 to n-1 do for i:=1 to n-1 do write(ansi,);write(ansi,);writeln(ansn);writeln(ansn);exit;exit;end;end;枚举每种选择枚举每种选择 if if 该选择可行该选择可行 thenthen begin begin 更改该选择标记更改该选择标记 d
6、fs(k+1,dfs(k+1,）；）；回溯回溯 end;end;end;end;深度优先搜索的一般框架：深度优先搜索的一般框架：Procedure dfs(k,);Procedure dfs(k,);var var begin begin if if 已找到一种方案已找到一种方案 thenthen begin begin print;print;exit;exit;end;end;派对派对 TYVJ P1085Matrix67发现身高接近的人似乎更合得来。发现身高接近的人似乎更合得来。Matrix67举办的派对共有举办的派对共有N(1=Nn then if in then begin begi
7、n f:=true;f:=true;for j:=1 to n-1 do for j:=1 to n-1 do if abs(ansj-ansj+1)k then if abs(ansj-ansj+1)k then begin begin f:=false;f:=false;break;break;end;/end;/检验检验1 1与与2 2，n-1n-1与与n n if f and(abs(ansn-ans1)=k)if f and(abs(ansn-ans1)=k)then inc(s);then inc(s);exit;exit;end;end;有没有更好的做法？有没有更好的做法？我们发
8、现，当我们确定下第一个位置的人与第二个我们发现，当我们确定下第一个位置的人与第二个位置的人时，他们的身高可能已经不符合要求了，位置的人时，他们的身高可能已经不符合要求了，但我们仍然搜索了下去。我们可以一边搜索一边判但我们仍然搜索了下去。我们可以一边搜索一边判断。断。依次确定每个位置上的人，检验一下该位置的人与前一位置的依次确定每个位置上的人，检验一下该位置的人与前一位置的人是否符合要求人是否符合要求当所有人都已确定，再检验当所有人都已确定，再检验n位置与位置与1位置的人是否符合位置的人是否符合要求要求我们可以把第一个人固定在第一个位置再进行搜索，这样最后我们可以把第一个人固定在第一个位置再进行
9、搜索，这样最后的答案就不用再除以的答案就不用再除以n for j:=1 to n dofor j:=1 to n do if canj and if canj and (abs(aj-ansi-1)=k)then (abs(aj-ansi-1)n then if in then begin begin if abs(ansn-ans1)=k if abs(ansn-ans1)n then if in then begin begin inc(ans);inc(ans);exit;exit;end;end;for j:=1 to n do for j:=1 to n do if ajand bi
10、+jand ci-jthen if ajand bi+jand ci-jthen你有你有n堆石头质量分别为堆石头质量分别为W1，W2，Wn(W100 000）。现在）。现在需要你将石头合并为两部分，使两部分的质量之和最接近。需要你将石头合并为两部分，使两部分的质量之和最接近。输入：第一行为整数输入：第一行为整数n（1n20），表示有），表示有n堆石子。第二行堆石子。第二行n个整个整数，为每堆石子的质量。数，为每堆石子的质量。输出：一行。只需要输出合并后两部分的质量之和的差。输出：一行。只需要输出合并后两部分的质量之和的差。样例输入：样例输入：样例输出：样例输出：5 35 8 13 27 14石
11、子合并石子合并我们可以知道这我们可以知道这n堆石子的质量和堆石子的质量和sum。从而只要知道一部分石子的质量就可以知道另一部分的质量。从而只要知道一部分石子的质量就可以知道另一部分的质量。可以用搜索枚举哪些石子放在第一部分，得到第一部分的质量可以用搜索枚举哪些石子放在第一部分，得到第一部分的质量a，求出所有方案中，求出所有方案中abs（sum-a）-a）中最小的即为答案。）中最小的即为答案。如果第一部分石子质量之和已超过总质量的一半，继续向该如果第一部分石子质量之和已超过总质量的一半，继续向该部分中加入石子，两部分质量差的绝对值必然增大，没有继部分中加入石子，两部分质量差的绝对值必然增大，没有
12、继续搜索的必要。续搜索的必要。begin begin ans:=maxlongint;ans:=maxlongint;sum:=0;sum:=0;read(n);read(n);for i:=1 to n do for i:=1 to n do begin begin read(wi);read(wi);sum:=sum+wi;sum:=sum+wi;end;end;dfs(1,0);dfs(1,0);writeln(ans);writeln(ans);end.end.program shizihebing;program shizihebing;var var ans,sum,i,j,k,n
13、:longint;ans,sum,i,j,k,n:longint;w:array 0.20 of longint;w:array 0.20 of longint;function min(a,b:longint):longint;function min(a,b:longint):longint;begin begin if ab then exit(b)else exit(a);if ab then exit(b)else exit(a);end;end;procedure dfs(k,tot:longint);procedure dfs(k,tot:longint);begin begin
14、 if(tot*2=sum)or(kn)then if(tot*2=sum)or(kn)then begin begin ans:=min(ans,abs(sum-tot-tot);ans:=min(ans,abs(sum-tot-tot);exit;exit;end;end;dfs(k+1,tot+wk);dfs(k+1,tot+wk);/将第将第k k堆石子并入第一部分堆石子并入第一部分 dfs(k+1,tot);dfs(k+1,tot);/将第将第k k堆石子并入第二部分堆石子并入第二部分 end;end;自然数拆分自然数拆分 输入自然数输入自然数n，然后将其拆分成由若干数相加的形式，然
15、后将其拆分成由若干数相加的形式，参与加法运算的数可以重复。参与加法运算的数可以重复。输入只有一个整数输入只有一个整数n，表示待拆分的自然数，表示待拆分的自然数n。n=0 then dfs(i,tot-i);if tot-i=0 then dfs(i,tot-i);end;end;NOIP2009靶形数独有一个未填满的数独，求这个数独填满后能获得的最大总分数有一个未填满的数独，求这个数独填满后能获得的最大总分数分数计算方法：分数计算方法：总分数为每个方格上的分值和完成这个数独时填在相应格上的数字的乘总分数为每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和积的总和 时间限制时间限制
16、2s样例输入样例输入7 0 0 9 0 0 0 0 11 0 0 0 0 5 9 0 00 0 0 2 0 0 0 8 00 0 5 0 2 0 0 0 30 0 0 0 0 0 6 4 84 1 3 0 0 0 0 0 00 0 7 0 0 2 0 9 02 0 1 0 6 0 8 0 40 8 0 5 0 4 0 1 2 样例输出样例输出2829一个最简单的想法：一个最简单的想法：我们可以从左上角到右下角枚举每一个未填上的我们可以从左上角到右下角枚举每一个未填上的格子，再枚举它可以放哪些数字，将它填上后继续搜格子，再枚举它可以放哪些数字，将它填上后继续搜索。当所有格子都填上后，计算一下总分
17、，如果总分索。当所有格子都填上后，计算一下总分，如果总分大于当前最优值就更新最优值大于当前最优值就更新最优值这样大约可以得这样大约可以得35分分我们还可以对上面的想法进行改进：我们还可以对上面的想法进行改进：我们可以先计算出每个格子的选择数我们可以先计算出每个格子的选择数先确定可选择数小的格子先确定可选择数小的格子即先把只有一种选择的格子确定下来即先把只有一种选择的格子确定下来再确定有两种选择的格子再确定有两种选择的格子从而避免搜索到过多无法得到可行方案的状态从而避免搜索到过多无法得到可行方案的状态这样大约可以得这样大约可以得75分分对于这道题，由于数据的原因，如果从右下角到左上角枚对于这道题
18、，由于数据的原因，如果从右下角到左上角枚举，可以得到举，可以得到90分左右。分左右。如果再加上一个叫做卡步的东西，我们可以得到如果再加上一个叫做卡步的东西，我们可以得到100分。分。什么是卡步？什么是卡步？我们发现搜到一个可行的方案是很快的，时间主要用于更我们发现搜到一个可行的方案是很快的，时间主要用于更新最优解。卡步就是当执行的步数到达一定值时，若程序新最优解。卡步就是当执行的步数到达一定值时，若程序还没有结束，那么我们就直接输出搜到的最优解，并退出。还没有结束，那么我们就直接输出搜到的最优解，并退出。这个值很有可能不是最优的，但若继续搜索下去必然会超这个值很有可能不是最优的，但若继续搜索下
19、去必然会超时，所以我们直接退出。这是在比赛中常用的技巧。时，所以我们直接退出。这是在比赛中常用的技巧。如何卡步？如何卡步？最简单的办法就是在过程最简单的办法就是在过程dfs中加入中加入inc(p);if p then begin writeln(ans);halt;end;本题可以用搜索本题可以用搜索+卡步得到卡步得到100分，很重要的原分，很重要的原因是这道题测试数据的特殊性。因是这道题测试数据的特殊性。如果要使程序能通过任何数据，可以采用位运算如果要使程序能通过任何数据，可以采用位运算加速搜索和加速搜索和Dancing-links，但这两种方法在联，但这两种方法在联赛范围内基本不会出现，我
20、们不进行深入讨论。赛范围内基本不会出现，我们不进行深入讨论。另外还用一种方法可以得到另外还用一种方法可以得到100分：分：根据当前状根据当前状态确定每个格子的选择数态确定每个格子的选择数我们之前有一个想法是按选择数从少我们之前有一个想法是按选择数从少到多搜索，但当我们确定下一个格子到多搜索，但当我们确定下一个格子的数字后，会影响其它格子的选择，的数字后，会影响其它格子的选择，使它们的选择数减少。所以我们可以使它们的选择数减少。所以我们可以在搜索的时候计算格子的选择数，从在搜索的时候计算格子的选择数，从当前当前选择数最少的格子开始搜索。选择数最少的格子开始搜索。program sudoku;pr
21、ogram sudoku;const const z:array 1.9,1.9 of longint=(1,1,1,2,2,2,3,3,3),z:array 1.9,1.9 of longint=(1,1,1,2,2,2,3,3,3),(1,1,1,2,2,2,3,3,3),(1,1,1,2,2,2,3,3,3),(1,1,1,2,2,2,3,3,3),(1,1,1,2,2,2,3,3,3),(4,4,4,5,5,5,6,6,6),(4,4,4,5,5,5,6,6,6),(4,4,4,5,5,5,6,6,6),(4,4,4,5,5,5,6,6,6),(4,4,4,5,5,5,6,6,6),(
22、4,4,4,5,5,5,6,6,6),(7,7,7,8,8,8,9,9,9),(7,7,7,8,8,8,9,9,9),(7,7,7,8,8,8,9,9,9),(7,7,7,8,8,8,9,9,9),(7,7,7,8,8,8,9,9,9);(7,7,7,8,8,8,9,9,9);fenshu:array 1.9,1.9 of longint=(6,6,6,6,6,6,6,6,6),fenshu:array 1.9,1.9 of longint=(6,6,6,6,6,6,6,6,6),(6,7,7,7,7,7,7,7,6),(6,7,7,7,7,7,7,7,6),(6,7,8,8,8,8,8,7,
23、6),(6,7,8,8,8,8,8,7,6),(6,7,8,9,9,9,8,7,6),(6,7,8,9,9,9,8,7,6),(6,7,8,9,10,9,8,7,6),(6,7,8,9,10,9,8,7,6),(6,7,8,9,9,9,8,7,6),(6,7,8,9,9,9,8,7,6),(6,7,8,8,8,8,8,7,6),(6,7,8,8,8,8,8,7,6),(6,7,7,7,7,7,7,7,6),(6,7,7,7,7,7,7,7,6),(6,6,6,6,6,6,6,6,6);(6,6,6,6,6,6,6,6,6);varvar i,j,ans,t:longint;i,j,ans,t:
24、longint;map:array 0.9,0.9 of longint;map:array 0.9,0.9 of longint;hang,lie,ge:array 1.9,1.9 of boolean;hang,lie,ge:array 1.9,1.9 of boolean;x,y:array 0.81 of longint;x,y:array 0.81 of longint;c:array 0.81 of boolean;c:array 0.81 of boolean;procedure calc;/procedure calc;/计算总分计算总分 var var i,j,s:longi
25、nt;i,j,s:longint;begin begin s:=0;s:=0;for i:=1 to 9 do for i:=1 to 9 do for j:=1 to 9 do for j:=1 to 9 do s:=s+mapi,j*fenshui,j;s:=s+mapi,j*fenshui,j;if sans then ans:=s;if sans then ans:=s;end;end;procedure dfs(k:longint);procedure dfs(k:longint);var var xx,yy,i,min,w,j,p:longint;xx,yy,i,min,w,j,p
26、:longint;begin begin if kt then if kt then begin begin calc;calc;exit;exit;end;end;min:=maxlongint;min:=maxlongint;for i:=1 to t do for i:=1 to t do if ci then if ci then begin begin w:=0;w:=0;for j:=1 to 9 do for j:=1 to 9 do if hangxi,j and lieyi,j and gezxi,yi,j then if hangxi,j and lieyi,j and g
27、ezxi,yi,j then begin begin inc(w);inc(w);if w=min then break;if w=min then break;end;end;if wmin then if wmin then begin begin p:=i;p:=i;min:=w;min:=w;end;end;end;/end;/找出当前选择最少的找出当前选择最少的 xx:=xp;xx:=xp;yy:=yp;yy:=yp;cp:=false;cp:=false;for i:=1 to 9 do/for i:=1 to 9 do/枚举填哪个数枚举填哪个数 if hangxx,i and l
28、ieyy,i and gezxx,yy,i then if hangxx,i and lieyy,i and gezxx,yy,i then begin begin mapxx,yy:=i;mapxx,yy:=i;hangxx,i:=false;hangxx,i:=false;lieyy,i:=false;lieyy,i:=false;gezxx,yy,i:=false;gezxx,yy,i:=false;dfs(k+1);dfs(k+1);hangxx,i:=true;hangxx,i:=true;lieyy,i:=true;lieyy,i:=true;gezxx,yy,i:=true;ge
29、zxx,yy,i:=true;mapxx,yy:=0;/mapxx,yy:=0;/回溯回溯 end;end;cp:=true;/cp:=true;/回溯回溯 end;end;begin begin ans:=-1;ans:=-1;t:=0;t:=0;fillchar(hang,sizeof(hang),true);fillchar(hang,sizeof(hang),true);fillchar(lie,sizeof(lie),true);fillchar(lie,sizeof(lie),true);fillchar(ge,sizeof(ge),true);fillchar(ge,sizeof
30、(ge),true);for i:=1 to 9 do for i:=1 to 9 do for j:=1 to 9 do for j:=1 to 9 do begin begin read(mapi,j);read(mapi,j);if mapi,j=0 then if mapi,j=0 then begin begin inc(t);inc(t);xt:=i;xt:=i;yt:=j;yt:=j;ct:=true;ct:=true;end end else else begin begin hangi,mapi,j:=false;hangi,mapi,j:=false;liej,mapi,j
31、:=false;liej,mapi,j:=false;gezi,j,mapi,j:=false;gezi,j,mapi,j:=false;end;end;end;end;dfs(1);dfs(1);writeln(ans);writeln(ans);end.end.我们可以看出，搜索算法的效率是很我们可以看出，搜索算法的效率是很低的，要提高效率，就要尽量早把没低的，要提高效率，就要尽量早把没有可能得到解的状态去掉，这种优化有可能得到解的状态去掉，这种优化搜索的方法叫做搜索的方法叫做剪枝。剪枝。NOIP2004虫食算给定整数给定整数N和三个字符串和三个字符串s1,s2,s3，这三个字符由，这三个
32、字符由N种大写字母组成，相种大写字母组成，相同的大写字母代表相同的数字。这三个字符串表示三个同的大写字母代表相同的数字。这三个字符串表示三个N进制的数字进制的数字a,b,c，且满足，且满足a+b=c，求各个大写字母分别代表什么数字。，求各个大写字母分别代表什么数字。【样例输入样例输入】5ABCEDBDACEEBBAA【样例输出样例输出】1 0 3 4 21234考虑到进位的问题，我们很容易想到从最低位开始搜索。考虑到进位的问题，我们很容易想到从最低位开始搜索。当搜索到第当搜索到第i位时，会有以下几种情况。位时，会有以下几种情况。第第i位位3个数都已确定个数都已确定第第i位位3个数确定了两个个数
33、确定了两个第第i位位3个数确定了一个个数确定了一个第第i位位3个数都未确定个数都未确定如何处理每种情况？1.只需验证是否合法，合法则继续搜索只需验证是否合法，合法则继续搜索2.由两个已知数和上一位的进位确定未知数，由两个已知数和上一位的进位确定未知数，继续搜索继续搜索3.枚举一个未知数，同枚举一个未知数，同2确定另一个未知数，确定另一个未知数，继续搜索继续搜索4.枚举两个未知数，同枚举两个未知数，同2确定另一个未知数，确定另一个未知数，继续搜索继续搜索通过上述处理我们可以通过大部分的数据，但是还是不能拿到满分，通过上述处理我们可以通过大部分的数据，但是还是不能拿到满分，最慢的一个数据要运行最慢
34、的一个数据要运行1分钟左右。分钟左右。如何剪枝在搜索过程中，有些位还没有搜到，但可能这些位上在搜索过程中，有些位还没有搜到，但可能这些位上的的3个数字都已确定，我们就可以先判断这些位是否合个数字都已确定，我们就可以先判断这些位是否合法，这样可以将时间大大缩短，所有数据均可在法，这样可以将时间大大缩短，所有数据均可在1s内内出解出解搜索算法的精髓就在于剪枝，很多题搜索算法的精髓就在于剪枝，很多题目的标准算法都不是搜索，但大部分目的标准算法都不是搜索，但大部分都可以用搜索算法拿到一些分。由于都可以用搜索算法拿到一些分。由于直接搜索效率太低，往往只能得到很直接搜索效率太低，往往只能得到很少的一部分分数，但如果你的剪枝足少的一部分分数，但如果你的剪枝足够强大，拿到大部分分数甚至满分也够强大，拿到大部分分数甚至满分也是有可能的。是有可能的。