廣度優(yōu)先搜索-課件

1、廣度優(yōu)先搜索（BFS）趙和旭廣度優(yōu)先搜索（BFS）趙和旭廣度優(yōu)先搜索廣度優(yōu)先搜索是一種分層的查找過程，每向前一層可能會(huì)訪問一批頂點(diǎn)，不像深度優(yōu)先搜索有回溯的過程。同時(shí)與深搜用棧來維護(hù)不同，廣搜一般是用先進(jìn)先出隊(duì)列來進(jìn)行維護(hù)的。實(shí)際上我們從初始狀態(tài)開始，搜索第k層的意義就是，搜索需要k步才能到達(dá)的狀態(tài)。廣度優(yōu)先搜索廣度優(yōu)先搜索是一種分層的查找過程，每向前一層可能廣度優(yōu)先搜索具體操作、特點(diǎn)具體操作：它是先將起始狀態(tài)加入隊(duì)列，然后每次從隊(duì)列中取出一個(gè)狀態(tài)，將其后繼狀態(tài)加入隊(duì)列，后繼狀態(tài)指的是由當(dāng)前狀態(tài)一步操作可以到達(dá)的狀態(tài)，直到所有狀態(tài)均被訪問為止。廣度優(yōu)先搜索具體操作、特點(diǎn)具體操作：廣度優(yōu)先搜索具

2、體操作、特點(diǎn)特點(diǎn)：1:它并不考慮結(jié)果的可能位置，而是徹底地搜索所有狀態(tài)，所以很少有基于 BFS 的啟發(fā)式算法，也很少對(duì) BFS 進(jìn)行剪枝。2:相對(duì)于 DFS，BFS 更加難于保存當(dāng)前節(jié)點(diǎn)的狀態(tài)，所以 BFS 在爆搜中的應(yīng)用較少。廣度優(yōu)先搜索具體操作、特點(diǎn)3：在某一層還沒有搜索完時(shí)，是不會(huì)進(jìn)入下一層的，也就是說在隊(duì)列中所有同一深度的狀態(tài)，是連續(xù)的一段。（這個(gè)性質(zhì)在之后會(huì)用到?。V度優(yōu)先搜索具體操作、特點(diǎn)3：在某一層還沒有搜索完時(shí)，是不會(huì)進(jìn)入下一層的，也就是說在隊(duì)經(jīng)典例題1引出廣度優(yōu)先搜索給出一個(gè)n個(gè)點(diǎn)m條的邊長(zhǎng)均為1的無向圖，求1到n的最短路。n=105，m=3*105經(jīng)典例題1引出廣度優(yōu)先搜索

3、給出一個(gè)n個(gè)點(diǎn)m條的邊長(zhǎng)均為1最短路問題？迪杰斯特拉算法，spfa？有沒有更快的做法？我們是不是要看一看題目有什么特殊性質(zhì)。經(jīng)典例題1引出廣度優(yōu)先搜索最短路問題？經(jīng)典例題1引出廣度優(yōu)先搜索對(duì)于邊長(zhǎng)為1的最短路徑問題，我們可以廣度優(yōu)先搜索，使復(fù)雜度變?yōu)镺(N)，比迪杰斯特拉更加優(yōu)。（重要套路！）我們來模擬一下這個(gè)過程。經(jīng)典例題1引出廣度優(yōu)先搜索對(duì)于邊長(zhǎng)為1的最短路徑問題，我們可以廣度優(yōu)先搜索，使復(fù)雜度變經(jīng)典例題1引出廣度優(yōu)先搜索求1到n的最短路。最開始的時(shí)候?qū)?號(hào)節(jié)點(diǎn)（初始狀態(tài)）加入隊(duì)列。作為第一層的元素。然后我們每一次會(huì)取出隊(duì)首元素，擴(kuò)展其相鄰點(diǎn)，作為第2層。第二層：2、3。經(jīng)典例題1引出廣度

