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