廣度優(yōu)先雙向搜索算法

1、第一章 廣度優(yōu)先雙向搜索1.1 廣度雙向搜索的概念所謂雙向搜索指的是搜索沿兩個(gè)力向同時(shí)進(jìn)行：正向搜索：從初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)方向搜索；逆向搜索：從目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)方向搜索；當(dāng)兩個(gè)方向的搜索生成同一子結(jié)點(diǎn)時(shí)終止此搜索過(guò)程。1. 2 廣度雙向搜索算法廣度雙向搜索通常有兩中方法：2. 兩個(gè)方向交替擴(kuò)展3. 選擇結(jié)點(diǎn)個(gè)數(shù)較少的那個(gè)力向先擴(kuò)展方法 2 克服了兩方向結(jié)點(diǎn)的生成速度不平衡的狀態(tài)，明顯提高了效率。算法說(shuō)明：設(shè)置兩個(gè)隊(duì)列c:array0.1,1.maxn of jid ，分別表示正向和逆向的擴(kuò)展隊(duì)列。設(shè)置兩個(gè)頭指針head:array0.1 of integer 分別表示正向和逆向當(dāng)前將擴(kuò)展結(jié)點(diǎn)

2、的頭指針。設(shè)置兩個(gè)尾指針tail:array0.1 of integer 分別表示正向和逆向的尾指針。maxn 表示隊(duì)列最大長(zhǎng)度。算法描述如下：1 .主程序代碼repeat 選擇節(jié)點(diǎn)數(shù)較少且隊(duì)列未空、未滿的方向先擴(kuò)展if (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn) then expand(0);if (tail1<=tail0) and not(head1>=tail1)or(tail1>=maxn) then expand(1); 如果一方搜索終止，繼續(xù)另一方的搜索，直到兩個(gè)方向都終止if not

3、(head0>=tail0)or(tail0>=maxn) then expand(0);if not(head1>=tail1)or(tail1>=maxn) then expand(1);Until (head0>=tail0)or(tail0>=maxn) And (head1>=tail1)or(tail1>=maxn)2 .expand(st:0.1) 程序代碼如下:inc(headst;取出隊(duì)列當(dāng)前待擴(kuò)展的結(jié)點(diǎn)cst,headstfor i:=1 to maxk dobeginif tailst>=maxn then exit;

4、inc(tailst);產(chǎn)生新結(jié)點(diǎn);check(st); 檢查新節(jié)點(diǎn)是否重復(fù)end;3 .check(st:0.1) 程序代碼:for i:=1 to tailst-1 doif cst,tailstp* = cst,ip* then begin dec(tailst);exit end;bool(st); 如果節(jié)點(diǎn)不重復(fù)，再判斷是否到達(dá)目標(biāo)狀態(tài)4 .bool(st:0.1) 程序代碼:for i:=1 to tail1-st doif cst,tailstF.*=c1-st,iA.* then print(st,tailst,i); 如果雙向搜索相遇(即得到同一節(jié)點(diǎn))，則輸出結(jié)果5 .pri

5、nt(st,tail,k) 程序代碼：if st=0 then begin print0(tail);print1(k) end;else begin print0(k);print1(tail) end;6 .print0(m) 程序代碼：if m<>0 then begin print(c0,mA.f);輸出 c0,mA.* end; 輸出正方向上產(chǎn)生的結(jié)點(diǎn)7 .print1(m) 程序代碼;n:=c1,mA.fwhile m<>0begin輸出 c1,nA.*;n:=c1,nA.f;end 輸出反方向上產(chǎn)生的結(jié)點(diǎn)1.3 例題與習(xí)題例 1 ： 8 數(shù)碼難題：2 8

6、31 2 31 6 4 -> 8 4(用最少的步數(shù))7 5 7 6 5程序如下：program num8;const maxn=4000;type jid=recordstr:string9;f:0.maxn;dep:byte;end;bin=0.1;var c:array0.1,1.maxn of Ajid;head,tail:array0.1 of integer;start,goal:string9;procedure init;var i,j:integer;beginstart:='283164705'goal:='123804765'for i

7、:=0 to 1 dofor j:=1 to maxn donew(ci,j);c0,1A.str:=start; c0,1A.f:=0; c0,1A.dep:=0;c1,1A.str:=goal; c1,1A.f:=0; c1,1A.dep:=0;for i:=0 to 1 dobegin headi:=0;taili:=1;end;end;procedure print(st:bin;tail,k:integer);procedure print0(m:integer);beginif m<>0 thenbegin print0(c0,mA.f);writeln(c0,mA.s

8、tr) end;end;procedure print1(m:integer);var n:integer;beginn:=c1,mA.f;while n<>0 dobegin writeln(c1,nA.str); n:=c1,nA.f end;end;beginif st=0 thenbegin writeln('step=',c0,tailA.dep+c1,kA.dep);print0(tail); print1(k);endelse begin writeln('step=',c0,kA.dep+c1,tailA.dep);print0(k)

9、; print1(tail); end ;halt;end;procedure check(st:bin);procedure bool(st:bin);var i:integer;beginfor i:=1 to tail1-st doif cst,tailstA.str=c1-st,iA.str then print(st,tailst,i); end;var i:integer;beginfor i:=1 to tailst-1 doif cst,tailstA.str=cst,iA.str thenbegin dec(tailst);exit end;bool(st);end;proc

10、edure expand(st:bin);var i,p0,p1,d:integer;str0,str1:string9;begininc(headst);str0:=cst,headstA.str;d:=cst,headstA.dep;p0:=pos('0',str0);for i:=1 to 4 dobeginif tailst>=maxn then exit;p1:=p0+2*i-5;if (p1 in 1.9) and not (p0=3) and (p1=4)and not(p0=4)and (p1=3)and not(p0=6)and(p1=7)and not

11、(p0=7)and(p1=6)thenbegininc(tailst);str1:=str0;str1p0:=str1p1;str1p1:='0'cst,tailstF.str:=str1;cst,tailstF.f:=headst;cst,tailstF.dep:=d+1;check(st);end;end;end;begininit;check(0);repeatif (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn)then expand(0);if (tail1<=tail0) and not(

12、head1>=tail1)or(tail1>=maxn)then expand(1);if not(head0>=tail0)or(tail0>=maxn) then expand(0);if not(head1>=tail1)or(tail1>=maxn) then expand(1);Until(head0>=tail0)or(tail0>=maxn)And(head1>=tail1)or(tail1>=maxn);writeln('No answer');end.練習(xí)：1.問(wèn)題描述:已知有兩個(gè)字串A$, B$及一

13、組字串變換的規(guī)則(至多6個(gè)規(guī)則)：A1$-> B1$A2$ -> B2$規(guī)則的含義為：在 人$中的子串 A1$可以變才奐為B1$、A2$可以變才奐為B2$例如：A$ = 'abcd' B$='xyz'變換規(guī)則為：，abc，->，xu，ud>，y，y>，yz，則此時(shí)，A$可以經(jīng)過(guò)一系列的變換變?yōu)锽$,其變換的過(guò)程為：，abcd'-，xud，-，xy，-，xyz，共進(jìn)行了三次變換，使得 A$變換為B$ 輸入:鍵盤輸人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ -變換規(guī)則 . . /所有字符串長(zhǎng)度的上限為20。輸出:輸出至屏幕。格式如下：若在10步（