寬度優(yōu)先搜索

1、寬度優(yōu)先搜索寬度優(yōu)先搜索走迷宮（Maze）【問題描述】已知一NN的迷宮，允許往上、下、左、右四個(gè)方向行走，現(xiàn)請(qǐng)你找出一條從左上角到右下角的最短路徑?！据斎霐?shù)據(jù)】輸入數(shù)據(jù)有若干行，第一行有一個(gè)自然數(shù)N（N20），表示迷宮的大小，其后有N行數(shù)據(jù)，每行有N個(gè)0或1（數(shù)字之間沒有空格，0表示可以通過，1表示不能通過），用以描述迷宮地圖。入口在左上角（1，1）處，出口在右下角（N，N）處。所有迷宮保證存在從入口到出口的可行路徑?！据敵鰯?shù)據(jù)】輸出數(shù)據(jù)僅一行，為從入口到出口的路徑（有多條路徑時(shí)輸出任意一條即可請(qǐng)嚴(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 從左上角開始，找到下一個(gè)能走的路cij=0，然后dfs(i,j),（接著窮舉i,j）下一個(gè)點(diǎn)繼續(xù)dfs,直到找到出口位置。算法2：bfs(寬度優(yōu)先搜索)_利用隊(duì)列實(shí)現(xiàn)入隊(duì)入隊(duì)出隊(duì)出隊(duì) A1 A2 A3 A4 A5 A6 A1A7

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

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

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

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

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

9、s/cpp)給定一個(gè)數(shù)N (ON100000)，變成另一個(gè)數(shù)K(OK100000)，允許的操作是乘以2，或者加減1，問最少要幾步才能完成？【輸入格式】?jī)H有兩個(gè)整數(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個(gè)人，他們的編號(hào)為1n，其中有一些人相互認(rèn)識(shí)，現(xiàn)在x想要認(rèn)識(shí)y，可以通過他所認(rèn)識(shí)的人來認(rèn)識(shí)更多的人（如果a認(rèn)識(shí)b、b認(rèn)識(shí)c，那么a可以通過b來認(rèn)識(shí)c），求出x最少需要

10、通過多少人才能認(rèn)識(shí)y。輸入: 第一行三個(gè)整數(shù)n、x、y；接下來一個(gè)nn的鄰接矩陣，ai,j=1表示i認(rèn)識(shí)j，ai,j=0表示不認(rèn)識(shí)。保證i=j時(shí),ai,j=0,并且ai,j=aj,i。輸出: x認(rèn)識(shí)y最少需要通過的人數(shù)。數(shù)據(jù)保證x一定能認(rèn)識(shí)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加入隊(duì)列并設(shè)置為隊(duì)頭元素，從隊(duì)頭開始進(jìn)行寬搜，窮舉鄰接矩陣的第x行，看x認(rèn)識(shí)誰（判斷ax,j=1），認(rèn)識(shí)的人（j）全部依次入隊(duì)，并且ans:=ans+1，如果出現(xiàn)了y，則

11、輸出ans，結(jié)束搜索，否則，取出隊(duì)頭元素繼續(xù)寬搜。七、bfs應(yīng)用舉例 程序?qū)崿F(xiàn)bfs應(yīng)用舉例小結(jié) 本題是說明“寬搜”的另一個(gè)重要應(yīng)用：求最優(yōu)值問題。比如最少幾次、最快幾步等！思考：如果要輸出x是通過什么關(guān)系（哪些人）認(rèn)識(shí)y的呢？解決：再設(shè)一個(gè)數(shù)據(jù)域（或者數(shù)組），記錄當(dāng)前節(jié)點(diǎn)是從哪個(gè)節(jié)點(diǎn)擴(kuò)展得到的。bfs應(yīng)用舉例例：例：奇怪的電梯（奇怪的電梯（lift.?） 呵呵，有一天我做了一個(gè)夢(mèng)，夢(mèng)見了一種很奇怪的電梯。大樓的每呵呵，有一天我做了一個(gè)夢(mèng)，夢(mèng)見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第一層樓都可以停電梯，而且第i層樓層樓(1=i=N)上有一個(gè)數(shù)字上有一個(gè)數(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)到在一個(gè)狀態(tài)是的，也就是說從當(dāng)前狀態(tài)到在一個(gè)狀態(tài)是盲目盲目的，只能窮舉。如何窮的，只能窮舉。如何窮舉、如何保存每一個(gè)狀態(tài)呢？隊(duì)列！舉、如何保存每一個(gè)狀態(tài)呢？隊(duì)列！ 第四、由于是要輸出最快的倒油方案，所以不應(yīng)該做無謂的倒油操作，第四、由于是要輸出最快的倒油方案，所以不應(yīng)該做無謂的倒油操作，也就是說從一個(gè)狀態(tài)采用一種倒油方法得到的狀態(tài)不能出現(xiàn)過，否則也就是說從一個(gè)狀態(tài)采用一種倒油方法得到的狀態(tài)不能出現(xiàn)過，否則一定不是最快的倒油方案。所以，需要對(duì)一定不是最快的倒油方案。所以，需要對(duì)狀態(tài)狀態(tài)“判重判重”。如何實(shí)現(xiàn)？。如何實(shí)現(xiàn)？窮舉！窮舉！ 第五、因?yàn)橐谖濉⒁驗(yàn)橐敵鼍唧w的倒油步驟輸出具體的倒油步驟，所以要保存各個(gè)狀態(tài)之間是怎么，所以要保存各個(gè)狀態(tài)之間是怎么轉(zhuǎn)移的，以便找到目標(biāo)狀態(tài)后倒過來，按照這個(gè)線索輸出從初始狀態(tài)轉(zhuǎn)移的，以便找到目標(biāo)狀態(tài)后倒過來，按照這個(gè)線索輸出從初始狀態(tài)到目標(biāo)狀態(tài)。