高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法二

1、算法在信息學(xué)奧林匹克競(jìng)賽中的應(yīng)用(搜索方法2)在深度優(yōu)先搜索算法中，深度較大的節(jié)點(diǎn)先擴(kuò)展，深度較小的節(jié)點(diǎn)先擴(kuò)展，這就是廣度優(yōu)先搜索方法。廣度優(yōu)先搜索的基本算法；bfs計(jì)劃；初始化；建立隊(duì)列數(shù)據(jù)；將隊(duì)列頭指針設(shè)置為closed :=0；隊(duì)列結(jié)束指針open :=1；重復(fù)Closed增加1，并取出closed指向的節(jié)點(diǎn)進(jìn)行擴(kuò)展；對(duì)于i:=1至r，開始如果子節(jié)點(diǎn)滿足條件，則開始Open增加1，新節(jié)點(diǎn)存儲(chǔ)在數(shù)據(jù)庫團(tuán)隊(duì)的末尾；如果新節(jié)點(diǎn)和原始節(jié)點(diǎn)有重復(fù)，則在此節(jié)點(diǎn)刪除(打開減1)否則，如果新節(jié)點(diǎn)，即目標(biāo)節(jié)點(diǎn)，輸出并退出；結(jié)束 if ；結(jié)束 for ；直到關(guān)閉=打開；隊(duì)列為空當(dāng)使用廣度優(yōu)先搜索時(shí)，最接近根

2、節(jié)點(diǎn)的節(jié)點(diǎn)首先擴(kuò)展，因此廣度優(yōu)先搜索更適合于尋找步驟數(shù)最少的解。由于深度優(yōu)先使用標(biāo)記方法，存儲(chǔ)空間大大減少，而廣度優(yōu)先需要保留所有搜索到的節(jié)點(diǎn)。隨著搜索的深入，所需的存儲(chǔ)空間呈指數(shù)級(jí)增長(zhǎng)。因此，必要時(shí)，我們使用雙向搜索來減少搜索空間和存儲(chǔ)空間，如下例所示。廣度優(yōu)先搜索的應(yīng)用字符串轉(zhuǎn)換示例(NOIP2002tg)問題描述:已知有兩個(gè)字符串A$，B$和一組字符串轉(zhuǎn)換規(guī)則(最多6個(gè)規(guī)則):A1$-B1$ A2$-B2$規(guī)則的含義是A$中的子串A1$可以轉(zhuǎn)換成B1$并且A2$可以轉(zhuǎn)換成B2$。例如：A$=ABCD B$=XYZ變換規(guī)則為： ABC-徐- UD - Y - Y - YZ 。此時(shí)，可以通過

3、一系列的轉(zhuǎn)換將$ A轉(zhuǎn)換成$ B，轉(zhuǎn)換過程是：“ABCD”“XUD”“XY”回車:鍵盤輸入文件名。文件格式如下：一百美元A1$ B1$ A2$ B2$ |-轉(zhuǎn)換規(guī)則./所有字符串的最大長(zhǎng)度為20。輸出:輸出到屏幕。格式如下：如果可以在10步內(nèi)(包括10步)將$ A轉(zhuǎn)換為$ B，將輸出最少的轉(zhuǎn)換步數(shù)；否則，輸出“無答案！”樣本輸入和輸出b.in:abcd xyzabc xuud yy yz屏幕顯示：3算法分析：這個(gè)問題是尋找最小數(shù)量的轉(zhuǎn)換步驟。顯然，可以使用廣度優(yōu)先搜索方法。如果直接從初始狀態(tài)搜索目標(biāo)狀態(tài)，則在最壞情況下存儲(chǔ)的節(jié)點(diǎn)數(shù)超過6的10次方，并且搜索空間太大。因此，我們考慮雙向搜索，同時(shí)