4、優(yōu)先搜索求1到n的最短路。然后由第二層擴(kuò)展第三層，不斷重復(fù)取出隊(duì)首元素，擴(kuò)展相鄰且未經(jīng)過的點(diǎn)。第三層：4、5、6。第四層：7、8。第五層：9。這樣我們就得到了9號(hào)節(jié)點(diǎn)到1號(hào)點(diǎn)的距離為4。經(jīng)典例題1引出廣度優(yōu)先搜索然后由第二層擴(kuò)展第三層，不斷重復(fù)取出隊(duì)首元素，擴(kuò)展相鄰且未經(jīng)經(jīng)典例題1代碼實(shí)現(xiàn)經(jīng)典例題1代碼實(shí)現(xiàn)經(jīng)典例題1代碼實(shí)現(xiàn)注釋在代碼中。經(jīng)典例題1代碼實(shí)現(xiàn)注釋在代碼中。廣搜一般的代碼實(shí)現(xiàn)方式廣搜一般的代碼實(shí)現(xiàn)方式經(jīng)典問題1的變形給出一個(gè)n個(gè)點(diǎn)m條的邊長(zhǎng)為0或者1的無向圖，求1到n的最短路。n=105，m=3*105經(jīng)典問題1的變形給出一個(gè)n個(gè)點(diǎn)m條的邊長(zhǎng)為0或者1的無向圖，這也是一個(gè)比較經(jīng)典的

5、技巧，同時(shí)也非常巧妙。提示：在新元素加進(jìn)隊(duì)列的時(shí)候，可不可以處理一下？經(jīng)典問題1的變形這也是一個(gè)比較經(jīng)典的技巧，同時(shí)也非常巧妙。經(jīng)典問題1的變形我們考慮在遍歷新的節(jié)點(diǎn)的時(shí)候，分邊為0和1進(jìn)行討論。如果遍歷過去經(jīng)過0這條邊，加到隊(duì)首。如果遍歷過去經(jīng)過1這條邊，加到隊(duì)尾。然后就ok了。怎么這么簡(jiǎn)單？為什么？經(jīng)典問題1的變形我們考慮在遍歷新的節(jié)點(diǎn)的時(shí)候，分邊為0和1進(jìn)行討論。經(jīng)典問題實(shí)際上我們發(fā)現(xiàn)，整個(gè)這個(gè)隊(duì)列中從前到后的點(diǎn)，就是按照和1號(hào)點(diǎn)距離從小到大排序的。而我們對(duì)于當(dāng)前點(diǎn)u，新加進(jìn)去的點(diǎn)v，如果邊長(zhǎng)度為0，那么v和u到1號(hào)點(diǎn)的距離相同，所以是要加到隊(duì)首，在當(dāng)前它是沒有遍歷到的點(diǎn)中距離1最近的。

6、經(jīng)典問題1的變形實(shí)際上我們發(fā)現(xiàn)，整個(gè)這個(gè)隊(duì)列中從前到后的點(diǎn)，就是按照和1號(hào)點(diǎn)而同理，如果是邊長(zhǎng)度為1，那當(dāng)前肯定是距離1最遠(yuǎn)的，要加到隊(duì)列的后面。經(jīng)典問題1的變形經(jīng)典問題1的變形對(duì)于這個(gè)隊(duì)列的一些性質(zhì)的證明1：對(duì)于每一時(shí)刻，隊(duì)列中的所有點(diǎn)到1的距離，最大值和最小值最多相差1。2：隊(duì)列內(nèi)部的點(diǎn)，到1的距離是單調(diào)不下降的。3：我們每一次加進(jìn)去一個(gè)點(diǎn)，一定是當(dāng)前所能到達(dá)的點(diǎn)中距離1最遠(yuǎn)的。對(duì)于這個(gè)隊(duì)列的一些性質(zhì)的證明1：對(duì)于每一時(shí)刻，隊(duì)列中的所有點(diǎn)經(jīng)典問題2數(shù)聯(lián)通塊給出一個(gè)n*m的網(wǎng)格，每一個(gè)有一個(gè)顏色，兩個(gè)格子之間相連當(dāng)且僅當(dāng)，兩個(gè)格子相連且顏色相同。求聯(lián)通塊的數(shù)量。n*m=105經(jīng)典問題2數(shù)聯(lián)通

