1、廣度優先搜索廣度優先搜索在樹中又叫按層次遍歷，對于樹而言，寬度廣度優先搜索在樹中又叫按層次遍歷，對于樹而言，寬度優先搜索的思路可以描述為：訪問根結點，依次訪問根結優先搜索的思路可以描述為：訪問根結點，依次訪問根結點的每一個子結點（第二層），再通過這些結點訪問第三點的每一個子結點（第二層），再通過這些結點訪問第三層結點層結點。廣度優先與深度優先搜索相比，時間復雜度。廣度優先與深度優先搜索相比，時間復雜度都是相同的，不同的僅僅在于結點訪問的順序不同。它們都是相同的，不同的僅僅在于結點訪問的順序不同。它們在完全遍歷的問題上應該是差不多，但是在有些問題上，在完全遍歷的問題上應該是差不多，但是在有些問題

2、上，比如求最優解，有時廣度優先要比深度優先搜索好。比如求最優解，有時廣度優先要比深度優先搜索好。為了求一個最優解，如果使用深度優先并不能保證找到的為了求一個最優解，如果使用深度優先并不能保證找到的解最優，只有搜索完整棵樹，找到所有解，再比較它們的解最優，只有搜索完整棵樹，找到所有解，再比較它們的優劣，才能從中求出最優解，這顯然不如廣度優先搜索簡優劣，才能從中求出最優解，這顯然不如廣度優先搜索簡單。單。一般來說廣度優先搜索可以利用隊列實現，主要用于解決一般來說廣度優先搜索可以利用隊列實現，主要用于解決求一種狀態通過幾種規定的操作以最少次數變換到另一種求一種狀態通過幾種規定的操作以最少次數變換到另

3、一種狀態的問題。狀態的問題。引例經過城市最少的一條路徑狀態描述（矩陣表示）：1表示不相鄰 0表示相鄰const ju:array1.8,1.8of 0.1=(1,0,0,0,1,0,1,1), (0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1);結點定義type node=record city:char;城市名稱 pre:integer;父結點end;varhead,tail,i:i

4、nteger;隊列首與隊列尾a:array1.100of node;結點數s:arrayA.Hof boolean;城市數procedure out(d:integer);輸出過程，通過每個結點的父結點來輸出Begin write(ad.city); repeat d:=ad.pre; write(-,ad.city); until ad.pre=0; writeln;end;procedure doit;begin head:=0;tail:=1;入隊 a1.city:=A;a1.pre:=0;初始化從A結點開始擴展 fillchar(s,sizeof(s),true);所有結點可用 rep

5、eat inc(head);隊首加，出隊 for i:=1 to 8 do訪問可擴展的結點 if (juord(ahead.city)-64,i=0)and (schr(i+64)=true)then結點可用 begin inc(tail);入隊 atail.city:=chr(64+i); atail.pre:=head;記住它的父結點以便輸出 satail.city:=false;該結點標志為已用 if atail.city=H then判斷是否到達目標結點 begin out(tail);輸出 break;退出搜索，因為已找到最優解 end; end; until head=tail;e

6、nd;begin doit;end.主程序主程序小結廣度優先搜索相當于鐘擺！圖2 搜索樹擴展根節點葉子節點4,5,6,7,81112131415161718小結廣度優先算法描述：Program bfs; 初始化，初始狀態存入隊列；隊列首指針head:=0;尾指針tail:=1;While headtail do begin 指針head后移一位，指向待擴展的結點；for i:=1 to maxdo begin if 擴展出的新結點是目標結點 then 輸出并退出；if 擴展出的新結點符合條件，并且新結點與原已產生的結點不重復 then tail指針加，把新結點存入隊列尾；end;End;注意事

