隊(duì)列與廣搜（鳳山書屋）

1、隊(duì)列與廣度優(yōu)先搜索1陽山書屋隊(duì)2陽山書屋規(guī)定：只能從隊(duì)首出隊(duì)只能從隊(duì)尾入隊(duì)每個人只能進(jìn)出隊(duì)一次3陽山書屋一 、隊(duì)列的概念隊(duì)列是一種的線性表，刪除在表頭（隊(duì)頭），插入在表尾（隊(duì)尾）進(jìn)行。先進(jìn)先出（First In First Out）假設(shè)入隊(duì)的順序是：a1,a2,an， 則出隊(duì)列的順序也是： a1,a2,an。a1 a2 a3 an隊(duì)頭隊(duì)尾出隊(duì)列入隊(duì)列4陽山書屋隊(duì)尾：tail （指向隊(duì)尾，最后一個元素）隊(duì)首：head (習(xí)慣指向隊(duì)首的前一位置，空的位置)隊(duì)列數(shù)組q下標(biāo)： 3 4 5 6 7 初始：head=tail=0非空： head=tail ;65419Headtail5陽山書屋定義：Con

2、st max=隊(duì)列的大小；Var queue:array1.max of datatype; head,tail: longint;隊(duì)列的兩種操作： 入隊(duì)：procedure add(x); 出隊(duì)：function deldatatype=record data:各種需要保存狀態(tài) depth:longint; / 深度End;6陽山書屋1）、過程ADD(x)在隊(duì)列q的尾端插入元素x procedure ADD( x：qtyper)； begin inc(tail); qtail：=x； end；ADD2）、函數(shù)DEL取出q隊(duì)列的隊(duì)首元素 function DEL； begin inc(head

3、); del:=qhead； end；DEL7陽山書屋二、廣度優(yōu)先搜索BFS (Breadth First Serach)也稱為寬度優(yōu)先搜索按層遍歷的一種搜索方法8陽山書屋 深度優(yōu)先搜索(Depth-First Search) dfs狀態(tài)空間圖 狀態(tài)搜索樹：先擴(kuò)展最左邊的結(jié)點(diǎn)，再擴(kuò)展右邊的結(jié)點(diǎn) 目標(biāo)9陽山書屋 廣度優(yōu)先搜索(Breadth -First Search) bfs狀態(tài)空間圖 狀態(tài)搜索樹：先擴(kuò)展深度小的結(jié)點(diǎn)，從上而下擴(kuò)展結(jié)點(diǎn) 目標(biāo)10陽山書的遍歷(輸出結(jié)點(diǎn))：深度優(yōu)先遍歷（dfs）原則：能向前走就走，不能走就后退一步再選擇可行點(diǎn)11陽山書屋a:array1.

4、maxn,1.maxn of integer;/鄰接矩陣visited:array1.maxn of boolean; /訪問標(biāo)志procedure dfs(i:integer); /深度優(yōu)先遍歷結(jié)點(diǎn) var j:integer; begin write(i, ); visitedi:=true; for j:=1 to n do if (ai,j=1)and(not visitedj) then dfs(j); end;begin init; dfs(1);end.12陽山書屋廣度優(yōu)先遍歷（bfs）1搜索過程如下： 從起點(diǎn)開始由近及遠(yuǎn)按層次遍歷。1435678291013陽山書屋 /q:ar

5、ray1.maxn of longint;/隊(duì)列保存結(jié)點(diǎn) head:=0; tail:=1; /隊(duì)列初始化 q1:=1; visited1:=true; /1進(jìn)隊(duì)列，避免重復(fù) while headtail do /隊(duì)列不空 begin inc(head); /出隊(duì)列 k:=qhead; write(k, ); for j:=1 to n do /找沒有遍歷過的鄰接點(diǎn) if (ak,j=1)and(visitedj=false) then begin inc(tail); /進(jìn)隊(duì)列 qtail:=j; visitedj:=true; end; end;14陽山書屋【問題描述：】在n*n的棋盤上有

6、一匹馬在第x行第y列的格子上。棋盤上有些格子上有障礙物，馬不能達(dá)到有障礙物的格子。已知馬在棋盤中的走法按“日“字8個方向可走，如下圖所示：問：哪些格子能到達(dá)，到達(dá)這些格子的最小步數(shù)是多少。【輸入：】第一行:n（n=100）,x,y(馬的開始位置)。接下來n行為棋盤的描述：“-“為空格子，”+“表示該格子有障礙物?！据敵觯骸縩行，每行n個用空格隔開的數(shù)，表示馬到達(dá)該格子的最少步數(shù)，如果無法到達(dá)則用-1表示。1、跳馬15陽山書屋4 2 2-+-【樣例輸入：】4 3 2 13 0 3 22 3 -1 11 2 1 4【樣例輸出：】馬1111222233334416陽山書屋 dx:array1.8 o

