搜索與回溯課件

1、搜索與回溯對(duì)于某個(gè)問(wèn)題，如果沒(méi)有高效的算法，或者用高效的算法解決有一定的困難，我們常用搜索算法來(lái)求解，即通過(guò)枚舉每一種可行的方案來(lái)找到題目的答案。深度優(yōu)先搜索只要當(dāng)前枚舉到的狀態(tài)可行，就繼續(xù)枚舉下去。當(dāng)找到一種方案或者無(wú)法繼續(xù)枚舉下去時(shí)，就退回到上一狀態(tài)。退回到上一狀態(tài)的過(guò)程叫做回溯。給定n（n10），求1,2,3,n的全排列個(gè)數(shù)。如果一個(gè)數(shù)列含包含這n個(gè)數(shù)，并且這n個(gè)數(shù)都僅出現(xiàn)一次，符合該條件的所有數(shù)列叫做這n個(gè)數(shù)的全排列。如1,2,3三個(gè)元素的全排列為:1,2,3 1,3,2 2,1,32,3,1 3,1,2 3,2,1看一個(gè)簡(jiǎn)單的問(wèn)題什么是全排列？可能有的同學(xué)已經(jīng)注意到了這個(gè)問(wèn)題的答案就

2、是n！=123n如果要輸出所有方案呢？先確定放在第1個(gè)位置的是哪個(gè)數(shù)當(dāng)n個(gè)位置的數(shù)都確定下來(lái)后，我們就得到了一個(gè)方案依次確定第2個(gè)位置，第3個(gè)位置，第n個(gè)位置我們可以用一個(gè)布爾數(shù)組used來(lái)表示每個(gè)數(shù)字是否用過(guò)，用過(guò)為true，未用過(guò)為false。用ansi記錄第i個(gè)位置的數(shù)是多少 for i:=1 to n do if not usedi then /若i未出現(xiàn)過(guò)則在 第k個(gè)位置放i begin usedi:=true; /標(biāo)記 ansk:=i; dfs(k+1);/繼續(xù)搜索 usedi:=false;/回溯 end; end; begin read(n); dfs(1); g

3、ram quanpailie; var n:longint; ans:array 0.10 of longint; used:array 0.10 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;AB 枚舉每種選擇 if 該選擇可行 then begin 更改該選擇標(biāo)記 dfs(k+1,）； 回溯 end; end;深度優(yōu)先搜索的一般框架：Procedure dfs(k,);

4、 var begin if 已找到一種方案 then begin print; exit; end; AB派對(duì) TYVJ P1085Matrix67發(fā)現(xiàn)身高接近的人似乎更合得來(lái)。Matrix67舉辦的派對(duì)共有N(1=Nn then begin f:=true; for j:=1 to n-1 do if abs(ansj-ansj+1)k then begin f:=false; break; end;/檢驗(yàn)1與2，n-1與n if f and (abs(ansn-ans1)=k) then inc(s); exit; end; AB有沒(méi)有更好的做法？我們發(fā)現(xiàn)，當(dāng)我們確定下第一個(gè)位置的人與第二

5、個(gè)位置的人時(shí)，他們的身高可能已經(jīng)不符合要求了，但我們?nèi)匀凰阉髁讼氯ァＮ覀兛梢砸贿吽阉饕贿吪袛?。依次確定每個(gè)位置上的人，檢驗(yàn)一下該位置的人與前一位置的人是否符合要求當(dāng)所有人都已確定，再檢驗(yàn)n位置與1位置的人是否符合要求我們可以把第一個(gè)人固定在第一個(gè)位置再進(jìn)行搜索，這樣最后的答案就不用再除以n for j:=1 to n do if canj and (abs(aj-ansi-1)n then begin if abs(ansn-ans1)n then begin inc(ans); exit; end; for j:=1 to n do if ajand bi+jand ci-jthenAB你有

6、n堆石頭質(zhì)量分別為W1，W2，Wn(W100 000）?，F(xiàn)在需要你將石頭合并為兩部分，使兩部分的質(zhì)量之和最接近。輸入：第一行為整數(shù)n（1n20），表示有n堆石子。第二行n個(gè)整數(shù)，為每堆石子的質(zhì)量。輸出：一行。只需要輸出合并后兩部分的質(zhì)量之和的差。樣例輸入： 樣例輸出：5 35 8 13 27 14石子合并我們可以知道這n堆石子的質(zhì)量和sum。從而只要知道一部分石子的質(zhì)量就可以知道另一部分的質(zhì)量?？梢杂盟阉髅杜e哪些石子放在第一部分，得到第一部分的質(zhì)量a，求出所有方案中abs（sum-a）-a）中最小的即為答案。如果第一部分石子質(zhì)量之和已超過(guò)總質(zhì)量的一半，繼續(xù)向該部分中加入石子，兩部分質(zhì)量差的絕對(duì)

7、值必然增大，沒(méi)有繼續(xù)搜索的必要。 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); gram shizihebing; var ans,sum,i,j,k,n:longint; w:array 0.20 of longint; function min(a,b:longint):longint; begin if ab then exit(b) else exit(a); end; procedure

8、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;AB自然數(shù)拆分 輸入自然數(shù)n，然后將其拆分成由若干數(shù)相加的形式，參與加法運(yùn)算的數(shù)可以重復(fù)。輸入只有一個(gè)整數(shù)n，表示待拆分的自然數(shù)n。 n=0 then dfs(i,tot-i); end;ABNOIP2009靶形數(shù)獨(dú)有一個(gè)未填滿的數(shù)獨(dú)，求這個(gè)數(shù)獨(dú)填滿后能獲得的最大總分?jǐn)?shù)分?jǐn)?shù)計(jì)算

