寬度優(yōu)先搜索

1、寬度優(yōu)先搜索寬度優(yōu)先搜索走迷宮（Maze）【問題描述】已知一NN的迷宮，允許往上、下、左、右四個方向行走，現(xiàn)請你找出一條從左上角到右下角的最短路徑?！据斎霐?shù)據(jù)】輸入數(shù)據(jù)有若干行，第一行有一個自然數(shù)N（N20），表示迷宮的大小，其后有N行數(shù)據(jù)，每行有N個0或1（數(shù)字之間沒有空格，0表示可以通過，1表示不能通過），用以描述迷宮地圖。入口在左上角（1，1）處，出口在右下角（N，N）處。所有迷宮保證存在從入口到出口的可行路徑?！据敵鰯?shù)據(jù)】輸出數(shù)據(jù)僅一行，為從入口到出口的路徑（有多條路徑時輸出任意一條即可請嚴(yán)格按照 下 上 左 右）。路徑格式參見樣例。【樣例輸入】40001010000100110 【樣

2、例輸出】(1,1)-(1,2)-(1,3)-(2,3)-(2,4)-(3,4)-(4,4)#includeusing namespace std;const int dx5=0,1,-1,0,0;const int dy5=0,0,0,1,-1;int a20,b20;int c2020;int n;int main()string s;int i,j;cinn;for (i=1;is;for (j=0;js.length();+j) if (sj=0) cij+1=0; else cij+1=1; dfs(1,1,1); void print(int dep)int i;for (i=1;i

3、dep;i+) cout(ai,bi;cout(ai,bi)endl;void dfs(int dep,int x,int y) int i,tx,ty; adep=x; bdep=y; cxy=1; if(x=n&y=n) print(dep); else for (i=1;i0&tx0&ty=n&ctxty=0) dfs(dep+1,tx,ty); 算法1：dfs 從左上角開始，找到下一個能走的路cij=0，然后dfs(i,j),（接著窮舉i,j）下一個點繼續(xù)dfs,直到找到出口位置。算法2：bfs(寬度優(yōu)先搜索)_利用隊列實現(xiàn)入隊入隊出隊出隊 A1 A2 A3 A4 A5 A6 A1A7

4、 隊列的概念隊列和棧一樣，也是一種特殊的線性表；隊列是一種運算受到限制的線性表，插入操作限定在表的一端進行，稱為“入隊”，刪除操作則限定在表的另一端進行，稱為“出隊”；插入一端稱為隊尾（rear），刪除一端稱為隊頭（front）。隊頭隊頭隊尾隊尾隊列的概念隊列的特點：先進隊列的元素先出隊列；隊列的特點：先進隊列的元素先出隊列；隊列常說成隊列常說成先進先出線性表先進先出線性表（FIFO，F(xiàn)irst In First Out）；）；類似于生活中排隊購票：先來先買，后來后買。類似于生活中排隊購票：先來先買，后來后買。隊列的存儲結(jié)構(gòu)在計算機中實現(xiàn)（存儲）隊列的最簡單方法是用一維數(shù)組；若每個節(jié)點需要存儲

5、的不只一個數(shù)據(jù)，則可以把每個數(shù)組元素的基類型設(shè)置為記錄；或者定義成多個一維數(shù)組，再或者定義成一個幾行n列的二維數(shù)組；為了標(biāo)識隊頭和隊尾，還要設(shè)置兩個下標(biāo)（指針）變量front和rear，分別指向隊列的頭和尾。周末舞會 假設(shè)在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。規(guī)定每個舞曲只能有一對跳舞者。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲。現(xiàn)要求寫一個程序，模擬上述舞伴配對問題。輸入： 3個整數(shù)m，n，k，分別表示男士人數(shù)、女士人數(shù)、幾輪舞曲。輸出： 各輪舞曲的配對方案。例、周末舞會 假設(shè)在周末舞會上，男士們和女士

6、們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。規(guī)定每個舞曲只能有一對跳舞者。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲。現(xiàn)要求寫一個程序，模擬上述舞伴配對問題。輸入： 3個整數(shù)m，n，k，分別表示男士人數(shù)、女士人數(shù)、幾輪舞曲。輸出： 各輪舞曲的配對方案。輸入樣例：2 4 6輸出樣例：1 12 21 32 41 12 2算法：模擬舞會配對 設(shè)計兩個隊列分別存放男士和女士的編號，每次取出（出隊）兩個隊列的隊頭元素進行配對（輸出），每對跳舞的人一旦跳完后就回到隊尾（入隊）等待下次被選。寬度優(yōu)先搜索（寬搜，bfs)寬度優(yōu)先搜索算法又稱為廣度優(yōu)先搜索