7、f integer=(-1,-2,-2,-1,1,2,2,1); dy:array1.8 of integer=(2,1,-1,-2,-2,-1,1,2);var can:array-1.maxn+2,-1.maxn+2 of boolean; dist:array1.maxn,1.maxn of integer; /記錄最少步數(shù) q:array1.maxn*maxn,1.2 of integer; head,tail:longint； procedure init; var s:string; begin readln(n,x0,y0); fillchar(can,sizeof(can),f

8、alse); for i:=1 to n do begin readln(s); for j:=1 to n do cani,j:=sj=-; end; end;17陽山書屋procedure bfs;/廣度優(yōu)先搜索 begin for i:=1 to n do for j:=1 to n do disti,j:=-1; head:=0; tail:=1; / 隊(duì)列初始化 distx0,y0:=0; q1,1:=x0; q1,2:= y0; / 起點(diǎn)進(jìn)隊(duì)列 while headtail do begin inc(head); /出隊(duì)列 x:=qhead,1; y:=qhead,2; /記錄出隊(duì)

9、結(jié)點(diǎn)狀態(tài) for k:=1 to 8 do /擴(kuò)張結(jié)點(diǎn)：走下一步 begin xx:=x+dxk; yy:=y+dyk; if canxx,yy and (distxx,yy=-1) then /能走但沒走過 begin distxx,yy:=distx,y+1; inc(tail); qtail,1:=xx; qtail,2:=yy; end; end; end; end;18陽山書屋 設(shè)有一個N*N方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中分別放有0和1，0表示可通，1表示不能，迷宮走的規(guī)則如下圖所示：即從某點(diǎn)開始，有八個方向可走，前進(jìn)方格中數(shù)字為0時表示可通過，為1時表示不可

10、通過，要另找路徑。輸入例子：（從文件中讀取數(shù)據(jù)） 80 0 0 1 1 0 1 01 0 1 1 0 1 1 00 1 0 0 1 0 0 10 0 1 1 0 1 0 10 1 0 0 0 1 1 00 1 1 1 1 1 0 10 0 1 1 1 0 1 11 1 0 0 0 0 0 0入口：（1，1）；出口：（1，8）輸出要求：找出一條 從入口（左上角）到出口（又上角）的最短路徑。 8(1 1)(2 2)(3 3)(3 4)(4 5)(3 6)(3 7)(2 8)(1 8)2、迷宮問題19陽山書屋Bfs算法：1）先求最少步數(shù)const fin=migong.in; fout=migong

11、.out; maxn=100; dx:array1.8of integer=(0,1,1,1,0,-1,-1,-1); dy:array1.8of integer=(-1,-1,0,1,1,1,0,-1);type node=record row,col:integer; /記錄行與列 depth:integer; /離起點(diǎn)的距離 end;var can:array0.maxn+1,0.maxn+1 of boolean; q:array1.maxn*maxn of node; n,head,tail:integer;20陽山書屋 head:=0; tail:=1; q1.row:=1; q1

12、.col:=1; q1.depth:=0; can1,1:=false; while headtail do begin inc(head); x:=qhead.row; y:=qhead.col; step:=qhead.depth; for k:=1 to 8 do begin xx:=x+dxk; yy:=y+dyk; if canxx,yy then /沒走過，沒入過隊(duì) begin if (xx=1)and(yy=n) then print(step+1); inc(tail); qtail.row:=xx; qtail.col:=yy; qtail.depth:=step+1; ca

13、nxx,yy:=false; end; end; end; print(-1);/無解的情況21陽山書屋 procedure print(ans:integer); var j:integer; begin assign(output,fout); rewrite(output); if ans=-1 then writeln(no answer) else writeln(ans); close(output); halt; end;22陽山書屋1和2是怎樣保證不重復(fù)進(jìn)隊(duì)列的？重復(fù)進(jìn)隊(duì)列，做了無用功，浪費(fèi)空間和時間。設(shè)置合適的布爾數(shù)組23陽山書屋 給定10個盒子排成一行，其中有兩個相鄰的盒子

