2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法二.doc
《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法二.doc》由會員分享,可在線閱讀,更多相關《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法二.doc(4頁珍藏版)》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法二 在深度優(yōu)先搜索算法中,深度越大的結點越先得到擴展,若把它改為深度越小的結點越先得到擴展,就是廣度優(yōu)先搜索法。 廣度優(yōu)先搜索基本算法: program bfs; 初始化;建立隊列data; 設隊列首指針closed:=0;隊列尾指針open:=1; repeat closed 增1,取出closed所指結點進行擴展; for i:=1 to r do begin if 子結點符合條件then begin open增1,并把新結點存入數(shù)據(jù)庫隊尾; if新結點與原有結點有重復 then 刪于該結點(open減1) else if 新結點即目標 then 輸出并退出 ; end{if}; end{for}; until closed>=open;{隊列為空} 使用廣度優(yōu)先搜索時,離根結點最近的結點先擴展,所以廣度優(yōu)先搜索法比較適合求步數(shù)最少的解,由于深度優(yōu)先使用了標志法,使得存儲空間大大減少,而廣度優(yōu)先要保留所有搜索過的節(jié)點,隨著搜索程度的加深,所需的存儲空間成指數(shù)增加。因此在必要時我們采用雙向搜索來減少搜索空間和存儲空間,如下面的例子。 廣度優(yōu)先算法應用 例 字串變換(NOIPxxtg) [問題描述]:已知有兩個字串 A$, B$ 及一組字串變換的規(guī)則(至多6個規(guī)則): A1$ -> B1$ A2$ -> B2$ 規(guī)則的含義為:在 A$中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ …。例如:A$=abcd B$=xyz 變換規(guī)則為:‘a(chǎn)bc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 則此時,A$ 可以經(jīng)過一系列的變換變?yōu)?B$,其變換的過程為:‘a(chǎn)bcd’->‘xud’->‘xy’->‘xyz’ 共進行了三次變換,使得 A$ 變換為B$。 [輸入]:鍵盤輸人文件名。文件格式如下: A$ B$ A1$ B1$ \ A2$ B2$ |-> 變換規(guī)則 ... ... / 所有字符串長度的上限為 20。 [輸出]:輸出至屏幕。格式如下: 若在 10 步(包含 10步)以內(nèi)能將 A$ 變換為 B$ ,則輸出最少的變換步數(shù);否則輸出"NO ANSWER!" [輸入輸出樣例] b.in: abcd xyz abc xu ud y y yz 屏幕顯示:3 算法分析:此題是求變換的最少步數(shù),很顯然可以使用廣度優(yōu)先搜索法,如果直接從初狀態(tài)搜到目標狀態(tài),最壞情況下存儲的結點數(shù)超過6的10次方冪,搜索空間過大,因此我們考慮使雙向搜索,同時從初始狀態(tài)和目標狀態(tài)向中間狀態(tài)搜索,當相遇時搜索結束。采用雙向搜索,存儲的結點數(shù)還有可能超限,我們在前向搜索隊列中存儲5步內(nèi)變換的結點,在后向搜索隊列中,由于第5步產(chǎn)生的結點只是用來與前向隊列中的結點比較,所以可以不存儲在隊列中,后向搜索隊列只需存儲4步內(nèi)的結點,這樣就解決了存儲空間問題。 為了使用方便,在程序設計中用一個數(shù)組a[1..max]存儲兩個隊列,前向搜索隊列為a[1..mid],后向搜索隊列為a[mid..max],用st存儲搜索方向,st=0表示前向搜索,st=1表示后向搜索,用op[st]和cl[st]分別表示隊列尾指針和首指針,用be表示隊列起始位置,循環(huán)產(chǎn)生每一個結點,若在10內(nèi)無解退出循環(huán),若在10內(nèi)找到解則輸出解并退出程序。 源程序: const mid=1xx;max=16000; type node=record s:string;x:byte;end; var i,mark:integer; a:array [1..max]of ^node; x:array[0..6,0..1]of string[20]; d,fil:string; op,cl:array [0..1] of integer; procedure Init;{讀取數(shù)據(jù),初始化} var f:text;t:string; begin readln(fil); assign(f,fil);reset(f);i:=0; while not eof(f) do begin readln(f,t); x[i,0]:=copy(t,1,pos( ,t)-1); x[i,1]:=copy(t,pos( ,t)+1,length(t)); inc(i); end;{while} mark:=i-1;close(f); end; {判斷是否到達目標狀態(tài)} procedure bool(be,st:integer); begin for i:=mid-be+1 to cl[1-st] do if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x); halt; end;{if} end; {判斷節(jié)點是否與前面的結點重復} procedure check(be,st:integer); begin for i:=be+1 to cl[st]-1 do if a[i]^.s=a[cl[st]]^.s then begin dec(cl[st]);exit; end; bool(be,st); end; {擴展產(chǎn)生新節(jié)點} procedure expand(be,st:integer); var i,j,k,lx,ld:integer; begin inc(op[st]);d:=a[op[st]]^.s; k:=a[op[st]]^.x;ld:=length(d); for i:=1 to mark do begin lx:=length(x[i,st]); for j:=1 to ld do begin if (copy(d,j,lx)=x[i,st]) then begin if (st<>1)or(k<>4)then begin inc(cl[st]); new(a[cl[st]]); end;{if} a[cl[st]]^.s:= copy(d,1,j-1)+ x[i,1-st]+ copy(d,j+lx,ld); a[cl[st]]^.x:=k+1; check(be,st);{檢查是否重復} end;{if} end;{for} end;{for} end; procedure bfs; var be,k,st:integer; Begin for st:=0 to 1 do begin if st=0 then be:=0 else be:=mid; op[st]:=be+0;cl[st]:=be+1; new(a[cl[st]]); a[cl[st]]^.s:=x[0,st]; a[cl[st]]^.x:=0; end;{for} repeat if (op[0]- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 搜索法二 2019 2020 年高 信息技術 全國青少年 奧林匹克 聯(lián)賽 教案 搜索
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經(jīng)上傳用戶書面授權,請勿作他用。
鏈接地址:http://www.3dchina-expo.com/p-2564503.html