《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法二》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法二（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、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;
repeat
closed 增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)(o
2、pen減1)
else if 新結(jié)點(diǎn)即目標(biāo) then 輸出并退出 ;
end{if};
end{for};
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è)
3、規(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’ 則此時(shí)，A$ 可以經(jīng)過(guò)一系列的變換變?yōu)?B$，其變換的過(guò)程為：‘a(chǎn)bcd’->‘xud’->‘xy’->‘xyz’ 共進(jìn)行了三次變換，使得 A$ 變換為B$。
[輸入]:鍵盤輸人文件名。文件格式如下：
A$ B$
A1$ B1$ \
A2$ B2$? |-> 變換規(guī)則
... ... /?
所有字符
4、串長(zhǎng)度的上限為 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)搜到目標(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)變
5、換的結(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ù)組a[1..max]存儲(chǔ)兩個(gè)隊(duì)列，前向搜索隊(duì)列為a[1..mid]，后向搜索隊(duì)列為a[mid..max]，用st存儲(chǔ)搜索方向，st=0表示前向搜索，st=1表示后向搜索，用op[st]和cl[st]分別表示隊(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;
6、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 eo
7、f(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;
{判斷是否到達(dá)目標(biāo)狀態(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
8、 writeln(a[cl[st]]^.x+a[i]^.x);
halt;
end;{if}
end;
{判斷節(jié)點(diǎn)是否與前面的結(jié)點(diǎn)重復(fù)}
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;
{擴(kuò)展產(chǎn)生新節(jié)點(diǎn)}
procedure expand(be,st:integer);
var i,j,k,
9、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[s
10、t]]);
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);{檢查是否重復(fù)}
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
11、 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]=cl[0])or(a[cl[0]]^.x>5)or(op[1]>=cl[1])or (a[cl[1]]^.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)先搜索。
2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 搜索法二
