資源描述：
《廣度優(yōu)先搜索優(yōu)化.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、廣度優(yōu)先雙向搜索?1.1廣度雙向搜索的概念所謂雙向搜索指的是搜索沿兩個力向同時進行：正向搜索：從初始結點向目標結點方向搜索；逆向搜索：從目標結點向初始結點方向搜索；當兩個方向的搜索生成同一子結點時終止此搜索過程。1.2廣度雙向搜索算法廣度雙向搜索通常有兩中方法：1.兩個方向交替擴展2.選擇結點個數(shù)較少的那個方向先擴展．方法2克服了兩方向結點的生成速度不平衡的狀態(tài)，明顯提高了效率。?算法說明：設置兩個隊列c:array[0..1,1..maxn]ofjid，分別表示正向和逆向的擴展隊列。設置兩個頭指針head:array[0.
2、.1]ofinteger分別表示正向和逆向當前將擴展結點的頭指針。設置兩個尾指針tail:array[0..1]ofinteger分別表示正向和逆向的尾指針。maxn表示隊列最大長度。算法描述如下：1.主程序代碼?repeat?{選擇節(jié)點數(shù)較少且隊列未空、未滿的方向先擴展}??if(tail[0]<=tail[1])andnot((head[0]>=tail[0])or(tail[0]>=maxn))thenexpand(0);?if(tail[1]<=tail[0])andnot((head[1]>=tail[1])or(
3、tail[1]>=maxn))thenexpand(1);?{如果一方搜索終止，繼續(xù)另一方的搜索，直到兩個方向都終止}?ifnot((head[0]>=tail[0])or(tail[0]>=maxn))thenexpand(0);?ifnot((head[1]>=tail[1])or(tail[1]>=maxn))thenexpand(1);?Until((head[0]>=tail[0])or(tail[0]>=maxn))??And((head[1]>=tail[1])or(tail[1]>=maxn))2.expan
4、d(st:0..1)程序代碼如下:?inc(head[st];?取出隊列當前待擴展的結點c[st,head[st]]?fori:=1tomaxkdo???begin??????iftail[st]>=maxnthenexit;?????inc(tail[st]);????產(chǎn)生新結點;?????check(st);{檢查新節(jié)點是否重復}???end;3.check(st:0..1)程序代碼:?fori:=1totail[st]-1do?????ifc[st,tail[st]]^.*=c[st,i]^.*thenbegindec
5、(tail[st]);exitend;???bool(st);{如果節(jié)點不重復，再判斷是否到達目標狀態(tài)}?4.bool(st:0..1)程序代碼:?fori:=1totail[1-st]do???ifc[st,tail[st]]^.*=c[1-st,i]^.*then?print(st,tail[st],i);????{如果雙向搜索相遇（即得到同一節(jié)點），則輸出結果}135.print(st,tail,k)程序代碼：ifst=0thenbeginprint0(tail);print1(k)end;???????elsebeg
6、inprint0(k);print1(tail)end;6.print0(m)程序代碼：?ifm<>0thenbeginprint(c[0,m]^.f);輸出c[0,m]^.*end;{輸出正方向上產(chǎn)生的結點}7.print1(m)程序代碼;?n:=c[1,m]^.f?whilem<>0?begin???輸出c[1,n]^.*;??n:=c[1,n]^.f;?end{輸出反方向上產(chǎn)生的結點}1.3例題與習題?例1：8數(shù)碼難題：???????????????283???123???????????????164->8??4（用
7、最少的步數(shù)）???????????????7??5???765程序如下：programnum8;constmaxn=4000;typejid=record????str:string[9];????f:0..maxn;????dep:byte;????end;???bin=0..1;varc:array[0..1,1..maxn]of^jid;???head,tail:array[0..1]ofinteger;???start,goal:string[9];procedureinit;vari,j:integer;begin
8、?start:='283164705';?goal:='123804765';?fori:=0to1do?forj:=1tomaxndo???new(c[i,j]);?c[0,1]^.str:=start;c[0,1]^.f:=0;c[0,1]^.dep:=0;?c[1,1]^.str:=