9、方法：總分?jǐn)?shù)為每個(gè)方格上的分值和完成這個(gè)數(shù)獨(dú)時(shí)填在相應(yīng)格上的數(shù)字的乘積的總和 時(shí)間限制 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一個(gè)最簡(jiǎn)單的想法： 我們可以從左上角到右下角枚舉每一個(gè)未填上的格子，再枚舉它可以放哪些數(shù)字，將它填上后繼續(xù)搜索。當(dāng)所有格子都填上后，計(jì)算一下總分，如果總分大于當(dāng)前最優(yōu)值就更新最

10、優(yōu)值這樣大約可以得35分我們還可以對(duì)上面的想法進(jìn)行改進(jìn)：我們可以先計(jì)算出每個(gè)格子的選擇數(shù)先確定可選擇數(shù)小的格子即先把只有一種選擇的格子確定下來(lái)再確定有兩種選擇的格子從而避免搜索到過(guò)多無(wú)法得到可行方案的狀態(tài)這樣大約可以得75分對(duì)于這道題，由于數(shù)據(jù)的原因，如果從右下角到左上角枚舉，可以得到90分左右。如果再加上一個(gè)叫做卡步的東西，我們可以得到100分。什么是卡步？我們發(fā)現(xiàn)搜到一個(gè)可行的方案是很快的，時(shí)間主要用于更新最優(yōu)解?？ú骄褪钱?dāng)執(zhí)行的步數(shù)到達(dá)一定值時(shí)，若程序還沒(méi)有結(jié)束，那么我們就直接輸出搜到的最優(yōu)解，并退出。這個(gè)值很有可能不是最優(yōu)的，但若繼續(xù)搜索下去必然會(huì)超時(shí)，所以我們直接退出。這是在比賽中常

11、用的技巧。如何卡步？最簡(jiǎn)單的辦法就是在過(guò)程dfs中加入inc(p);if p then begin writeln(ans);halt; end;本題可以用搜索+卡步得到100分，很重要的原因是這道題測(cè)試數(shù)據(jù)的特殊性。如果要使程序能通過(guò)任何數(shù)據(jù)，可以采用位運(yùn)算加速搜索和Dancing-links，但這兩種方法在聯(lián)賽范圍內(nèi)基本不會(huì)出現(xiàn)，我們不進(jìn)行深入討論。另外還用一種方法可以得到100分：根據(jù)當(dāng)前狀態(tài)確定每個(gè)格子的選擇數(shù)我們之前有一個(gè)想法是按選擇數(shù)從少到多搜索，但當(dāng)我們確定下一個(gè)格子的數(shù)字后，會(huì)影響其它格子的選擇，使它們的選擇數(shù)減少。所以我們可以在搜索的時(shí)候計(jì)算格子的選擇數(shù)，從當(dāng)前選擇數(shù)最少的格

12、子開始搜索。program sudoku; const 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), (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 1.9,1.9 of longint=(6,6,6,6,6,6,6,6,6), (6,

13、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 0.9,0.9 of longint; hang,lie,ge:array 1.9,1.9 of boolean; x,y:array 0.81 of longint; c:array 0.81 of

14、boolean; procedure calc;/計(jì)算總分 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; fo

15、r 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;/找出當(dāng)前選擇最少的 xx:=xp; yy:=yp; cp:=false; for i:=1 to 9 do /枚舉填哪個(gè)數(shù) if hangxx,i and lieyy,i and gezxx,yy,i then begin mapxx,yy:=i; hangxx,i:=false; lieyy,i:=false;

16、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,j=0

17、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; dfs(1); writeln(ans); end.我們可以看出，搜索算法的效率是很低的，要提高效率，就要盡量早把沒(méi)有可能得到解的狀態(tài)去掉，這種優(yōu)化搜索的方法叫做剪枝。NOIP2019蟲食算給定整數(shù)N和三個(gè)字符串s1,s2,s3，這三個(gè)字符由N種大寫字母組成，相同的大寫字母代表相同的數(shù)字。這三個(gè)字符串表示三個(gè)N進(jìn)制的數(shù)字a,b,c，且滿足a+b=c，求各個(gè)大寫字母分別代表什么數(shù)字?！緲永斎搿?ABCEDBDACEEBBAA【樣例輸出】1 0 3 4 21234考慮到進(jìn)位的問(wèn)題，我們很容易想到從最低位開始搜索。當(dāng)搜索到第i位時(shí)，會(huì)有以下幾種情況。第i位3個(gè)數(shù)都已確定第i位3個(gè)數(shù)確定了兩個(gè)第i位3個(gè)數(shù)確定了一個(gè)第i位3個(gè)數(shù)都未確定如何處理每種情況？1.只需驗(yàn)證是否合法，合法則繼續(xù)搜索2.由兩個(gè)已知數(shù)和上一位的進(jìn)位確定未知數(shù)，繼續(xù)搜索3.枚舉一個(gè)未