7、項注意事項、每生成一個子結點，就要提供指向它們父結點的指針。當、每生成一個子結點，就要提供指向它們父結點的指針。當解出現時，通過逆向跟蹤，找到從根結點到目標結點的一條路解出現時，通過逆向跟蹤，找到從根結點到目標結點的一條路徑。徑。、生成的結點要與前面所有已經產生的結點比較，以免出現、生成的結點要與前面所有已經產生的結點比較，以免出現重復結點，浪費時間和空間，還有可能陷入死循環。重復結點，浪費時間和空間，還有可能陷入死循環。、如果目標結點的深度與、如果目標結點的深度與“費用費用”（如路徑長度）成正比，（如路徑長度）成正比，那么找到的第一個解即為最優解，這時，搜索速度比深度搜索那么找到的第一個解即

8、為最優解，這時，搜索速度比深度搜索要快些。如果結點的要快些。如果結點的“費用費用”不與深度成正比時，第一次找到不與深度成正比時，第一次找到的解不一定是最優解。的解不一定是最優解。、廣度優先搜索的效率還有賴于目標結點所在位置情況，如、廣度優先搜索的效率還有賴于目標結點所在位置情況，如果目標結點深度處于較深層時，需搜索的結點數基本上以指數果目標結點深度處于較深層時，需搜索的結點數基本上以指數增長，這時一般要采用循環隊列來儲存擴展結點。增長，這時一般要采用循環隊列來儲存擴展結點。 設有下圖所示的一個棋盤，在棋盤上的設有下圖所示的一個棋盤，在棋盤上的A(0,0)點有一個中國象棋馬，點有一個中國象棋馬，

9、并約定馬走的規則：并約定馬走的規則： 1、馬只向右走；、馬只向右走； 2、馬走、馬走“日日“字。字。找出所有從找出所有從A到到B的路徑。的路徑。輸入：輸入：B的坐標的坐標n，m（=15）。）。輸出：所有走法。輸出：所有走法。如：如：輸入：輸入：8 4輸出：（輸出：（0,0)(2 1)(4 0)(5 2)(6 0)(7 2)(8 4)共共37組解見組解見tmall.txt1234567123跳馬問題最小步數跳馬問題最小步數最優解輸出結果為：最優解輸出結果為：（8，4）（6，3）（4，2）（2，1），），-（0，0）求最少步到達求最少步到達B點。點。Best:最短路線，最短路線，a：臨時得到的一個

10、路線。：臨時得到的一個路線。Min：最少步。：最少步。procedure try(i:integer); 搜索到當前第搜索到當前第i個點個點 var j:integer; begin if (ai,1=n) and (ai,2=m)and(imin) then begin min:=i;best:=a;exit;end; 記下當前最短路徑和最少步數記下當前最短路徑和最少步數 if (ai,1n) or (ai,2m)and(i=min) then exit; 剪枝優化剪枝優化 for j:=1 to 4 do if (ai,1+xj,1=0)and(ai,1+xj,1=0)and(ai,2+x

11、j,2=m) then begin ai+1,1:=ai,1+xj,1; ai+1,2:=ai,2+xj,2; try(i+1); end; end;我們可以參照工作分配中求最大效益的方法來求解我們可以參照工作分配中求最大效益的方法來求解缺點：缺點：很明顯，要找到一條跳的步數最小的路徑，必須把很明顯，要找到一條跳的步數最小的路徑，必須把所有路徑全部跳完后才能判斷哪一條是最優路徑，所有路徑全部跳完后才能判斷哪一條是最優路徑，搜索效率比較低。搜索效率比較低。廣度搜索求解跳馬問題狀態產生規則狀態產生規則const dx:array1.4 of integer=(1,2,2,1); dy:array1

12、.4 of integer=(2,1,-1,-2);type node=record lx,ly:integer; pre:integer;父結點，輸出時用 end;var a:array0.1000of node; h,t,n,m,i,x,y:integer;procedure print;輸出，倒著輸出直到父結點變成始結點止begin while at.pre0 do begin write(at.lx,at.ly,-); t:=at.pre; end; writeln(0,0); halt;由于搜索到的肯定是最優解所以程序運行結束end;begin readln(n,m); h:=0;

