2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法一.doc
2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法一在這里介紹兩種基本的搜索算法:深度優(yōu)先搜索和廣度優(yōu)先搜索法,以樹的搜索為例,深度優(yōu)先搜索法是優(yōu)先擴展尚未擴展的且具有最大深度的結點;廣度優(yōu)先搜索法是在擴展完第K層的結點以后才擴展K+1層的結點。深度優(yōu)先搜索法與前面講的回溯法差不多,主要的區(qū)別是回溯法在求解過程中不保留完整的樹結構,而深度優(yōu)先搜索則記下完整的搜索樹,搜索樹起記錄解路徑和狀態(tài)判重的作用。為了減少存儲空間,在深度優(yōu)先搜索中,用標志的方法記錄訪問過的狀態(tài),這種處理方法使得深度優(yōu)先搜索法與回溯法沒什么區(qū)別了。在回溯法中,我們己分析了非遞歸的實現(xiàn)過程,在這里就只討論深度優(yōu)先的遞歸實現(xiàn)方法。深度優(yōu)先搜索的遞歸實現(xiàn)過程:procedure dfs(i); for i:=1 to r do if 子結點mr符合條件then 產(chǎn)生的子結點mr入棧; if 子結點 mr 是目標結點 then 輸出 else dfs(i+1);棧頂元素出棧(即刪去mr);endif;endfor;在講解遞推法時,我們討論了用遞推法解騎土游歷問題,在這里我們再看看如何用深度優(yōu)先搜索法求解此題。搜索算法應用例1騎士游歷:設有一個n*m的棋盤,在棋盤上任一點有一個中國象棋馬,馬走的規(guī)則為:1.馬走日字 2.馬只能向右走。當N,M 輸入之后,找出一條從左下角到右上角的路徑。例如:輸入 N=4,M=4,輸出:路徑的格式:(1,1)->(2,3)->(4,4),若不存在路徑,則輸出"no"算法分析:我們以44的棋盤為例進行分析,用樹形結構表示馬走的所有過程(如下圖),求從起點到終點的路徑,實際上就是從根結點開始深度優(yōu)先搜索這棵樹。馬從(1,1)開始,按深度優(yōu)先搜索法,走一步到達(2,3),判斷是否到達終點,若沒有,則繼續(xù)往前走,再走一步到達(4,4),然后判斷是否到達終點,若到達則退出,搜索過程結束。為了減少搜索次數(shù),在馬走的過程中,判斷下一步所走的位置是否在棋盤上,如果不在棋盤上,則另選一條路徑再走。程序如下:const dx:array1.4of integer=(2,2,1,1); dy:array1.4of integer=(1,-1,2,-2);type map=record x,y:integer; end;var i,n,m:integer; a:array0.50of map;procedure dfs(i:integer);var j:integer;begin for j:=1 to 4 doif (ai-1.x+dxj>0)and(ai-1.x+dxj<=n) and(ai-1.y+dyj>0)and(ai-1.y+dyj<=n) then判斷是否在棋盤上 begin ai.x:=ai-1.x+dxj; ai.y:=ai-1.y+dyj;入棧 if (ai.x=n)and(ai.y=m)then begin write(,1,1,); for j:=2 to i do write(->(,aj.x,aj.y,); halt;輸出結果并退出程序 end; dfs(i+1);搜索下一步 ai.x:=0;ai.y:=0;出棧 end;end;begin a1.x:=1;a1.y:=1; readln(n,m); dfs(2); writeln(no);end.從上面的例子我們可以看出,深度優(yōu)先搜索算法有兩個特點:1、 己產(chǎn)生的結點按深度排序,深度大的結點先得到擴展,即先產(chǎn)生它的子結點。2、 深度大的結點是后產(chǎn)生的,但先得到擴展,即“后產(chǎn)生先擴展”,與棧的工作原理相同,因此用堆棧作為該算法的主要數(shù)據(jù)結構,存儲產(chǎn)生的結點。對于不同的問題,深度優(yōu)先搜索算法基本上是一樣的,但在具體處理方法和編程技巧上又都不相同,甚至會有很大的差別。我們再看看另一個例子。題二 選數(shù)(存盤名:NOIPxxpj)問題描述:已知 n 個整數(shù) x1,x2,xn,以及一個整數(shù) k(kn)。從n 個整數(shù)中任選 k 個整數(shù)相加,可分別得到一系列的和。例如當 n=4,k3,4 個整數(shù)分別為 3,7,12,19 時,可得全部的組合與它們的和為:3712=2237192971219383121934?,F(xiàn)在,要求你計算出和為素數(shù)共有多少種。例如上例,只有一種的和為素數(shù):371929。 輸入:鍵盤輸入,格式為:n , k (1<=n<=20,kn)x1,x2,,xn (1<=xi<=5000000)輸出:屏幕輸出,格式為:一個整數(shù)(滿足條件的種數(shù))。 輸入輸出樣例:輸入:4 3 3 7 12 19輸出:1算法分析:本題是求從n個數(shù)中選k個數(shù)的組合,并使其和為素數(shù)。求解此題時,先用深度優(yōu)先搜索法生成k個數(shù)的組合,再判斷k個數(shù)的和是否為素數(shù),若為素數(shù)則總數(shù)加1。在程序?qū)崿F(xiàn)過程中,用數(shù)組a存放輸入的n個數(shù),用s表示k個數(shù)的和,ans表示和為素數(shù)的個數(shù)。為了避免不必要的搜索,程序?qū)λ阉鬟^程進行了優(yōu)化,限制搜索范圍,在搜索過程dfs(i,m)中,參數(shù)m為第i個數(shù)的上限,下限為n-k+i。源程序:var n,k,i: byte; ans,s:longint; a: array1 . 20 of Longint;procedure prime(s:longint);判斷K個數(shù)的和是否為素數(shù)var i:integer;begin i:=2; while (sqr(i)<=s)and(s mod i<>0) do inc(i); if sqr(i)>s then inc(ans)若為素數(shù)則總數(shù)加1end;procedure dfs(i,m:byte);搜索第i個數(shù), var j:byte;j表示第i個數(shù)的位置begin for j:=m to n-k+i do枚舉第i個數(shù) begin inc(s,aj);入棧 if i=k then prime(s) else dfs(i+1,j+1);繼續(xù)搜第i+1個數(shù) dec(s,aj)出棧 endend;begin readln(n,k); for i:=1 to n do read(ai); ans:=0; s:=0; dfs(1,1); writeln(ans);end.從上面的兩個例子我們可以看出,用遞歸實現(xiàn)深度優(yōu)先搜索比非遞歸更加方便。在使用深度搜索法解題時,搜索的效率并不高,所以要重視對算法的優(yōu)化,盡可能的減少搜索范圍,提高程序的速度。在下一篇中將繼續(xù)介紹另一種搜索方法廣度優(yōu)先搜索法。