7、塊給出一個(gè)n*m的網(wǎng)格，每一個(gè)有一個(gè)顏色舉個(gè)例子：n=4 , m=51 2 1 2 3 1 1 1 2 32 2 2 2 33 3 3 3 3在這個(gè)問題中聯(lián)通塊的數(shù)量為4。經(jīng)典問題2數(shù)聯(lián)通塊舉個(gè)例子：經(jīng)典問題2數(shù)聯(lián)通塊我們從上到下，從左到右，以此遍歷每一個(gè)點(diǎn)，如果某一個(gè)點(diǎn)沒有遍歷到過，那么ans+，并遍歷整個(gè)相鄰的聯(lián)通塊。怎么代碼實(shí)現(xiàn)？經(jīng)典問題2數(shù)聯(lián)通塊我們從上到下，從左到右，以此遍歷每一個(gè)點(diǎn)，如果某一個(gè)點(diǎn)沒有遍經(jīng)典問題2數(shù)聯(lián)通塊代碼實(shí)現(xiàn)經(jīng)典問題2數(shù)聯(lián)通塊代碼實(shí)現(xiàn)有一個(gè)非常經(jīng)典的編碼技巧。對(duì)于當(dāng)前所在的格子，你怎么遍歷所有的相鄰格子？QAQ：“4個(gè)if，枚舉4個(gè)方向”其實(shí)有更簡(jiǎn)單辦法，且拓展性

8、很強(qiáng)的方法。經(jīng)典問題2數(shù)聯(lián)通塊一個(gè)代碼技巧有一個(gè)非常經(jīng)典的編碼技巧。經(jīng)典問題2數(shù)聯(lián)通塊一個(gè)代碼圖1：圖2：經(jīng)典問題2數(shù)聯(lián)通塊一個(gè)代碼技巧圖1：經(jīng)典問題2數(shù)聯(lián)通塊一個(gè)代碼技巧 我們發(fā)現(xiàn)，這樣寫，就可以用一個(gè)for循環(huán)，代替4個(gè)if。其實(shí)如果需要遍歷8聯(lián)通的格子，也是一樣的。它的可拓展性非常強(qiáng)。經(jīng)典問題2數(shù)聯(lián)通塊一個(gè)代碼技巧 我們發(fā)現(xiàn)，這樣寫，就可以用一個(gè)for循環(huán)，代替4個(gè)if。經(jīng)典問題3走迷宮給出一個(gè)n*m的網(wǎng)格，其中有一些格子是障礙“*”,不能經(jīng)過，其他位置是空地“.”，初始時(shí)Bob被放在一個(gè)位置，求Bob最少走多少步可以走出網(wǎng)格。如果永遠(yuǎn)都不能走出網(wǎng)格，輸出 -1 。n,m=1000經(jīng)典問

9、題3走迷宮給出一個(gè)n*m的網(wǎng)格，其中有一些格子是障舉個(gè)例子：一個(gè)5*5的迷宮，初始在S：(4,3)* * * * * . . . * . * . .* . S * .* * * * *紅色的為走出迷宮的路線。經(jīng)典問題3走迷宮舉個(gè)例子：一個(gè)5*5的迷宮，初始在S：(4,3)經(jīng)典問題3還是套用最開始給出的bfs的方法。最開始將初始坐標(biāo)加入隊(duì)列，然后每一次取出隊(duì)首，擴(kuò)展相鄰沒有遍歷到過的點(diǎn)，然后加入隊(duì)列中。如果某一時(shí)刻我們發(fā)現(xiàn)走出了網(wǎng)格了，那么直接輸出當(dāng)前的步數(shù)即可。如果隊(duì)列空了，還是沒有走出網(wǎng)格，說明無解，輸出-1。經(jīng)典問題3走迷宮還是套用最開始給出的bfs的方法。經(jīng)典問題3走迷宮經(jīng)典問題3走迷宮

10、代碼實(shí)現(xiàn)經(jīng)典問題3走迷宮代碼實(shí)現(xiàn)八數(shù)碼問題在33的棋盤上，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤中留有一個(gè)空格，空格用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：給出一種初始布局（初始狀態(tài)）和目標(biāo)布局，找到一種最少步驟的移動(dòng)方法，實(shí)現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變。例：八數(shù)碼問題在33的棋盤上，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至八數(shù)碼問題每一次移動(dòng)算是一步，也就是說這是一個(gè)由初始狀態(tài)到目標(biāo)狀態(tài)的所有邊長(zhǎng)均為1的最短路徑問題。(這里狀態(tài)指的是什么？)考慮bfs。實(shí)際上每一步，只需考慮空白格子和周圍哪一個(gè)格子交換即可。咦？感覺交換兩次可能會(huì)回到原先的狀態(tài)？八數(shù)碼問題每一次移動(dòng)算是

