《搜索与回溯》PPT课件.ppt

搜索与回溯,对于某个问题，如果没有高效的算法，或者用高效的算法解决有一定的困难，我们常用搜索算法来求解，即通过枚举每一种可行的方案来找到题目的答案。,深度优先搜索,只要当前枚举到的状态可行，就继续枚举下去。当找到一种方案或者无法继续枚举下去时，就退回到上一状态。退回到上一状态的过程叫做回溯。,给定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个位置的是哪个数,当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:longint; 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 已找到一种方案 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; can: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,有没有更好的做法？ 我们发现，当我们确定下第一个位置的人与第二个位置的人时，他们的身高可能已经不符合要求了，但我们仍然搜索了下去。我们可以一边搜索一边判断。,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); 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,下表给出了一个可行的方案,我们可以依次确定每一行皇后的位置,如果在某一列可以放下一个皇后，我们就在这里放下，并搜索下一行,若无法放下皇后则回到上一行，即回溯,当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),true); 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(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,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,自然数拆分,输入自然数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减去这个数，再枚举一个数，再减去这个数，直至减到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 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 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分,对于这道题，由于数据的原因，如果从右下角到左上角枚举，可以得到90分左右。 如果再加上一个叫做卡步的东西，我们可以得到100分。 什么是卡步？ 我们发现搜到一个可行的方案是很快的，时间主要用于更新最优解。卡步就是当执行的步数到达一定值时，若程序还没有结束，那么我们就直接输出搜到的最优解，并退出。这个值很有可能不是最优的，但若继续搜索下去必然会超时，所以我们直接退出。这是在比赛中常用的技巧。 如何卡步？ 最简单的办法就是在过程dfs中加入 inc(p);if p then begin writeln(ans);halt; end;,本题可以用搜索+卡步得到100分，很重要的原因是这道题测试数据的特殊性。 如果要使程序能通过任何数据，可以采用位运算加速搜索和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,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), (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 then 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:=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:=-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