4、從初始狀態(tài)和目標(biāo)狀態(tài)搜索到中間狀態(tài)。當(dāng)他們相遇時(shí)，搜尋就結(jié)束了。使用雙向搜索時(shí)，存儲(chǔ)的節(jié)點(diǎn)數(shù)可能會(huì)超過限制。我們將經(jīng)過5步轉(zhuǎn)換的節(jié)點(diǎn)存儲(chǔ)在正向搜索隊(duì)列中。在后向搜索隊(duì)列中，因?yàn)椴襟E5中生成的節(jié)點(diǎn)僅用于與前向隊(duì)列中的節(jié)點(diǎn)進(jìn)行比較，所以它們可能不會(huì)存儲(chǔ)在隊(duì)列中。反向搜索隊(duì)列只需要分4步存儲(chǔ)節(jié)點(diǎn)，解決了存儲(chǔ)空間問題。為了使用方便，數(shù)組a1.max用于在程序設(shè)計(jì)中存儲(chǔ)兩個(gè)隊(duì)列。正向搜索隊(duì)列是1.mid，反向搜索隊(duì)列是一個(gè)mid.max。st用于存儲(chǔ)搜索方向，st=0表示正向搜索，st=1表示反向搜索，opst和clst分別表示正向搜索源程序：const mid=12000max=16000類型node

5、=記錄s:stringx :字節(jié)；結(jié)束；varI，mark:integera :陣列1.node；x:array0.6，0.字符串20的1；d，fil:stringop，cl:array 0.1的整數(shù)；初始化過程；讀取數(shù)據(jù)，初始化var f:textt:string開始read ln(fil)；分配(f，fil)；重置(f)；I :=0；而不是eof(f)開始readln(f，t)；xi，0:=副本(t，1，pos(，t)-1)；xi，1:=副本(t，pos(，t) 1，長(zhǎng)度(t)；Inc(I)；結(jié)束；while標(biāo)記：=I-1；關(guān)閉(f)；結(jié)束；判斷是否達(dá)到目標(biāo)狀態(tài)過程bool(be，ST :

6、 integer)；開始對(duì)于i:=中間be 1至cl1-st do如果aclst.s=ai.讓我們開始吧writeln(aclst.十. ai.x)；停下來；結(jié)束；if結(jié)束；確定該節(jié)點(diǎn)是否與前一個(gè)節(jié)點(diǎn)重復(fù)程序檢查(be，ST : integer)；開始對(duì)于i:=be 1至clst-1 do如果ai.s=aclst.那么開始于12月(clST)；出口；結(jié)束；布爾(be，ST)；結(jié)束；擴(kuò)展生成新節(jié)點(diǎn)過程擴(kuò)展(be，ST : integer)；var i，j，k，lx，ld:integer開始Inc(opST)；d:=aopst.s；k:=aopst.x；ld:=長(zhǎng)度(d)；對(duì)于i:=1，標(biāo)記開始l

7、x:=長(zhǎng)度(xi，ST)；對(duì)于j:=1至ld，開始如果(復(fù)制(d，j，lx)=xi，st)然后開始如果(st1)或(k4)然后開始Inc(clST)；新(aclST)；結(jié)束；ifaclst.s:=副本(d，1，j-1) xi，1-st副本(d，j lx，LD)；aclst.x:=k 1；檢查(be，ST)；檢查重復(fù)項(xiàng)結(jié)束；if結(jié)束；for結(jié)束；for結(jié)束；bfs程序；var be，k，st:integer開始對(duì)于st:=0到1，請(qǐng)開始如果st=0，則be:=0，否則be:=中間值；opST:=be 0；clST:=be 1；新(aclST)；aclst.s:=x0,st；aclst.x:=0；結(jié)束；for重復(fù)如果(op0=cl0)or(acl0.x5)or(op1=cl1)or(acl1.x5)；結(jié)束。BEGIN初始化；bfs寫下(沒有答案！(結(jié)束。兩種搜索算法的比較；搜索方法擴(kuò)展模式數(shù)據(jù)結(jié)構(gòu)適合解決的問題深度優(yōu)先后一代首次擴(kuò)張堆可行的解決方案或所有解決方案寬廣第一先生成，先擴(kuò)展長(zhǎng)