11、一步，也就是說這是一個(gè)由初始狀態(tài)到目需要對(duì)每一個(gè)局面進(jìn)行hash。（用數(shù)字來表示這個(gè)局面，便于儲(chǔ)存和判斷）我們發(fā)現(xiàn)如果把三行拼在一起，那么這個(gè)棋盤就拼成了一個(gè)排列了。而排列和棋盤一一對(duì)應(yīng)！計(jì)算可得：9!=362880。也就是說狀態(tài)還是比較少的，對(duì)于排列的hash有一種很經(jīng)典的方式叫做康拓展開。八數(shù)碼問題需要對(duì)每一個(gè)局面進(jìn)行hash。（用數(shù)字來表示這個(gè)局面，便于儲(chǔ)康拓展開考慮一個(gè)0.(n-1)的排列 a0.(n-1)。HASH=a0*(n-1)!+a1*(n-2)!+.+a2*(n-3)!+.+an-1*0! ，其中ai為當(dāng)前未出現(xiàn)的元素中是排在第幾個(gè)(從0開始)。逆展開的話就是每次除以一個(gè)階乘

12、，商為當(dāng)前這個(gè)數(shù)是什么，余數(shù)則繼續(xù)做下去?？低卣归_考慮一個(gè)0.(n-1)的排列 a0.(n-1)康拓展開例子2 、0、 1展開= 2*2！ + 0 * 1！ + 0*0！同學(xué)們自己試一試3 、2、 0、 1的展開。這個(gè)康拓展開的本質(zhì)是這個(gè)排列的字典序排名?？低卣归_例子2 、0、 1展開對(duì)于0，1，2的排列，求3對(duì)應(yīng)的排列。3/(2!) = 1 余1 1/(1!) =1 余 00/(0!)=0 余 0最后的答案是 1，2，0康拓逆展開例子對(duì)于0，1，2的排列，求3對(duì)應(yīng)的排列?？低啬嬲归_例子codevs1004四子連棋在一個(gè)4*4的棋盤上擺放了14顆棋子，其中有7顆白色棋子，7顆黑色棋子，有兩個(gè)空

13、白地帶，任何一顆黑白棋子都可以向上下左右四個(gè)方向移動(dòng)到相鄰的空格，這叫行棋一步，黑白雙方交替走棋，任意一方可以先走，如果某個(gè)時(shí)刻使得任意一種顏色的棋子形成四個(gè)一線（包括斜線），這樣的狀態(tài)為目標(biāo)棋局。codevs1004四子連棋在一個(gè)4*4的棋盤上擺放了14顆是八數(shù)碼問題的加強(qiáng)版。思路還是一樣的，就是對(duì)于當(dāng)前狀態(tài)，我們看一看移動(dòng)哪一個(gè)棋子就好。關(guān)鍵還是找一個(gè)hash函數(shù)，表示每一個(gè)狀態(tài)。codevs1004四子連棋是八數(shù)碼問題的加強(qiáng)版。codevs1004四子連棋hash函數(shù)：用一個(gè)二進(jìn)制或者三進(jìn)制來表示。代碼怎么寫？codevs1004四子連棋hash函數(shù)：用一個(gè)二進(jìn)制或者三進(jìn)制來表示。cod

14、evs10bzoj4395不太一樣的bfs 有N*N個(gè)房間，組成了一張N*N的網(wǎng)格圖，Bessie一開始位于左上角(1,1)，并且只能上下左右行走。 一開始，只有(1,1)這個(gè)房間的燈是亮著的，Bessie只能在亮著燈的房間里活動(dòng)。 有另外M條信息，每條信息包含四個(gè)數(shù)a,b,c,d，表示房間(a,b)里有房間(c,d)的燈的開關(guān)。 請(qǐng)計(jì)算出最多有多少個(gè)房間的燈可以被打開bzoj4395不太一樣的bfs 有N*N個(gè)房間在這個(gè)問題中我們需要考慮一下，什么樣的格子，是可以遍歷到的。1：與原先遍歷到過的點(diǎn)相鄰。2：這個(gè)格子的燈是開著的。這只有這兩個(gè)條件滿足時(shí)，我們才可以把一個(gè)格子加入隊(duì)列里。bzoj4