14、是空的，其余的盒子中有4個A和4個B。 移動規(guī)則：任意兩相鄰字母可移到空盒子中去，但這兩個字母的原來順序保持不變。 目標(biāo)：全部的A在左邊，全部的B在右邊，空格在中間。 對于任意給定的一個排列順序，最少經(jīng)過多少次移動，能達(dá)到目標(biāo)序列。輸入：一行：初始序列，空格用0代替。輸出：初始序列達(dá)到目標(biāo)的最少移動次數(shù)。樣例：輸入：輸出：5AAAABBBBABBAABAB3、中國盒子問題 （box） 初始：目標(biāo)：24陽山書屋ABAB00ABABA00BBAABABAAABB00BABAAA00BBBABAAAABBBB00AAAA00BBBB1234525陽山書屋1)、問題：初始序列達(dá)到目標(biāo)的最少移動次數(shù)。

15、適合使用bfs算法。 2)、隊(duì)列需要保存的狀態(tài)： 轉(zhuǎn)化后的字符串s; 轉(zhuǎn)換需要的步數(shù)depth。 適合用記錄數(shù)據(jù)類型： type node=record str:string; depth:integer; end;3)、狀態(tài)的多少（隊(duì)列的大?。?!/(4!*4!)=63026陽山書屋4)、狀態(tài)的轉(zhuǎn)移：看兩個空格的能移動的位置 任意兩相鄰字母可移到空盒子中去，但這兩個字母的原來順序保持改變 ABBAABAB1）、確定空格的位置： sp:=pos(0,s);spS=i （1-9）2）、i，i+1與sp，sp+1位置的字符交換：條件：( i+1 sp ) or ( sp+1i ) /前后情況3）

16、、交換：Tem=stemsp:=si; temsp+1:=si+1; temi:=0; temi+1:=0;？27陽山書屋5)、判重：是否已進(jìn)過隊(duì)列 從隊(duì)中的所有狀態(tài)查找：1.tail function find(tem:string):boolean; var j:integer; begin for j:=1 to tail do if tem=qj.str then exit(true); exit(false); end;28陽山書屋 head:=0; tail:=1; q1.str:=s1; q1.depth:=0; while headtail do begin inc(head)

17、; s:=qhead.str; step:=qhead.depth; sp:=pos(0,s); for i:=1 to 9 do begin tem:=s; if (i+1sp)or(sp+1i) then begin temsp:=si; temsp+1:=si+1; temi:=0; temi+1:=0; if tem=st then print(step+1); if not find(tem) then begin inc(tail); qtail.str:=tem; qtail.depth:=step+1; end; end; end; end;29陽山書屋廣度優(yōu)先 搜索算法（bf

18、s）:1、適合的題目類型： 1）、求從給定初始狀態(tài)到目標(biāo)狀態(tài)最少需要的步數(shù)。 2）、給定初始狀態(tài)，經(jīng)過k步后能夠到達(dá)哪些狀態(tài)。2、利用的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列。3、狀態(tài)的最大值：決定隊(duì)列的大小（非常重要）4、隊(duì)列里需要記住哪些狀態(tài)：一般使用記錄數(shù)據(jù)類型。5、狀態(tài)的轉(zhuǎn)移：不能遺漏。6、狀態(tài)的判重：避免重復(fù)進(jìn)入隊(duì)列。7、無解的判斷30陽山書屋head=0：隊(duì)列的首指針；tail=1：隊(duì)列的尾指針；Quene1:初始結(jié)點(diǎn);While headtail do /還有未擴(kuò)展的結(jié)點(diǎn)，隊(duì)列不空 Begin Inc（head）； /移動隊(duì)列的首指針：出隊(duì)列 記錄head狀態(tài)； For i=1 to method do

19、 /按規(guī)則擴(kuò)展下一層新的子結(jié)點(diǎn) if 條件滿足 then Begin 生成新的結(jié)點(diǎn); if 新結(jié)點(diǎn)隊(duì)列中沒出現(xiàn)過 then 保存新結(jié)點(diǎn)（入隊(duì)列）； if 新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn) then print(tail) 搜索結(jié)束； End End；Print(-1); /無解BFS的基本框架：31陽山書屋type queue=record 必要的有用的狀態(tài); father:longint;/父親結(jié)點(diǎn)，輸出路徑 depth:longint; end;q:array1.maxn of queue;隊(duì)列的大小作為全局變量，避免用作局部變量，尤其當(dāng)maxn很多時。32陽山書屋/輸出轉(zhuǎn)化過程：路線 procedure

