[較好的深搜課件]搜索與回溯_課件

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è)位置Procedure search(k:integer）; begin if 到目的地 then 輸出解 ; exit; for I:=1 to 算符種數(shù) do begin 保存結(jié)果 search(k+1）； 恢復(fù)到保存結(jié)果之前的狀態(tài) end; end;深度優(yōu)先搜索的一般框架：Procedure dfs(k,); var begin if 已找到一種方案 then begin print; exit; end;枚舉每種選擇 if 該選擇可行

3、then begin 更改該選擇標(biāo)記 dfs(k+1,）； 回溯 end; end; AB例：設(shè)有A，B，C，D，E五人從事J1，J2，J3，J4，J5五項(xiàng)工作，每人只能從事一項(xiàng)，他們的效益如表所示： J1J2J3J4J5A13111047B13101085C59774D151210115E1011884求最佳安排使效益最高。分析：每人選擇五項(xiàng)工作中的一項(xiàng)，在各種選擇的組合中，找到效益最高的一種組合輸出。const data:array1.5,1.5 of integer =(13,11,10,4,7),(13,10,10,8,5),(5,9,7,7,4), (15,12,10,11,5),(

4、10,11,8,8,4);var i,max:integer; g, f:array1.5 of integer; p:array1.5 of integer;procedure go(step,t:integer); var i:integer; begin if step5 then begin if tmax then begin max:=t; g:=f; end; exit; end; for i:=1 to 5 do if pi=0 then begin fstep:=i; pi:=1; t:=t+datastep,i; go(step+1,t); t:=t-datastep,i;

5、 pi:=0; end; end;begin max:=0; for i:=1 to 5 do pi:=0; go(1,0); writeln; for i:=1 to 5 do write(chr(64+i),:j,gi, :3); writeln; writeln(supply:,max);end.學(xué)校放寒假時(shí)，信息學(xué)競(jìng)賽輔導(dǎo)教師有A，B，C，D，E五本書(shū)，要分給參加培訓(xùn)的張、王，劉、孫、李五位學(xué)生，每人只能一本書(shū)。教師事先讓每個(gè)人將自己喜愛(ài)的書(shū)填寫(xiě)在如下的表中。然后根據(jù)他們填寫(xiě)的表來(lái)分配書(shū)本，希望設(shè)計(jì)一個(gè)程序幫助教師求出所有可能的分書(shū)方案，使每個(gè)學(xué)生都滿意。ABCDE張同學(xué)YY王同學(xué)YY

6、Y劉同學(xué)YY孫同學(xué)Y李同學(xué)YYconst like:array1.5,1.5 of integer =(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:array1.5 of string=(zhang,wang,liu,sun,li);var p,f:array1.5 of integer; t:integer;procedure print; var i:integer; begin for i:=1 to 5 do write(namei,:,chr(64+fi), ); writeln; end;proce

7、dure try(step:integer); var i:integer; begin for i:=1 to 5 do if (pi=0) and (likestep,i0) then begin fstep:=i; pi:=1; if step5 then begin print;t:=t+1;exit;end for i:=1 to 5 do if (pi=0) and (likestep,i0) then begin fstep:=i; pi:=1; try(step+1); pi:=0; end; end;begin fillchar(p,sizeof(p),0); try(1);

8、 writeln(t); end.派對(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è)位置的人與第二個(gè)位置的人時(shí)，他們的身高可能已經(jīng)不符合要求了，但我們?nèi)匀凰阉髁讼氯?。我?/p>

9、可以一邊搜索一邊判斷。依次確定每個(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)b then exit(b) else exit(a); end; procedure dfs(k,tot:longint); begin if (tot*2=sum)or(kn) then begin ans:=min(ans,a

10、bs(sum-tot-tot); exit; end; dfs(k+1,tot+wk);/將第k堆石子并入第一部分 dfs(k+1,tot);/將第k堆石子并入第二部分 end;AB自然數(shù)分解算法減法：枚舉一個(gè)數(shù)，用n減去這個(gè)數(shù)，再枚舉一個(gè)數(shù)，再減去這個(gè)數(shù)，直至減到0加法：枚舉一個(gè)數(shù)，加上這個(gè)數(shù)，再枚舉一個(gè)數(shù)，再加上這個(gè)數(shù)，直至加到n從大到小枚舉，只允許減（加）小于等于last的數(shù)，反之則相反NOIP2009靶形數(shù)獨(dú)有一個(gè)未填滿的數(shù)獨(dú)，求這個(gè)數(shù)獨(dú)填滿后能獲得的最大總分?jǐn)?shù)分?jǐn)?shù)計(jì)算方法：總分?jǐn)?shù)為每個(gè)方格上的分值和完成這個(gè)數(shù)獨(dú)時(shí)填在相應(yīng)格上的數(shù)字的乘積的總和 時(shí)間限制 2s樣例輸入7 0 0 9 0

11、 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)值就更新最優(yōu)值這樣大約可以得35分我們還可以對(duì)上面的想法進(jìn)行改進(jìn)：我們可以先計(jì)算出每個(gè)格子的選擇數(shù)先確定可選擇數(shù)小的格子即先把只

12、有一種選擇的格子確定下來(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í)，所以我們直接退出。這是在比賽中常用的技巧。如何卡步？最簡(jiǎn)單的辦法就是在過(guò)程dfs中加入inc(p);if p then begin writeln(a

13、ns);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ù)最少的格子開(kāi)始搜索。program sudoku; const z:array 1.9,1.9 of longint=(1,1

14、,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,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),

15、 (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 boolean; procedure calc;/計(jì)算總分 var i,j,s:longint; begin s:=0

16、; 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

17、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; gezxx,yy,i:=false; dfs(k+1); hangxx,i:=true; lieyy,i:=true;

18、 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 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.我們可以看出，搜索算法的效率是很低的