7、，是最簡便的圖的搜索算法之一，這個算法是很多重要的圖論算法的模型；BFS（Breadth First Search）屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋目標(biāo)節(jié)點（目標(biāo)狀態(tài)）；換句話說，它并不考慮結(jié)果的可能位置，不關(guān)心搜索的快慢好壞，就是徹底地搜索整張圖，直到找到目標(biāo)節(jié)點為止（或者無解）；從算法的觀點看，所有因為展開節(jié)點而得到的子節(jié)點都會被加入到一個先進先出的隊列中，所以是隊列的重要應(yīng)用。通過搜索樹，比較通過搜索樹，比較bfsbfs與與dfsdfs的區(qū)別。白色表示未訪問的區(qū)別。白色表示未訪問的節(jié)點，黑色表示已經(jīng)訪問的節(jié)點，灰色表示：的節(jié)點，黑色表示已經(jīng)訪問的節(jié)點，灰色

8、表示：DFSDFS中為中為正在訪問的節(jié)點、正在訪問的節(jié)點、BFSBFS中為已入隊等待訪問的節(jié)點。中為已入隊等待訪問的節(jié)點。六、寬度優(yōu)先搜索（寬搜，bfs)結(jié)構(gòu)一：求一個解、所有解、最優(yōu)解while front=rear 由front狀態(tài)去尋找新的目標(biāo)狀態(tài) if 找到新的狀態(tài)沒有出現(xiàn)過 把新狀態(tài)添加進隊列（rear+) if 新的狀態(tài)就是目標(biāo)狀態(tài) 做相應(yīng)處理（退出循環(huán)輸出解、輸出當(dāng)前解、比較解的優(yōu)劣） front+front狀態(tài)可能到達(dá)的狀態(tài)窮舉完畢，則出隊，進入下一個狀態(tài)去尋求新狀態(tài) 寬度優(yōu)先搜索（寬搜，bfs)例1：迷宮寬搜程序怎么實現(xiàn)bfs應(yīng)用舉例例2、數(shù)字變換（num.in/out/pa

9、s/cpp)給定一個數(shù)N (ON100000)，變成另一個數(shù)K(OK100000)，允許的操作是乘以2，或者加減1，問最少要幾步才能完成？【輸入格式】僅有兩個整數(shù) N 和 K 【輸出格式】最少步數(shù)【樣例輸入】517【樣例輸出】4bfs應(yīng)用舉例 bfs應(yīng)用舉例541068379 912112016214181322191715部分狀態(tài)空間樹部分狀態(tài)空間樹BFS vs DFS程序?qū)崿F(xiàn)例3、關(guān)系網(wǎng)絡(luò)（relationship.?） 有n個人，他們的編號為1n，其中有一些人相互認(rèn)識，現(xiàn)在x想要認(rèn)識y，可以通過他所認(rèn)識的人來認(rèn)識更多的人（如果a認(rèn)識b、b認(rèn)識c，那么a可以通過b來認(rèn)識c），求出x最少需要