13、t:=1; a1.lx:=0;記錄始狀態 a1.ly:=0; a1.pre:=0; while h=1)and(x=1)and(y=m) then begin inc(t);入隊 at.pre:=h;記住父結點 at.lx:=x; at.ly:=y;記錄新結點 if (x=n) and (y=m) then print;是否到達 end; end; end;writeln(No solution)end.輸出結果為：8，46，34，22，1-0，0【基礎】走迷宮 題目描述題目描述迷宮由N*N個方格組成，每個方格均被組織者事先標上了“0”或“1”（左上角第一個方格和右下角最后一個方格一定是“0”

14、）。當你進入左上角的第一個方格中時，看到相鄰的方格是“0”時則可以進入，而如果是“1”時則表示此路不通。兔兔被告之：從迷宮的左上角第一個方格的入口處準備進入時，你可得到一個記有N*N分值的記分表，每經過一個標有“0”的方格，記分表將自動扣去1分，當走到右下角最后一個方格的出口處時，將顯示你手中的記分表剩余的分值。夏令營的組織者將只獎勵所有參加此項活動中，記分表剩余的分值最多的營員。輸入輸入第一行是一個整數N（3N40），接下來有N行，每行均有N個由0 和1組成的數據輸出輸出包括一個整數（記分表剩余的分值）樣例輸入樣例輸入4 00111000 00011000 樣例輸出樣例輸出9解題思想：此題本

15、質上還是求最短的路徑，因為求剩余的價值最大，也就是意味著要走過的路最短這樣減少的值就會少！另外，對于此題不要求輸出最短的路徑，所以變量定義時可以考慮更少，不用再記錄所走過的每個結點的位置，而且根據廣度優先搜索的原理，從一個結點擴展到下一層結點，所剩余的值就是父結點的值減一即可，到了最后的目標結點，剩余的值就是所求的值。注意事項：輸入是字符，不是數字0，1來源來源武進區第4屆程序設計比賽題（初中）const dx:array1.4of integer=(1,0,-1,0);坐標增量 dy:array1.4of integer=(0,1,0,-1);type node=record s,x,y:i

16、nteger;S表示剩余的值，初值為n*n，x,y表示位置 end;varq:array1.100000of node;隊列a:array1.100,1.100of char;狀態變量h,t,i,j,n,lx,ly:longint;狀態產生規則begin readln(n); for i:=1 to n do begin for j:=1 to n do read(ai,j);由于讀入是字符，務必請注意 readln; end; h:=0;t:=1;q1.s:=n*n-1;q1.x:=1;q1.y:=1;a1,1:=1;從第一個結點開始，初值為n*n-1 repeat inc(h);出隊 fo

17、r i:=1 to 4 do遍歷所有結點 begin lx:=qh.x+dxi;ly:=qh.y+dyi; if (lx in 1.n)and(ly in 1.n)and(alx,ly=0) then結點可用 begin inc(t);入隊 qt.s:=qh.s-1;該結點的剩余值為父結點的值減一 qt.x:=lx;記錄位置，便于下次擴展用 qt.y:=ly; if (lx=n)and(ly=n) then begin writeln(qt.s);halt;end;如果到了目標結點直接輸出 alx,ly:=1;該結點標志為已用過，以免重復入隊 end; end; until h=t;end.例

18、例3-13-1：（：（xibaoshumuxibaoshumu.txt.txt） 一矩形陣列由數字一矩形陣列由數字0 0到到9 9組成組成, ,數字數字1 1到到9 9代表細胞代表細胞, ,細胞的定義為沿細胞數字上下左右還是細胞數字則為同細胞的定義為沿細胞數字上下左右還是細胞數字則為同一細胞一細胞, ,求給定矩形陣列的細胞個數。求給定矩形陣列的細胞個數。輸入：整數輸入：整數m,n(mm,n(m行，行，n n列列) ) 矩陣矩陣輸出：細胞的個數。輸出：細胞的個數。樣例樣例: :輸入輸入: : 4 10 4 100234500067023450006710345605001034560500204

