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

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

2、n！=123n如果要輸出所有方案呢？先確定放在第1個位置的是哪個數(shù)當n個位置的數(shù)都確定下來后，我們就得到了一個方案依次確定第2個位置，第3個位置，第n個位置Procedure search(k:integer）; begin if 到目的地 then 輸出解 ; exit; for I:=1 to 算符種數(shù) do begin 保存結(jié)果 search(k+1）； 恢復到保存結(jié)果之前的狀態(tài) end; end;深度優(yōu)先搜索的一般框架：Procedure dfs(k,); var begin if 已找到一種方案 then begin print; exit; end;枚舉每種選擇 if 該選擇可行

3、then begin 更改該選擇標記 dfs(k+1,）； 回溯 end; end; AB例：設(shè)有A，B，C，D，E五人從事J1，J2，J3，J4，J5五項工作，每人只能從事一項，他們的效益如表所示： J1J2J3J4J5A13111047B13101085C59774D151210115E1011884求最佳安排使效益最高。分析：每人選擇五項工作中的一項，在各種選擇的組合中，找到效益最高的一種組合輸出。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.學校放寒假時，信息學競賽輔導教師有A，B，C，D，E五本書，要分給參加培訓的張、王，劉、孫、李五位學生，每人只能一本書。教師事先讓每個人將自己喜愛的書填寫在如下的表中。然后根據(jù)他們填寫的表來分配書本，希望設(shè)計一個程序幫助教師求出所有可能的分書方案，使每個學生都滿意。ABCDE張同學YY王同學YY

6、Y劉同學YY孫同學Y李同學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.派對 TYVJ P1085Matrix67發(fā)現(xiàn)身高接近的人似乎更合得來。Matrix67舉辦的派對共有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;/檢驗1與2，n-1與n if f and (abs(ansn-ans1)=k) then inc(s); exit; end; AB有沒有更好的做法？我們發(fā)現(xiàn)，當我們確定下第一個位置的人與第二個位置的人時，他們的身高可能已經(jīng)不符合要求了，但我們?nèi)匀凰阉髁讼氯?。我?/p>

9、可以一邊搜索一邊判斷。依次確定每個位置上的人，檢驗一下該位置的人與前一位置的人是否符合要求當所有人都已確定，再檢驗n位置與1位置的人是否符合要求我們可以把第一個人固定在第一個位置再進行搜索，這樣最后的答案就不用再除以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ù)分解算法減法：枚舉一個數(shù)，用n減去這個數(shù)，再枚舉一個數(shù)，再減去這個數(shù)，直至減到0加法：枚舉一個數(shù)，加上這個數(shù)，再枚舉一個數(shù)，再加上這個數(shù)，直至加到n從大到小枚舉，只允許減（加）小于等于last的數(shù)，反之則相反NOIP2009靶形數(shù)獨有一個未填滿的數(shù)獨，求這個數(shù)獨填滿后能獲得的最大總分數(shù)分數(shù)計算方法：總分數(shù)為每個方格上的分值和完成這個數(shù)獨時填在相應(yīng)格上的數(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一個最簡單的想法： 我們可以從左上角到右下角枚舉每一個未填上的格子，再枚舉它可以放哪些數(shù)字，將它填上后繼續(xù)搜索。當所有格子都填上后，計算一下總分，如果總分大于當前最優(yōu)值就更新最優(yōu)值這樣大約可以得35分我們還可以對上面的想法進行改進：我們可以先計算出每個格子的選擇數(shù)先確定可選擇數(shù)小的格子即先把只

12、有一種選擇的格子確定下來再確定有兩種選擇的格子從而避免搜索到過多無法得到可行方案的狀態(tài)這樣大約可以得75分對于這道題，由于數(shù)據(jù)的原因，如果從右下角到左上角枚舉，可以得到90分左右。如果再加上一個叫做卡步的東西，我們可以得到100分。什么是卡步？我們發(fā)現(xiàn)搜到一個可行的方案是很快的，時間主要用于更新最優(yōu)解?？ú骄褪钱攬?zhí)行的步數(shù)到達一定值時，若程序還沒有結(jié)束，那么我們就直接輸出搜到的最優(yōu)解，并退出。這個值很有可能不是最優(yōu)的，但若繼續(xù)搜索下去必然會超時，所以我們直接退出。這是在比賽中常用的技巧。如何卡步？最簡單的辦法就是在過程dfs中加入inc(p);if p then begin writeln(a

13、ns);halt; end;本題可以用搜索+卡步得到100分，很重要的原因是這道題測試數(shù)據(jù)的特殊性。如果要使程序能通過任何數(shù)據(jù)，可以采用位運算加速搜索和Dancing-links，但這兩種方法在聯(lián)賽范圍內(nèi)基本不會出現(xiàn)，我們不進行深入討論。另外還用一種方法可以得到100分：根據(jù)當前狀態(tài)確定每個格子的選擇數(shù)我們之前有一個想法是按選擇數(shù)從少到多搜索，但當我們確定下一個格子的數(shù)字后，會影響其它格子的選擇，使它們的選擇數(shù)減少。所以我們可以在搜索的時候計算格子的選擇數(shù)，從當前選擇數(shù)最少的格子開始搜索。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;/計算總分 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;/找出當前選擇最少的 xx:=xp; yy:=yp; cp:=false; for i:=1 to 9 do /枚舉填哪個數(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.我們可以看出，搜索算法的效率是很低的