10、通過多少人才能認(rèn)識y。輸入: 第一行三個整數(shù)n、x、y；接下來一個nn的鄰接矩陣，ai,j=1表示i認(rèn)識j，ai,j=0表示不認(rèn)識。保證i=j時,ai,j=0,并且ai,j=aj,i。輸出: x認(rèn)識y最少需要通過的人數(shù)。數(shù)據(jù)保證x一定能認(rèn)識y 。樣例輸入：5 1 50 1 0 0 01 0 1 1 00 1 0 1 00 1 1 0 10 0 0 1 0樣例輸出：2七、bfs應(yīng)用舉例算法分析： 寬搜。 先設(shè)答案ans=0。把x加入隊列并設(shè)置為隊頭元素，從隊頭開始進行寬搜，窮舉鄰接矩陣的第x行，看x認(rèn)識誰（判斷ax,j=1），認(rèn)識的人（j）全部依次入隊，并且ans:=ans+1，如果出現(xiàn)了y，則

11、輸出ans，結(jié)束搜索，否則，取出隊頭元素繼續(xù)寬搜。七、bfs應(yīng)用舉例 程序?qū)崿F(xiàn)bfs應(yīng)用舉例小結(jié) 本題是說明“寬搜”的另一個重要應(yīng)用：求最優(yōu)值問題。比如最少幾次、最快幾步等！思考：如果要輸出x是通過什么關(guān)系（哪些人）認(rèn)識y的呢？解決：再設(shè)一個數(shù)據(jù)域（或者數(shù)組），記錄當(dāng)前節(jié)點是從哪個節(jié)點擴展得到的。bfs應(yīng)用舉例例：例：奇怪的電梯（奇怪的電梯（lift.?） 呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第一層樓都可以停電梯，而且第i層樓層樓(1=i=N)上有一個數(shù)字上有一個數(shù)字Ki(0=Ki0) an

12、d (x70) and (x70) and (x30) and (x33) 操作是操作是x10:=x10+x3-3;x3:=3;x7x10:=x10+x3-3;x3:=3;x7不變不變7 7斤的瓶子往斤的瓶子往3 3斤的瓶子里倒：斤的瓶子里倒：? ?7 7斤的瓶子往斤的瓶子往1010斤的瓶子里倒：斤的瓶子里倒：? ?3 3斤的瓶子往斤的瓶子往7 7斤的瓶子里倒：斤的瓶子里倒：? ?3 3斤的瓶子往斤的瓶子往1010斤的瓶子里倒：斤的瓶子里倒：? ?七、bfs應(yīng)用舉例例例6 6、倒油問題（、倒油問題（oil.?oil.?）算法分析：算法分析： 第三、在沒有找到解（沒出現(xiàn)目標(biāo)狀態(tài)）之前，是不知道該

13、怎么倒油第三、在沒有找到解（沒出現(xiàn)目標(biāo)狀態(tài)）之前，是不知道該怎么倒油的，也就是說從當(dāng)前狀態(tài)到在一個狀態(tài)是的，也就是說從當(dāng)前狀態(tài)到在一個狀態(tài)是盲目盲目的，只能窮舉。如何窮的，只能窮舉。如何窮舉、如何保存每一個狀態(tài)呢？隊列！舉、如何保存每一個狀態(tài)呢？隊列！ 第四、由于是要輸出最快的倒油方案，所以不應(yīng)該做無謂的倒油操作，第四、由于是要輸出最快的倒油方案，所以不應(yīng)該做無謂的倒油操作，也就是說從一個狀態(tài)采用一種倒油方法得到的狀態(tài)不能出現(xiàn)過，否則也就是說從一個狀態(tài)采用一種倒油方法得到的狀態(tài)不能出現(xiàn)過，否則一定不是最快的倒油方案。所以，需要對一定不是最快的倒油方案。所以，需要對狀態(tài)狀態(tài)“判重判重”。如何實現(xiàn)？。如何實現(xiàn)？窮舉！窮舉！ 第五、因為要第五、因為要輸出具體的倒油步驟輸出具體的倒油步驟，所以要保存各個狀態(tài)之間是怎么，所以要保存各個狀態(tài)之間是怎么轉(zhuǎn)移的，以便找到目標(biāo)狀態(tài)后倒過來，按照這個線索輸出從初始狀態(tài)轉(zhuǎn)移的，以便找到目標(biāo)狀態(tài)后倒過來，按照這個線索輸出從初始狀態(tài)到目標(biāo)狀態(tài)。