19、5600671204560067100000000890000000089輸出輸出:4:40234500067103456050020456006710000000089共共4 4個細胞個細胞算法步驟：算法步驟： 1 1、從文件中讀入、從文件中讀入m m* *n n矩陣，將其轉換為矩陣，將其轉換為0 0、1 1矩陣存入矩陣存入picpic數組中；數組中； 2 2、沿、沿picpic數組矩陣從上到下，從左到右，找到遇到的第數組矩陣從上到下，從左到右，找到遇到的第一個細胞；將細胞的位置入隊一個細胞；將細胞的位置入隊h h，并沿其上、下、左、右，并沿其上、下、左、右四個方向上搜索，如果遇到細胞四個方

20、向上搜索，如果遇到細胞(picI,j(picI,j=1)=1)則將其位置入隊，則將其位置入隊，入隊后的位置入隊后的位置picI,jpicI,j 數組置為數組置為0 0； 3 3、將、將h h隊的隊頭出隊，沿其上、下、左、右四個方向上隊的隊頭出隊，沿其上、下、左、右四個方向上搜索，如果遇到細胞則將其位置入隊，入隊后的位置搜索，如果遇到細胞則將其位置入隊，入隊后的位置picpic數數組置為組置為0 0； 4 4、重復、重復3 3，直至，直至h h隊空為止，則此時找出了一個細胞；隊空為止，則此時找出了一個細胞； 5 5、重復、重復2 2，直至矩陣找不到細胞；，直至矩陣找不到細胞； 6 6、輸出找到的

21、細胞數。、輸出找到的細胞數。const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1);var s:string; pic:array1.50,1.80 of 0.1; 0:無細胞；無細胞；1：有細胞：有細胞 m,n,i,j,num:integer; h:array1.4000,1.2 of byte; 隊列：存細胞的坐標，隊列：存細胞的坐標，1：行；：行；2：列：列procedure doing(i,j:integer); var k,open,closed,x,y:integer; begin inc(num);

22、 pici,j:=0; open:=0; 隊列頭隊列頭 closed:=1; 隊列尾隊列尾 h1,1:=i; h1,2:=j;遇到的第一個細胞入隊遇到的第一個細胞入隊 while open0) and (x0) and (y=n) and (picx,y=1) (x,y)處有細胞處有細胞 then begin inc(closed);進隊列進隊列 hclosed,1:=x;hclosed,2:=y; picx,y:=0;打刪除標志打刪除標志 end;為細胞的入隊為細胞的入隊 end; end;begin fillchar(pic,sizeof(pic),0); num:=0; fillchar

23、(h,sizeof(h),0); assign(input,a.in);reset(input); assign(output,a.out);rewrite(output); readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do if sj=0 then pici,j:=0 else pici,j:=1; end; for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩陣中尋找細胞 writeln(num); close(input); close

24、(output);end.八數碼問題在在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有18中的某一個數碼。棋盤中留有一個空格，允許其周圍的某一個將牌向中的某一個數碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結構，給出一個初始布局（稱初始狀態）和一個目標布局（稱目標狀結構，給出一個初始布局（稱初始狀態）和一個目標布局（稱目標狀態），問如何移動將牌，才能實現從初始狀態到目標狀態的轉換。態），問如何移動將牌，才能實現從

25、初始狀態到目標狀態的轉換。圖圖1八數碼問題的初始和目標狀態八數碼問題的初始和目標狀態狀態表示：顯然用二維數組來表示布局直觀，狀態表示：顯然用二維數組來表示布局直觀，S（I,j）表示第）表示第I行第行第J列列格子上放的數字。空格用格子上放的數字。空格用0表示；表示；移動規則：根據題意空格周圍的棋子可以向空格移動。為便于解決問移動規則：根據題意空格周圍的棋子可以向空格移動。為便于解決問題，顯然從另一個角度來看，空格周圍的棋子可以向空格移動相當于題，顯然從另一個角度來看，空格周圍的棋子可以向空格移動相當于“空格向四周移動空格向四周移動”，這樣就把四枚棋子的移動轉化為一個空格的移，這樣就把四枚棋子的移