15、395不太一樣的bfs在這個(gè)問題中bzoj4395不太一樣的bfs然后思路比較自然了。我們對(duì)于每一個(gè)格子記錄是否與當(dāng)前遍歷到的格子相鄰，以及是否亮燈。兩種情況滿足時(shí)，加入隊(duì)列即可。bzoj4395不太一樣的bfs然后思路比較自然了。bzoj4395不太一樣的bfs雙向廣搜 所謂雙向廣搜，就是初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)同時(shí)擴(kuò)展，直至在兩個(gè)擴(kuò)展方向上出現(xiàn)同一個(gè)結(jié)點(diǎn)，搜索結(jié)束。 普通的廣搜是：從初始狀態(tài)開始，一層一層不斷擴(kuò)展直到發(fā)現(xiàn)目標(biāo)狀態(tài)。 雙向廣搜：從初始和結(jié)束狀態(tài)分別開始擴(kuò)展，直到兩方擴(kuò)展的狀態(tài)相遇。雙向廣搜 所謂雙向廣搜，就是初始結(jié)點(diǎn)向目標(biāo)結(jié)雙向廣搜優(yōu)點(diǎn)？ 速度快！我們用兩張圖來

16、對(duì)比一下。雙向廣搜優(yōu)點(diǎn)？ 速度快！我們用兩張圖來對(duì)比一下。雙向廣搜優(yōu)點(diǎn)？ 速度快！單向廣搜的遍歷空間：雙向廣搜優(yōu)點(diǎn)？ 速度快！雙向廣搜優(yōu)點(diǎn)？ 速度快！雙向廣搜的遍歷空間：雙向廣搜優(yōu)點(diǎn)？ 速度快！雙向廣搜缺點(diǎn)？主要是編碼難度大，對(duì)代碼能力的要求比較高。所以在考場(chǎng)上，如果時(shí)間沒有那么充足，對(duì)雙向廣搜沒有那么熟練的話，不建議寫雙廣搜。雙向廣搜缺點(diǎn)？主要是編碼難度大，對(duì)代碼能力的要求比較高。雙向廣搜一般代碼實(shí)現(xiàn)方式雙向廣搜一般代碼實(shí)現(xiàn)方式雙向廣搜注意事項(xiàng)對(duì)于遍歷，擴(kuò)展節(jié)點(diǎn)時(shí)：要每次擴(kuò)展一層，而不是每次擴(kuò)展一個(gè)節(jié)點(diǎn)！反例？雙向廣搜注意事項(xiàng)對(duì)于遍歷，擴(kuò)展節(jié)點(diǎn)時(shí)：雙向廣搜注意事項(xiàng)雙向廣搜注意事項(xiàng)bzoj50

17、49Lydsy九月月賽導(dǎo)航系統(tǒng)這個(gè)國(guó)度由n座城市和m條雙向道路構(gòu)成。因?yàn)檫@個(gè)國(guó)度崇尚隨機(jī)，因此m條邊是用隨機(jī)選擇兩端點(diǎn)的方式生成的。充滿好奇的小Q想在這里進(jìn)行k次隨機(jī)的旅行，每次的起點(diǎn)和終點(diǎn)也是隨機(jī)選擇的。bzoj5049Lydsy九月月賽導(dǎo)航系統(tǒng)這個(gè)國(guó)度由n座bzoj5049Lydsy九月月賽導(dǎo)航系統(tǒng)在每次出發(fā)之前，他會(huì)使用導(dǎo)航系統(tǒng)計(jì)算兩點(diǎn)間最少需要經(jīng)過幾條道路。請(qǐng)寫一個(gè)程序，幫助小Q計(jì)算兩點(diǎn)間的最短路。n=100000,m=300000,kB-C-D-E-F-G-I-J-H-K 每一次搜到底！深度優(yōu)先搜索: A-B-C-D-E-F-G-I廣度優(yōu)先搜索 A- （第一層） B-E-K- （第二層）C-D-F-G-H （第三層）I-J （第四層） 一層一層搜索！廣度優(yōu)先搜索 A- （第一層）廣搜廣搜是一層一層，一步一步，所以很多求最短方案，最少的步驟數(shù)的搜索問題，考慮廣搜。這種時(shí)候若用深搜，往往會(huì)沒有一個(gè)明確的終止范圍，容易搜索的過深，導(dǎo)致效率低下。廣搜廣搜是一層一層，一步一步，所以很多求最短方案，最少的步驟深搜深搜往往是把所有可行的情況列舉出來了，找一個(gè)最優(yōu)解，不一定是最短的步數(shù)。不是有的深搜也是求最短步數(shù)嗎？注意廣搜是一般不好加剪枝，但是深搜的剪枝使用比較方便，當(dāng)搜索的界限比較明確，你也有一個(gè)比較成熟剪枝方案時(shí)，深搜是可以代替廣搜找最短步數(shù)的。深搜深搜往往是把所有可行的