20、 dfs(i:longint);/從當(dāng)前點(diǎn)遞歸輸出 begin if qi.father0 then dfs(qi.father); write(qi.v, ); end; procedure print(k:longint); begin writeln(qk.depth); dfs(k); halt; end;33陽山書屋常用的判重方法：合適的布爾類型 (迷宮類)樸素的隊(duì)列查找 find(1.tail)：如果多，時間長構(gòu)造合適的哈希函數(shù)：為了分類，減少查找時間影響bfs時間的關(guān)鍵：重點(diǎn)減少不必要的擴(kuò)展結(jié)點(diǎn)34陽山書屋【問題描述】對于只含有字母A和B的字符串，給定初始串s1和目標(biāo)串s2。同時

21、給定串中字母的移動規(guī)則：每次移動只能交換兩個相鄰的字母。任務(wù)：求s1最少經(jīng)過多少次交換得到s2?！据斎搿康谝恍校撼跏即畇1。第二行：目標(biāo)串s2。【輸出】由s1生成s2的最少交換次數(shù)。【數(shù)據(jù)范圍限制】100%的數(shù)據(jù)：s1和s2長度=20?！据斎胼敵鰳永?change.inchange.outAABBAABAAAAB44、A B交換35陽山書屋保存的狀態(tài)狀態(tài)數(shù)量：隊(duì)列的大小狀態(tài)的擴(kuò)展條件判重方法分析：36陽山書屋判重的改進(jìn)： 構(gòu)造哈希函數(shù)：把AB串對應(yīng)于二進(jìn)制A:0 B:1AB串和二進(jìn)制一一對應(yīng)關(guān)系。AABBAA00110012。f12=true大?。?0位：22037陽山書屋function

22、hash(s:string):longint; var k,i:longint; begin k:=0; for i:=n downto 1 do k:=k*2+ord(si)-65; hash:=k; end;構(gòu)造函數(shù)：hash(s)fhash(s)=true38陽山書屋 head:=0; tail:=1; q1.str:=s1; q1.depth:=0; fhash(s1):=true; while headtail do begin inc(head); s:=qhead.str; step:=qhead.depth; for i:=1 to n-1 do if sisi+1 then

23、begin ss:=s; ssi:=si+1; ssi+1:=si; if not fhash(ss) then begin inc(tail); qtail.str:=ss; qtail.depth:=step+1; fhash(ss):=true; if ss=s2 then print(tail); end; end; end;39陽山書屋 有兩個無刻度標(biāo)志的水杯，分別可裝x升和y升的水。設(shè)另一個水缸，可以用來向水杯灌水或從水杯向水缸里倒水，兩個水杯之間也可以相互倒水。已知x升的水杯開始是盛滿水的，y升的杯子是空的，問如何通過倒水和灌水操作，用最少的步數(shù)能在y升的杯子里量出z升水。5：倒

24、水問題CA水缸（足夠的水,未滿）X=20 Y=15 Z=10Y=10？B40陽山書屋輸入： 一行：x，y，z（0)and(by)。結(jié)果： 要么A空（ay-b）。 可以從A中倒mina,y-b升水給B。狀態(tài)： A：a-mina,y-b; B：b+mina,y-b。43陽山書屋2: ACxax-ayby-bBAC條件： A中有水：a0結(jié)果： 把A中水全倒入C狀態(tài)： A: 0; B:b不變。44陽山書屋3: BAxax-ayby-bBAC條件：B中有水且A不滿，即 (b0)and(ax)。結(jié)果: 要么B空（bx-a）。 可以從B中倒minb,a-x升水給A。狀態(tài)：A：a+minb,x-a; B：b-

25、minb,x-a。45陽山書屋4: BCxax-ayby-bBAC條件： B中有水：b0結(jié)果: 把B中水全倒入C狀態(tài)： A: a ;B:0升。46陽山書屋5: CAxax-ayby-bBAC條件： A不滿: ax。結(jié)果: 把A倒?jié)M狀態(tài)： A: x滿，B：b不變。47陽山書屋6: CBxax-ayby-bBAC條件： B不滿：by。結(jié)果: 把B倒?jié)M狀態(tài)： A：a不變，B：y滿。48陽山書屋算法實(shí)現(xiàn)：每倒一次需要保存的狀態(tài)：a,b,father,depth倒完一次后檢查：a和b的值：出現(xiàn) ? b=z ?隊(duì)列的大?。簃ax=100；（max+1）*（max+1）怎樣判斷重復(fù)： fi,j:boolean。A中出現(xiàn)i升，B中出現(xiàn)j升水的情況；49陽山書屋Const max=100;type node=record a,b:integer; father:integer; depth:integer; /a:A中水；b：B中的水； end;var x,y,z:integer; q:array1.(max+1)*(max+1) of node; f:array0.max,0.max of boo