26、動轉化為一個空格的移動，從而便于問題的處理。動，從而便于問題的處理。移動規則：移動規則：1、向上移動、向上移動Y+12、向下移動、向下移動Y-13、向左移動、向左移動X-14、向右移動、向右移動X+1搜索策略：搜索策略：1、把初始狀態作為當前狀態；、把初始狀態作為當前狀態；2、從當前的狀態出發，運用四條移動規則，產生新的、從當前的狀態出發，運用四條移動規則，產生新的狀態狀態3、判斷新的狀態是否達到目標狀態，如果是，轉、判斷新的狀態是否達到目標狀態，如果是，轉5；4、把新的狀態記錄下，取出下一個中間狀態作為當前、把新的狀態記錄下，取出下一個中間狀態作為當前狀態，返回狀態，返回2；5、輸出從初始狀

27、態到目標狀態的路徑，結束。、輸出從初始狀態到目標狀態的路徑，結束。const n:array1.4,1.2of integer=(1,0),(-1,0),(0,1),(0,-1);四個規則type arr=array1.3,1.3of integer;var a,b:Arr; list:array1.10000of arr;隊列，存放結點 fa:array1.10000of integer;記錄父結點 t:integer; i,o,j,x,y:integer; found:boolean;判斷是否到達目標結點function f(c,d:arr):boolean;var k,l:integer

28、;begin f:=true; for k:=1 to 3 do for l:=1 to 3 do if ck,ldk,l then f:=false;end;判斷是否已經存放在隊列中function pa(c:arr):boolean;var k,l:integer;begin pa:=true; for k:=1 to o do if f(c,listk) then pa:=false;end;遞歸輸出，按父結點是否為0來輸出procedure print(c:integer);begin if fac0 then print(fac); for i:=1 to 3 do begin fo

29、r j:=1 to 3 do write(listci,j, ); writeln; end; writeln;end;找0的位置以便于繼續擴展procedure fou;var k,l:integer;begin for k:=1 to 3 do for l:=1 to 3 do if listjk,l=0 then begin x:=k; y:=l; end;end;beginfor i:=1 to 3 do begin for j:=1 to 3 do begin read(list1i,j); end; readln; end; for i:=1 to 3 do begin for j

30、:=1 to 3 do read(bi,j); readln; end; o:=1;隊列初始化 j:=0; fa1:=0; while j0)and(y+ni,20)and(x+ni,14)and(y+ni,21000) then break; end; if found then print(o) else writeln(NO ANSWER);end.最少步數在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學生設想：如果馬能有兩種走法將增加其趣味性，因此，他規定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個19

31、19的圍棋的圍棋盤上任選兩點A，B，A點放上黑子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走。倆人一個走黑馬，一個走白馬。誰用最少的步數走到左上角坐標為（1，1）的點時，誰獲勝。現在他請你幫忙，給你A，B兩點的坐標，想知道兩個位置到（1，1）點的可能的最少步數。輸入：12 1618 10輸出：89分析：由于A,B兩點是隨機輸入的，因此我們無法找到計算最少步數的數學規律，只能通過廣度優先搜索的辦法求解。（1）確定出發點從（x,y）出發通過一次廣度優先搜索，可以找到從（x,y）至棋盤上所有可達到的點的最少步數。而問題中要求的是黑馬所在的（x1,y1）和白馬所在的（x2,y2

