信息學(xué)競賽搜索專題

1、JSOI搜索算法NJOI搜索 給出初始節(jié)點(diǎn)，要求尋找到符合約束條件的目標(biāo)節(jié)點(diǎn) 給出初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，要求找到從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑。 最優(yōu)解？較優(yōu)解？全部解？NJOI搜索算法 枚舉 廣度優(yōu)先搜索 深度優(yōu)先搜索、回溯 A*NJOI深度優(yōu)先深度優(yōu)先棧Why State?搜索深度優(yōu)先搜索遞歸（系統(tǒng)棧）回溯（人工棧的維護(hù)）什么是棧？NJOIFunction jc(n:integer):integer; begin if n=1 then jc:=1 else jc:=n*jc(n-1); end;Begin write(jc(4);End.432系統(tǒng)棧實(shí)例系統(tǒng)棧實(shí)例NJOI在調(diào)用過程或函數(shù)之

2、前，系統(tǒng)需完成三件事：在調(diào)用過程或函數(shù)之前，系統(tǒng)需完成三件事：將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用過程保存；過程保存；為被調(diào)用過程的局部變量分配存儲區(qū)；為被調(diào)用過程的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)過程的入口。將控制轉(zhuǎn)移到被調(diào)過程的入口。從被調(diào)用過程返回調(diào)用過程之前，系統(tǒng)也應(yīng)完從被調(diào)用過程返回調(diào)用過程之前，系統(tǒng)也應(yīng)完成三件工作：成三件工作：保存被調(diào)過程的計算結(jié)果；保存被調(diào)過程的計算結(jié)果；釋放被調(diào)過程的數(shù)據(jù)區(qū)；釋放被調(diào)過程的數(shù)據(jù)區(qū)；依照被調(diào)過程保存的返回地址將控制轉(zhuǎn)移到調(diào)用過依照被調(diào)過程保存的返回地址將控制轉(zhuǎn)移到調(diào)用過程。當(dāng)有多個過程構(gòu)成嵌

3、套調(diào)用時，按照程。當(dāng)有多個過程構(gòu)成嵌套調(diào)用時，按照“后調(diào)用先后調(diào)用先返回返回”的原則的原則系統(tǒng)棧系統(tǒng)棧NJOI漢諾塔（漢諾塔（tower of Hanoi）問題。）問題。Procedure move(n:integer; A,B,C:char); if n=1 then AC else move(n-1，A，C，B) AC move(n-1，B，A，C) 請寫出系統(tǒng)棧的變化過程請寫出系統(tǒng)棧的變化過程move(3,A,B,C)系統(tǒng)棧例NJOI 線性 讀寫操作都在棧頂 先進(jìn)后出棧的特點(diǎn)NJOI 靜態(tài)數(shù)組Type arr=array1.n of integer; stack=record vec:a

4、rr; top:integer; end;Var s:stack;Var stack:arr; top:integer; n動態(tài)鏈表Type link=node; node=record info:integer; next:link; end;Var stack:link; top:link;棧的定義NJOI操作靜態(tài)數(shù)組(A,top)動態(tài)鏈表(H,top)建立棧測試棧是否為空讀棧頂元素進(jìn)棧(push) 出棧(pop)Top:=0top:=nil;Top=0top=nil;AtopTTop:=top+1; atop:=;？Top:=top-1; ？頭插法棧的基本操作NJOI 入棧

5、順序為1,2,3,n，出棧序列為p1,p2,p3,pn，已知p1=n，則pi=? 入棧順序為1,2,3,n，出棧序列為p1,p2,p3,pn，已知pn=1，則pi=? 棧s初始為空，有元素1,2,3,4,5，現(xiàn)進(jìn)行進(jìn)、進(jìn)、進(jìn)、初、進(jìn)、出、進(jìn)，問：出棧序列，棧頂指針，棧頂元素應(yīng)用舉例NJOI 元素e1,e2,e3,e4,e5,e6依次通過棧s，若出棧順序為2,4,3,6,5,1，則棧s的容量至少為？ 車廂重組：1,2,3,4,5進(jìn)站，第一個到達(dá)出口的是3號車廂，問：可能的排列總數(shù)？應(yīng)用舉例NJOI 中綴表示法 運(yùn)算優(yōu)先級問題、括號的出現(xiàn)改變運(yùn)算順序 后綴表示法（逆波蘭式）-一次掃描棧的簡單應(yīng)用表

6、達(dá)式NJOI 3/5+6 3 5 / 6 + 6-9*(4+3)+5 6 9 4 3 + * - 5 + 轉(zhuǎn)換方法 2*(x+y)/(1-x) (25+x)*(a*(a+b)+b)后綴表示法NJOI 6-9*(4+3)+5 優(yōu)先級運(yùn)算符優(yōu)先級#-1（0（入棧時不作優(yōu)先級比較）+ -1* /2）單獨(dú)處理入棧標(biāo)準(zhǔn)：優(yōu)先級大于棧頂元素優(yōu)先級后綴表示法棧的使用NJOI# -16 - 19* 2( 04+ 13+*-+ 15+ 16943+*-5+6-9*(4+3)+5#NJOI6-9*(4+3)+53496+1(0*2-1#-1763-57+ 15-52中綴棧求解NJOIProcedure try(I

