2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法二
2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法二在深度優(yōu)先搜索算法中,深度越大的結(jié)點(diǎn)越先得到擴(kuò)展,若把它改為深度越小的結(jié)點(diǎn)越先得到擴(kuò)展,就是廣度優(yōu)先搜索法。廣度優(yōu)先搜索基本算法:program bfs;初始化;建立隊(duì)列data;設(shè)隊(duì)列首指針closed:=0;隊(duì)列尾指針open:=1;repeatclosed 增1,取出closed所指結(jié)點(diǎn)進(jìn)行擴(kuò)展; for i:=1 to r do begin if 子結(jié)點(diǎn)符合條件then begin open增1,并把新結(jié)點(diǎn)存入數(shù)據(jù)庫(kù)隊(duì)尾;if新結(jié)點(diǎn)與原有結(jié)點(diǎn)有重復(fù) then 刪于該結(jié)點(diǎn)(open減1)else if 新結(jié)點(diǎn)即目標(biāo) then 輸出并退出 ; endif; endfor;until closed>=open;隊(duì)列為空使用廣度優(yōu)先搜索時(shí),離根結(jié)點(diǎn)最近的結(jié)點(diǎn)先擴(kuò)展,所以廣度優(yōu)先搜索法比較適合求步數(shù)最少的解,由于深度優(yōu)先使用了標(biāo)志法,使得存儲(chǔ)空間大大減少,而廣度優(yōu)先要保留所有搜索過(guò)的節(jié)點(diǎn),隨著搜索程度的加深,所需的存儲(chǔ)空間成指數(shù)增加。因此在必要時(shí)我們采用雙向搜索來(lái)減少搜索空間和存儲(chǔ)空間,如下面的例子。廣度優(yōu)先算法應(yīng)用例 字串變換(NOIPxxtg)問(wèn)題描述:已知有兩個(gè)字串 A$, B$ 及一組字串變換的規(guī)則(至多6個(gè)規(guī)則):A1$ -> B1$A2$ -> B2$ 規(guī)則的含義為:在 A$中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ 。例如:A$'abcd'B$'xyz' 變換規(guī)則為:abc->xuud->yy->yz則此時(shí),A$ 可以經(jīng)過(guò)一系列的變換變?yōu)?B$,其變換的過(guò)程為:abcd->xud->xy->xyz 共進(jìn)行了三次變換,使得 A$ 變換為B$。輸入:鍵盤(pán)輸人文件名。文件格式如下:A$ B$A1$ B1$ A2$ B2$ |-> 變換規(guī)則. . / 所有字符串長(zhǎng)度的上限為 20。輸出:輸出至屏幕。格式如下:若在 10 步(包含 10步)以內(nèi)能將 A$ 變換為 B$ ,則輸出最少的變換步數(shù);否則輸出"NO ANSWER!"輸入輸出樣例b.in:abcd xyzabc xuud yy yz屏幕顯示:3算法分析:此題是求變換的最少步數(shù),很顯然可以使用廣度優(yōu)先搜索法,如果直接從初狀態(tài)搜到目標(biāo)狀態(tài),最壞情況下存儲(chǔ)的結(jié)點(diǎn)數(shù)超過(guò)6的10次方冪,搜索空間過(guò)大,因此我們考慮使雙向搜索,同時(shí)從初始狀態(tài)和目標(biāo)狀態(tài)向中間狀態(tài)搜索,當(dāng)相遇時(shí)搜索結(jié)束。采用雙向搜索,存儲(chǔ)的結(jié)點(diǎn)數(shù)還有可能超限,我們?cè)谇跋蛩阉麝?duì)列中存儲(chǔ)5步內(nèi)變換的結(jié)點(diǎn),在后向搜索隊(duì)列中,由于第5步產(chǎn)生的結(jié)點(diǎn)只是用來(lái)與前向隊(duì)列中的結(jié)點(diǎn)比較,所以可以不存儲(chǔ)在隊(duì)列中,后向搜索隊(duì)列只需存儲(chǔ)4步內(nèi)的結(jié)點(diǎn),這樣就解決了存儲(chǔ)空間問(wèn)題。為了使用方便,在程序設(shè)計(jì)中用一個(gè)數(shù)組a1.max存儲(chǔ)兩個(gè)隊(duì)列,前向搜索隊(duì)列為a1.mid,后向搜索隊(duì)列為amid.max,用st存儲(chǔ)搜索方向,st=0表示前向搜索,st=1表示后向搜索,用opst和clst分別表示隊(duì)列尾指針和首指針,用be表示隊(duì)列起始位置,循環(huán)產(chǎn)生每一個(gè)結(jié)點(diǎn),若在10內(nèi)無(wú)解退出循環(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.maxof node; x:array0.6,0.1of string20; 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); xi,0:=copy(t,1,pos(' ',t)-1); xi,1:=copy(t,pos(' ',t)+1,length(t); inc(i); end;while mark:=i-1;close(f);end;判斷是否到達(dá)目標(biāo)狀態(tài)procedure bool(be,st:integer);begin for i:=mid-be+1 to cl1-st do if aclst.s=ai.s then begin writeln(aclst.x+ai.x); halt; end;ifend;判斷節(jié)點(diǎn)是否與前面的結(jié)點(diǎn)重復(fù)procedure check(be,st:integer);begin for i:=be+1 to clst-1 doif ai.s=aclst.s thenbegin dec(clst);exit; end; bool(be,st);end; 擴(kuò)展產(chǎn)生新節(jié)點(diǎn)procedure expand(be,st:integer);var i,j,k,lx,ld:integer;begin inc(opst);d:=aopst.s; k:=aopst.x;ld:=length(d); for i:=1 to mark do begin lx:=length(xi,st); for j:=1 to ld do begin if (copy(d,j,lx)=xi,st) then begin if (st<>1)or(k<>4)then begin inc(clst); new(aclst); end;if aclst.s:= copy(d,1,j-1)+ xi,1-st+ copy(d,j+lx,ld); aclst.x:=k+1; check(be,st);檢查是否重復(fù) end;if end;for end;forend;procedure bfs;var be,k,st:integer;Begin for st:=0 to 1 do begin if st=0 then be:=0 else be:=mid; opst:=be+0;clst:=be+1; new(aclst); aclst.s:=x0,st; aclst.x:=0; end;for repeat if (op0<cl0)and(acl0.x<=5)then expand(0,0); if (op1<cl1)and(acl1.x<=5)then expand(mid,1); until(op0>=cl0)or(acl0.x>5)or(op1>=cl1)or (acl1.x>5);End;BEGIN init;bfs;writeln('NO ANSWER!')END.兩種搜索算法的比較:搜索方式擴(kuò)展方式數(shù)據(jù)結(jié)構(gòu)適合求解的問(wèn)題深度優(yōu)先后產(chǎn)生先擴(kuò)展棧可行解或所有解廣度優(yōu)先先產(chǎn)生先擴(kuò)展隊(duì)列最優(yōu)解在選擇搜索方式時(shí),并不是完全遵循以上原則,具體還是要根據(jù)題目的要求而定。在求最優(yōu)解時(shí),如果搜索的深度不大,我們也可以考慮使用深度優(yōu)先搜索;在求解可行解時(shí),如果搜索的深度沒(méi)有限制,或者搜索的代價(jià)與搜索的深度成正比,我們也應(yīng)該使用廣度優(yōu)先搜索。