網(wǎng)上找的一些算法搜索滾動(dòng)廣搜

1、滾動(dòng)廣搜我們知道樸素廣搜的空間浪費(fèi)很嚴(yán)重，原因很簡單，樸素廣搜將從初始節(jié)點(diǎn)開始可以達(dá)到的所有狀態(tài)全都下來了，而這樣需要消耗的空間代價(jià)是指數(shù)級的。所有使用廣搜時(shí)，空間就顯得很寶貴。于是我們開始尋找對狀態(tài)儲存的優(yōu)化，以減小對空間的消耗。一類典型的題目（求迷宮中到達(dá)某一個(gè)位置的最少步數(shù)），可以用到一種思想滾動(dòng)廣搜。滾動(dòng)廣搜的思想就是用到兩個(gè)表來儲存前一個(gè)階段可以達(dá)到的所有狀態(tài)和當(dāng)前階段可以達(dá)到的所有狀態(tài)。因?yàn)檫@一步能到達(dá)的所有位置只由上一步的位置決定，而所有的位置的集合規(guī)模是 n*m（分別表示迷宮的長和寬）。我們只需要開兩個(gè)大小為 n*m 的表就可以保證能所有可能達(dá)到的位置了。每次取出前一階段所有狀

2、態(tài)節(jié)點(diǎn)，并按照產(chǎn)生式規(guī)則對其擴(kuò)展并存入當(dāng)前階段的表內(nèi)。然后通過 now:=1-now 不斷切換前一階段與當(dāng)前階段，（注意：每次要對當(dāng)前階段的表和標(biāo)記數(shù)組進(jìn)行清空）。1下面給出滾動(dòng)廣搜的數(shù)據(jù)結(jié)構(gòu):type rec=record節(jié)點(diǎn)的描述，包括橫縱、坐標(biāo)，根據(jù)題目不同可適當(dāng)添加 x,y:integer;end;var q:array0.1,1.maxn*maxm of rec; 0、1 分別表示當(dāng)前階段和前一個(gè)階段 r:array0.1 of longint; 兩個(gè)表對應(yīng)的尾指針 used:array1.maxn,1.maxm of Boolean;標(biāo)記(u,v)是否以可到達(dá)2以下是滾動(dòng)廣搜的pr

3、ocedure rollbfs;var i,f,u,v:integer;begin算法部分。now:=0;rnow:=1;qnow,1.x:=fx;qnow,1.y:=fy;初始化，將起點(diǎn)位置入隊(duì) repeatnow:=1-now; rnow:=0; fillchar(used,sizeof(used),0);切換到當(dāng)前階段，置隊(duì)列為空，將 used 標(biāo)記數(shù)組清空for f:=1 to r1-now do取出前一階段的所有狀態(tài)節(jié)點(diǎn)并對其進(jìn)行擴(kuò)展 beginfor i:=1 to maxway do枚舉對于該位置所有可能的擴(kuò)展方向 beginu:=q1-now,f.x+ai;a,b 分別為橫、縱