7、); 選擇第I個皇后的位置； if 安全 then (1) 放置第I個皇后； (2) if I=8 then 輸出 else try(I+1); 嘗試下一個位置；棧的應(yīng)用八皇后（遞歸）13455248724648246462758245724885824762425253873837636382537335773625825523828352326374837463472486388247373663724NJOIFor j:=1 to 8 do if bj and cI+j and dI-j then ai:=j; bj:=f; cI+j:=f; dI-j:=f; if I0 do j:=j

8、+1; if j8 then top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top8 then print;八皇后非遞歸NJOIFor j:=1 to 8 do if bj and cI+j and dI-j then ai:=j; bj:=f; cI+j:=f; dI-j:=f; if I0 do j:=j+1; if j 8 then top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top 8 then print;mm全排列非遞歸NJOI 方式 遞歸 回溯 基本框架深度優(yōu)先搜索N

9、JOI 素數(shù)環(huán)：將120這20個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和是一個素數(shù) 走迷宮訓(xùn)練NJOI方向：上下左右NJOI方向：右下左上研究背景研究背景NJOI背包問題簡單枚舉有5個背包（不可拆分），背包的價值(w)、體積(t)各不相等，在容量(tj)范圍內(nèi)，如何選取，使價值最大？For a1:=0 to 1 do for a2:=0 to 1 do for a5:=0 to 1 do P;St:=aI*tI;Sw:=aI*wIIf stmax then 記錄狀態(tài)；有n個背包，問題如何解決？回溯窮舉NJOIA: 123450000000001000100001111111逢1進(jìn)位分析問題找出實(shí)質(zhì)N

10、JOI 初值：0 0 0 0 0 找到需要進(jìn)位的下標(biāo) 如何查找？ N1 結(jié)束標(biāo)記？實(shí)質(zhì)NJOIFor I:=0 to n do aI:=0;While a0=0 do j:=n; while aj=1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:=0; 計算P;打印；程序框架逢1進(jìn)位NJOI N個砝碼（1，3，9，3n-1）可以放在重物一側(cè)，也可以放在砝碼一側(cè)，給出一個重量，問：如何稱？While a0=0 do j:=n; while aj=1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:= 0 ; 計算;-

11、1逢1進(jìn)位NJOI 有n種背包，每種背包有若干個(bi)，While a0=0 do j:=n; while aj= 1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:= 0 ; 計算;Bj相等進(jìn)位NJOI 從1m中任意取出n個，打印所有取法123124125134135145234235245345保證不重復(fù)選擇 升序第n 位進(jìn)位標(biāo)志：m第n-1位進(jìn)位標(biāo)志：m-1第 j 位進(jìn)位標(biāo)志?相等進(jìn)位組合問題JSOI深度優(yōu)先搜索深入應(yīng)用NJOI跳馬周游棋盤問題NJOI 一棵八叉樹八個方向：目前位置(i,j)，下一個位置：可能為：(i+1,j+2),(i-1,j+

12、2),(i-2,j+1),(i-2,j-1),(i-1,j-2),(i+1,j-2),(i+2,j-1),(i+2,j+1) 用二維數(shù)組表示棋盤，未走過的地方設(shè)置為0bi1,j1 0 當(dāng)棋格當(dāng)棋格 ( i1, j 1) 未被占據(jù)未被占據(jù) i 當(dāng)棋格當(dāng)棋格 ( i1, j1) 在第在第 i 次移動中被占據(jù)次移動中被占據(jù) 范圍：未走過的和不越出棋盤邊界的那些位置 為了防止馬跳出棋盤，將棋盤擴(kuò)大二圈，這些位置的表示設(shè)置為-1分析NJOI 縮小搜索范圍避免無效搜索 改變搜索次序在幾個可能到達(dá)的位置中根據(jù)優(yōu)劣條件選擇一個最優(yōu)點(diǎn)來跳馬 剪枝深度優(yōu)先搜索的優(yōu)化方法NJOI 編一個程序，找出一條通過迷宮的路徑

13、。這里編一個程序，找出一條通過迷宮的路徑。這里顯示為顯示為1的單元表示走不通，將一只老鼠從入口處經(jīng)過迷宮到出的單元表示走不通，將一只老鼠從入口處經(jīng)過迷宮到出口處的通路一一打印出來?？谔幍耐芬灰淮蛴〕鰜?。010000001000010001100000111001100000 000000010入口 出口 迷宮問題NJOI基本題 16NJOI 12345678910100010012000010101310100011140011000005000010010找出一個從入口到出口的最短路徑（八個方向）迷宮問題總行數(shù)：總行數(shù)：0m+1, 總列數(shù)：總列數(shù)： 0n+1 111111111111010

