ACM算法設(shè)計(jì)-BFS(廣度搜索)-DFS入門(mén)(深度搜索)詳解.ppt

1、2020/7/15,ACM算法設(shè)計(jì)BFS(廣度搜索)-DFS(深度搜索)詳解,BFS算法,by plato,3,復(fù)習(xí)DFS算法,思想： 一直往深處走，直到找到解或者走不下去為止 框架： DFS(dep,) /dep代表目前DFS的深度 if (找到解|走不下去了) return; 枚舉下一種情況，DFS(dep+1,) ,4,DFS的遍歷方式,H,A,L,I,F,B,C,D,E,J,G,K,S,5,存在其他的遍歷方式？,6,BFS的思想,1.從初始狀態(tài)S開(kāi)始，利用規(guī)則，生成下一層的狀態(tài)。 2.順序檢查下一層的所有狀態(tài)，看是否出現(xiàn)目標(biāo)狀態(tài)G。 否則就對(duì)該層所有狀態(tài)節(jié)點(diǎn)，分別利用規(guī)則。生成再下一層

2、的所有狀 態(tài)節(jié)點(diǎn)。 3.繼續(xù)按上面思想生成再下一層的所有狀態(tài)節(jié)點(diǎn)，這樣一層一層往下展開(kāi)。直到出現(xiàn)目標(biāo)狀態(tài)為止。 按層次的順序來(lái)遍歷搜索樹(shù),7,BFS框架,通常用隊(duì)列(先進(jìn)先出,FIFO)實(shí)現(xiàn) 初始化隊(duì)列Q. Q=起點(diǎn)s; 標(biāo)記s為己訪問(wèn); while (Q非空) 取Q隊(duì)首元素u; u出隊(duì); if (u = 目標(biāo)狀態(tài)) 所有與u相鄰且未被訪問(wèn)的點(diǎn)進(jìn)入隊(duì)列; 標(biāo)記u為已訪問(wèn); ,8,尋找一條從入口到出口的通路,迷宮問(wèn)題,9,東,南,北(上),西(左),前進(jìn)方向：上(北)、下(南)、左(西)、右(東),首先從下方開(kāi)始，按照逆時(shí)針?lè)较蛩阉飨乱徊娇赡芮斑M(jìn)的位置,迷宮問(wèn)題-DFS,10,入口,出口,在迷宮

3、周?chē)訅?，避免判斷是否出?8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題-DFS,11,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,在尋找出口的過(guò)程中，每前進(jìn)一步，當(dāng)前位置入棧；每回退一步，棧頂元素出棧,迷宮問(wèn)題-DFS,12,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),向下方前進(jìn)一步,迷宮問(wèn)題-DFS,13,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),i,(3,1),向下方前進(jìn)一

4、步,迷宮問(wèn)題-DFS,14,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(4,1),(3,1),i,向下方前進(jìn)一步,break,迷宮問(wèn)題-DFS,15,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(5,1),(3,1),(4,1),向下方前進(jìn)一步,break,迷宮問(wèn)題-DFS,16,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(6,1),(3,1),(4,1),

5、(5,1),向下方前進(jìn)一步,break,迷宮問(wèn)題-DFS,17,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),向下方前進(jìn)一步,break,18,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方 、右方、左方均不能前進(jìn)，上方是來(lái)路，則后退,棧,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,迷宮問(wèn)題-DFS,19,i,i,i,i

6、,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),向右方、左方均不能前進(jìn)，下方路不通，上方是來(lái)路，則后退,break,迷宮問(wèn)題-DFS,20,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前進(jìn)一步,break,迷宮問(wèn)題-DFS,21,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5

7、,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(5,3),(5,2),break,迷宮問(wèn)題-DFS,22,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(5,2),(5,3),break,迷宮問(wèn)題-DFS,23,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向

8、右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,4),(5,2),(5,3),(6,3),i,break,迷宮問(wèn)題-DFS,24,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,5),(5,2),(5,3),(6,3),(6,4),break,迷宮問(wèn)題-DFS,25,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4

9、,5,6,7,9,0,9,0,向下方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(7,5),(5,2),(5,3),(6,3),(6,4),(6,5),break,迷宮問(wèn)題-DFS,26,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,5),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,迷宮問(wèn)題-DFS,27,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2

10、,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,迷宮問(wèn)題-DFS,28,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,7),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5)

11、,(8,5),(8,6),break,迷宮問(wèn)題-DFS,29,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步，到達(dá)出口,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),i,i,(8,7),break,迷宮問(wèn)題-DFS,30,i,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,9,0,用棧保存了路徑,棧,(1,1),(2,1),(3

12、,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),(8,7),迷宮問(wèn)題-DFS,31,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,32,1,1,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,33,1,1,2,2,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑

13、(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,34,1,1,2,2,3,3,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,35,1,1,2,2,3,4,3,4,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,36,1,1,2,2,3,4,5,3,4,5,5,入口,出口,借助于隊(duì)

14、列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,37,1,1,2,6,2,3,4,5,3,4,5,6,5,6,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,38,1,7,1,2,6,7,2,3,4,5,3,4,5,6,5,7,6,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮

15、問(wèn)題(最短路徑)-BFS,39,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,6,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宮問(wèn)題(最短路徑)-BFS,40,1,7,8,9,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,9,6,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宮問(wèn)題(最短路徑)-BFS,41,1,7,8,9,1,2,6,7,8,2,3,

16、4,5,10,3,10,4,5,6,10,5,7,8,9,6,10,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宮問(wèn)題(最短路徑)-BFS,42,1,7,8,9,1,2,6,7,8,2,3,4,5,10,11,3,11,10,11,4,5,6,10,11,5,7,8,9,6,10,11,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宮問(wèn)題(最短路徑)-BFS,43,1,7,8,9,1,2,6,7

17、,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,5,7,8,9,6,10,12,11,12,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宮問(wèn)題(最短路徑)-BFS,44,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5

18、,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宮問(wèn)題(最短路徑)-BFS,45,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宮問(wèn)題(最短路徑)-BFS,46,小結(jié),DFS：使用棧保存未被檢測(cè)的結(jié)點(diǎn)，結(jié)點(diǎn)按照深度優(yōu)先的次序被訪問(wèn)并依次被壓入棧中，并以相反的次序出棧進(jìn)行新的檢測(cè)。 類(lèi)似于樹(shù)的先根遍歷 深搜例子：走迷宮，你沒(méi)有辦法用分身術(shù)來(lái)站在每個(gè)走過(guò)的位置。不撞南山不回頭。 BFS：使用隊(duì)列保存未被檢測(cè)的結(jié)點(diǎn)。結(jié)點(diǎn)按照寬度優(yōu)先的次序被訪問(wèn)和進(jìn)、出隊(duì)列。 類(lèi)似于樹(shù)的按層次遍歷的過(guò)程 廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是