



下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、算法在信息學奧林匹克競賽中的應用(搜索方法2)在深度優(yōu)先搜索算法中,深度較大的節(jié)點先擴展,深度較小的節(jié)點先擴展,這就是廣度優(yōu)先搜索方法。廣度優(yōu)先搜索的基本算法;bfs計劃;初始化;建立隊列數(shù)據(jù);將隊列頭指針設置為closed :=0;隊列結束指針open :=1;重復Closed增加1,并取出closed指向的節(jié)點進行擴展;對于i:=1至r,開始如果子節(jié)點滿足條件,則開始Open增加1,新節(jié)點存儲在數(shù)據(jù)庫團隊的末尾;如果新節(jié)點和原始節(jié)點有重復,則在此節(jié)點刪除(打開減1)否則,如果新節(jié)點,即目標節(jié)點,輸出并退出;結束 if ;結束 for ;直到關閉=打開;隊列為空當使用廣度優(yōu)先搜索時,最接近根
2、節(jié)點的節(jié)點首先擴展,因此廣度優(yōu)先搜索更適合于尋找步驟數(shù)最少的解。由于深度優(yōu)先使用標記方法,存儲空間大大減少,而廣度優(yōu)先需要保留所有搜索到的節(jié)點。隨著搜索的深入,所需的存儲空間呈指數(shù)級增長。因此,必要時,我們使用雙向搜索來減少搜索空間和存儲空間,如下例所示。廣度優(yōu)先搜索的應用字符串轉換示例(NOIP2002tg)問題描述:已知有兩個字符串A$,B$和一組字符串轉換規(guī)則(最多6個規(guī)則):A1$-B1$ A2$-B2$規(guī)則的含義是A$中的子串A1$可以轉換成B1$并且A2$可以轉換成B2$。例如:A$=ABCD B$=XYZ變換規(guī)則為: ABC-徐- UD - Y - Y - YZ 。此時,可以通過
3、一系列的轉換將$ A轉換成$ B,轉換過程是:“ABCD”“XUD”“XY”回車:鍵盤輸入文件名。文件格式如下:一百美元A1$ B1$ A2$ B2$ |-轉換規(guī)則./所有字符串的最大長度為20。輸出:輸出到屏幕。格式如下:如果可以在10步內(nèi)(包括10步)將$ A轉換為$ B,將輸出最少的轉換步數(shù);否則,輸出“無答案!”樣本輸入和輸出b.in:abcd xyzabc xuud yy yz屏幕顯示:3算法分析:這個問題是尋找最小數(shù)量的轉換步驟。顯然,可以使用廣度優(yōu)先搜索方法。如果直接從初始狀態(tài)搜索目標狀態(tài),則在最壞情況下存儲的節(jié)點數(shù)超過6的10次方,并且搜索空間太大。因此,我們考慮雙向搜索,同時
4、從初始狀態(tài)和目標狀態(tài)搜索到中間狀態(tài)。當他們相遇時,搜尋就結束了。使用雙向搜索時,存儲的節(jié)點數(shù)可能會超過限制。我們將經(jīng)過5步轉換的節(jié)點存儲在正向搜索隊列中。在后向搜索隊列中,因為步驟5中生成的節(jié)點僅用于與前向隊列中的節(jié)點進行比較,所以它們可能不會存儲在隊列中。反向搜索隊列只需要分4步存儲節(jié)點,解決了存儲空間問題。為了使用方便,數(shù)組a1.max用于在程序設計中存儲兩個隊列。正向搜索隊列是1.mid,反向搜索隊列是一個mid.max。st用于存儲搜索方向,st=0表示正向搜索,st=1表示反向搜索,opst和clst分別表示正向搜索源程序:const mid=12000max=16000類型node
5、=記錄s:stringx :字節(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,長度(t);Inc(I);結束;while標記:=I-1;關閉(f);結束;判斷是否達到目標狀態(tài)過程bool(be,ST :
6、 integer);開始對于i:=中間be 1至cl1-st do如果aclst.s=ai.讓我們開始吧writeln(aclst.十. ai.x);停下來;結束;if結束;確定該節(jié)點是否與前一個節(jié)點重復程序檢查(be,ST : integer);開始對于i:=be 1至clst-1 do如果ai.s=aclst.那么開始于12月(clST);出口;結束;布爾(be,ST);結束;擴展生成新節(jié)點過程擴展(be,ST : integer);var i,j,k,lx,ld:integer開始Inc(opST);d:=aopst.s;k:=aopst.x;ld:=長度(d);對于i:=1,標記開始l
7、x:=長度(xi,ST);對于j:=1至ld,開始如果(復制(d,j,lx)=xi,st)然后開始如果(st1)或(k4)然后開始Inc(clST);新(aclST);結束;ifaclst.s:=副本(d,1,j-1) xi,1-st副本(d,j lx,LD);aclst.x:=k 1;檢查(be,ST);檢查重復項結束;if結束;for結束;for結束;bfs程序;var be,k,st:integer開始對于st:=0到1,請開始如果st=0,則be:=0,否則be:=中間值;opST:=be 0;clST:=be 1;新(aclST);aclst.s:=x0,st;aclst.x:=0;結束;for重復如果(op0=cl0)or(acl0.x5)or(op1=cl1)or(acl1.x5);結束。BEGIN初始化;bfs寫下(沒有答案!(結束。兩種搜索算法的比較;搜索方法擴展模式數(shù)據(jù)結構適合解決的問題深度優(yōu)先后一代首次擴張堆可行的解決方案或所有解決方案寬廣第一先生成,先擴展長
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 汽車使用節(jié)能技術課件
- 母嬰護理兒童護理78
- 綠色金融債券2025年市場發(fā)行規(guī)模預測與投資收益研究報告
- 小兒發(fā)熱護理案例分享
- 江蘇職業(yè)規(guī)劃課件
- 江蘇大學橋梁工程課件
- 培訓整體結案報告
- 國際護士節(jié)主題15
- 如何制定一份龍舟隊訓練計劃-方案模板
- 求職者銷售技能培訓課件
- 新能源汽車輕量化設計
- 公司合伙合同樣本
- 外貿(mào)知識培訓課件
- 《食品生產(chǎn)經(jīng)營企業(yè)落實食品安全主體責任監(jiān)督管理規(guī)定》解讀與培訓
- 急危重癥患者轉診流程與管理
- 小學教育學因材施教原則
- 2025智能變電站監(jiān)控系統(tǒng)技術規(guī)范
- 企業(yè)法務管理及風險防范措施
- 光伏 安裝合同范本
- 碳排放與財務績效-深度研究
- DB11-T 2100-2023 承插型盤扣式鋼管腳手架安全選用技術規(guī)程
評論
0/150
提交評論