32、）到達（1，1）目標點的最少步數。雖然兩條路徑的起點不同,但它們的終點卻是相同的。如果我們將終點（1，1）為起點，這樣只需要一次廣度搜索便可以得到（x1,y1）和（x2,x2）到達（1，1）的最小步數。（2）數據結構設：que隊列，存儲從（1，1）可到達的點（quek，1.2）以及到達該點所需要的最小步數（quek，3）（0k192+1）。隊列的首指針為closed，尾指針為open。初始時，que中只有一個元素為（1，1），最少步數為0。s記錄（1，1）到每點所需的最少步數。顯然，問題的答案是sx1，y1和x2，y2 。初始時，s1，1為0，除此之外的所有元素的值均設為-1。為了使馬從棋盤內

33、任意位置擴展出的坐標均在s的范圍內，我們將s的數組的范圍擴大至s-1.21,-1.21。dx,dy移動后的位置增量數組。馬有12種不同的擴展方向：馬走“日”：(x-2,y-1),(x-1,y-2),(x-2,y+1),(x-1,y+2),(x+2,y-1),(x+1,y-2),(x+2,y+1),(x+1,y+2)。馬走“田”:(x-2,y-2),(x-2,y+2),(x+2,y-2),(x+2,y+2).我們將i方向上的位置增量存入常量數組dxi和dxi中（1i12）：Const dx:array1.12 of integer=(-2,-2-1,1,2,2,2,2,1,-1,-2,-2);

34、dy:array1.12 of integer=(-1,-2,-2,-2,-2,-1,1,2,2,2,2,1);(3)約束條件不能越出界外。由于馬的所有可能的落腳點s均在s的范圍內，因此一旦馬越出界外，就將其s值賦為0，表示“已經擴展過，且到達（1，1）最少需要0步”。這看上去是荒謬的，但是可以簡單而有效地避免馬再次落入這些界外點。該點在以前的擴展中沒有到達過。如果曾經到達過，則根據廣度優先搜索的的原理，先前到達該點所需的步數一定小于當前步數，因此完全沒有必要再擴展下去。由此得出，馬跳后的位置（x,y）是否可以入隊的約束條件是sx,y0。（4）算法流程 fillchar(s,sizeof(s)

35、,o);s1,1:=0; for x1:=1 to 19 do for y1:=1 to 19 do sx1,y1:=-1; open:=1;closed:=0; que1,1:=1;que1,2:=1; read(x1,y1,x2,y2); while closedopen do begin inc(closed); for d:=1 to 12 do begin x:=queclosed,1+dxd; y:=queclosed,2+dyd; if sx,y0 then begin sx,y:=queclosed,3+1; inc(open); queopen,1:=x;queopen,2:

36、=y;queopen,3:=sx,y; end; end; end; end; writeln(sx1,y1); writeln(sx2,y2);小鼠迷宮問題【問題描述】小鼠a與小鼠b身處一個mn的迷宮中，如圖所示。每一個方格表示迷宮中的一個房間。這mn個房間中有一些房間是封閉的，不允許任何人進入。在迷宮中任何位置均可沿上，下，左，右4個方向進入未封閉的房間。小鼠a位于迷宮的（p，q）方格中，它必須找出一條通向小鼠b所在的（r，s）方格的路。請幫助小鼠a找出通向小鼠b的最短道路。 【輸入格式】輸入文件中的第一行為三個正整數n，m，k（1=n，m=100，0=k=mn-2），分別表示迷宮的行數，

37、列數和封閉的房間數。接下來的k行，每行有兩個正整數，表示被封閉的房間所在的行號和列號。最后的兩行，每行有兩個正整數，分別表示小鼠a所處的方格（p，q）和小鼠b所處的方格（r，s），小鼠a和小鼠b所處的方格是不封閉的。【輸出格式】輸出文件中為計算出的小鼠a通向小鼠b的最短路長度。【輸入輸出樣例】輸入：（maze.in）：8 8 33 34 56 62 17 7輸出：（maze.out）：11源程序：const maxn=100;w:array1.4of integer=(1,0,-1,0);定義狀態變化u:array1.4of integer=(0,1,0,-1);var map:array1.