4、方向上的增量v:=q1-now,f.y+bi;if (mapu,v可達(dá)到) and(not(usedu,v)(u,v)未被標(biāo)記過 then begininc(rnow); if (rnown*m) then exit; qnow,rnow.x:=u;，qnow,rnow.y:=v; usedu,v:=true;if (u=ex)and(v=ey) then如果達(dá)到終點(diǎn)則打應(yīng)并結(jié)束算法begin writeln(time);close(output);halt; end;end; end;end; until 01;end;參考題目：穿越線最后的戰(zhàn)犯SEARCH迷宮附：最后的戰(zhàn)犯題目描述：話說

5、Lucky 和 Feli 以 3721犬蠢一狼（以下簡稱小犬）在全軍為誘餌， 滅了大批日軍。但頑固的日軍軍官小之后仍然不肯認(rèn)輸。他躲在山區(qū)的一個(gè)巖洞中，等待日軍的救援。他妄圖憑借復(fù)雜的地形躲避我軍的追蹤。于是，總部派出足智多謀的 Feli前往巖洞搜尋小犬。Feli 來到巖洞復(fù)雜，為一個(gè)正方形，其中布滿了區(qū)域或者是空地，或者是不可逾越的，發(fā)現(xiàn)巖洞其實(shí)是一個(gè)巨大的迷宮。迷宮地形極為物。迷宮可以分為 N*N（2N100）個(gè)區(qū)域，每個(gè)物。小犬就躲藏在其中某一個(gè)區(qū)域內(nèi)。由于小犬已經(jīng)忍受了幾天的饑餓，F(xiàn)eli 進(jìn)入迷宮時(shí)他已經(jīng)失去思維處于迷亂狀態(tài)。小犬每秒鐘只會沿著他的方向直線前進(jìn)，如果遇到物或者迷宮邊界

6、，他會立刻向右轉(zhuǎn) 90 度（花去時(shí)間），繼續(xù)沿直線前進(jìn)（初始方向向北）。Feli 每秒鐘可以決定往哪個(gè)方向走。如果同一時(shí)刻 Feli 與小犬位于同一個(gè)區(qū)域，或者相鄰的區(qū)域（非對角線相鄰），F(xiàn)eli 可以立刻將小犬抓住。Feli 本來打算先確定小犬的位置，然后沿最短路線抓住他，但是 Feli 前進(jìn)時(shí)小犬同時(shí)也在移動(dòng)，就不能采取這種方法了。請你幫助 Feli 確定所用的時(shí)間最短。案，使 Feli 抓獲小犬?dāng)?shù)據(jù)說明：輸入數(shù)據(jù)第一行是一個(gè)整數(shù) N。以下 N 行每行N 個(gè)字符，“*”表示巖洞中的物，“.”表示空地，“J”表示小犬（一開始他會向北走），“F”表示 Feli。上北下南左西右東。輸出數(shù)據(jù)僅一行

7、，如果 Feli 能抓到小犬，那么輸出所需的最短時(shí)間，如果 Feli 抓不到小犬，那么這個(gè)最后的有出口），此時(shí)輸出“No戰(zhàn)犯將在巖洞中（因?yàn)?Feli 將在離開的時(shí)候封閉巖洞的所solution.”，不要輸出引號。樣例輸入(maze.in)樣例輸出(maze.out)源程序： program maze;type rec=record x,y:integer; end;const a:array1.4 of integer=(0,1,0,-1);33F*J.*.b:array1.4 of integer=(-1,0,1,0); var q:array0.1,1.10000 of rec;r:ar

8、ray0.1 of longint; map:array0.101,0.101 of integer; used:array0.101,0.101 of boolean; i,j,k,time,p,m,fx,fy,ex,ey,now:longint;d:char;procedure try; var j:integer; beginj:=0;ex:=ex+ap;ey:=ey+bp;while mapex,ey=0 do begininc(j);if j=5 then begin writeln(No solution.);close(output);halt; end; ex:=ex-ap;e

9、y:=ey-bp;inc(p);if p=5 then p:=1; ex:=ex+ap;ey:=ey+bp; end;end;procedure rollbfs;var i,f,u,v:integer; beginnow:=0;rnow:=1;qnow,1.x:=fx;qnow,1.y:=fy;p:=1; repeatinc(time);try;now:=1-now; rnow:=0; fillchar(used,sizeof(used),0); for f:=1 to r1-now dobeginfor i:=1 to 4 do beginu:=q1-now,f.x+ai;v:=q1-now

10、,f.y+bi;if (mapu,v=1) and (not(usedu,v) then begininc(rnow); if (rnow=10000) then exit; qnow,rnow.x:=u;qnow,rnow.y:=v;usedu,v:=true;if (u=ex)and(v=ey) or (u+1=ex)and(v=ey)or (u-1=ex)and(v=ey) or (u=ex)and(v+1=ey) or (u=ex)and(v-1=ey) thenbegin writeln(time);close(output);halt; end;end; end;until 01;

11、end;end;beginassign(input,maze.in);reset(input); assign(output,maze.out);rewrite(output); readln(m);fillchar(map,sizeof(map),0); for i:=1 to m dobeginfor j:=1 to m do beginread(d); case d of.:mapj,i:=1;*:mapj,i:=0;F:begin mapj,i:=1;fx:=j;fy:=i;J:begin mapj,i:=1;ex:=j;ey:=i; end;end;readln; end;close(input);end;end;if (ma