14、00100111000010101111010001111100110000011000010010111111111111NJOI 在深搜過程中，記錄搜索步數(shù)并與最小值進(jìn)行比較，記錄當(dāng)前最佳方案，最后打印輸出 能否改進(jìn)？方案1NJOI 從步數(shù)的角度考慮問題，分別列舉出一步能到達(dá)的結(jié)點(diǎn)、兩步能到達(dá)的結(jié)點(diǎn)、發(fā)現(xiàn)的終點(diǎn)肯定是最優(yōu)方案 如何記錄方案？ 記錄每個結(jié)點(diǎn)的來由方案28個方向表示可以用數(shù)組說明：個方向表示可以用數(shù)組說明：10213141506-17-18-1如何記錄探索的蹤跡？如何記錄探索的蹤跡？隊列隊列序號序號 123456X123332Y123144pre012233基本NJOI如何防止

15、重復(fù)探索：將迷宮中的如何防止重復(fù)探索：將迷宮中的0替換為替換為-1隊列中入隊、出隊情況如下表：隊列中入隊、出隊情況如下表：迷宮問題NJOI程序 1 2 3 4 5 6 7 8 91 0 1 0 0 0 1 0 0 12 0 0 0 0 1 0 1 0 13 1 0 1 0 0 0 1 1 14 0 0 1 1 0 0 0 0 05 0 0 0 0 1 0 0 1 0迷宮（用不同的顏色表示步數(shù)）NJOI 與深搜區(qū)別之一：搜索的方向不影響搜索規(guī)模 主要影響因素是什么？ 迷宮變形：起點(diǎn)在迷宮中心、幾乎沒有障礙結(jié)論*迷宮變形NJOI 在寬搜過程中，隊列以幾何數(shù)量級擴(kuò)展，擴(kuò)展層數(shù)越大，對存儲的威脅越大

16、如何對存儲進(jìn)行壓縮？雙向搜索結(jié)論NJOI現(xiàn)要找出一條從現(xiàn)要找出一條從A A到到B B經(jīng)過城市最少的一條路線。經(jīng)過城市最少的一條路線。廣度優(yōu)先遍歷廣度優(yōu)先遍歷: A 應(yīng)用NJOIF,r,隊列初始化；While f=r do 取隊首； 寬搜基本框架NJOIsq1.x:=1 ;sq1.y:=1 ;sq1.pre:=0 ;front :=1; rear :=1 ; mg1,1:=-1 ;while front=rear do x:=sqfront.x ; y:= sqfront.y ; for v:=1 to 8 do I:=x+zv.x ; j:= y+zv.y ; if mgI,j =0 then

17、 rear :=rear+1 ; sqrear.pre:=front ; sqrear.x:=I ; sqrear.y:=j ; mgI,j:= -1 ; if ( i=m ) and (j=n) then print; front := front+1 ; NJOI 設(shè)有數(shù)字設(shè)有數(shù)字2，3，5，7，13，運(yùn)算符號：，運(yùn)算符號：+,*, 且運(yùn)算無優(yōu)先級之分，如且運(yùn)算無優(yōu)先級之分，如2+3*5=25，3*5+2=17，編寫一個程序，給出任意一個，編寫一個程序，給出任意一個整數(shù)整數(shù)n，要求用以上的數(shù)和運(yùn)算符，以最少，要求用以上的數(shù)和運(yùn)算符，以最少的運(yùn)算次數(shù)產(chǎn)生出的運(yùn)算次數(shù)產(chǎn)生出n。 例如：例如：n

18、=7,7=7,（0次運(yùn)算）次運(yùn)算）n=93，93=13*7+2 （2次運(yùn)算次運(yùn)算 ）。）。 例 數(shù)值計算NJOI（1）數(shù)據(jù)的結(jié)構(gòu)：參加運(yùn)算的數(shù)據(jù)、參加運(yùn)算）數(shù)據(jù)的結(jié)構(gòu)：參加運(yùn)算的數(shù)據(jù)、參加運(yùn)算的符號的符號可以用常量數(shù)組可以用常量數(shù)組 data12，data23，參與運(yùn)算數(shù)據(jù)、，參與運(yùn)算數(shù)據(jù)、符號順序符號順序 （2）每步參加運(yùn)算的數(shù)據(jù)及運(yùn)算符號）每步參加運(yùn)算的數(shù)據(jù)及運(yùn)算符號 x, y , t：被加數(shù)、加數(shù)，結(jié)果（：被加數(shù)、加數(shù)，結(jié)果（x ），），t ：從：從哪一步計算到此。哪一步計算到此。 分析算法模式NJOI給出一個整數(shù)給出一個整數(shù)n(n1030)和和k個變換規(guī)則（個變換規(guī)則（k=R and 反面?zhèn)€數(shù)反面?zhèn)€數(shù)=5-R num=R and (10-num)=5-R num=R and num-R=5 0=num-R=5 R=05翻幣問題NJOI 問題求解模式：狀態(tài)問題求解模式：狀態(tài)A-狀態(tài)狀態(tài)B且且AB同同質(zhì)質(zhì) 正向隊列正向隊列Q1（隊列首為起始狀態(tài)（