ACM-DFS-BFS匯總教學(xué)講解課件

搜索

DFS+BFS

剪枝預(yù)備知識(shí)——樹的遍歷樹的遍歷主要有如下四種方法：1.先根/序遍歷2.中根/序遍歷3.后根/序遍歷4.層次遍歷分別有什么特點(diǎn)呢？工大ACM團(tuán)隊(duì)（1）先根遍歷對(duì)樹的訪問次序是:1.先訪問根結(jié)點(diǎn)2.再訪問左子樹3.最后訪問右子樹4.對(duì)于左右子樹的訪問也要滿足以上規(guī)則示例如下：工大ACM團(tuán)隊(duì)以上二叉樹的先根遍歷序列是：？？21357461、2、4、5、3、6、7工大ACM團(tuán)隊(duì)（2）中根遍歷對(duì)樹的訪問次序是:1.先訪問左子樹2.再訪問根結(jié)點(diǎn)3.最后訪問右子樹4.對(duì)于左右子樹的訪問也要滿足以上規(guī)則示例如下：工大ACM團(tuán)隊(duì)以上二叉樹的中根遍歷序列是：？？21357464、2、5、1、6、3、7工大ACM團(tuán)隊(duì)（3）后根遍歷對(duì)樹的訪問次序是:1.先訪問左子樹2.再訪問右子樹3.最后訪問根結(jié)點(diǎn)4.對(duì)于左右子樹的訪問也要滿足以上規(guī)則示例如下：工大ACM團(tuán)隊(duì)以上二叉樹的后根遍歷序列是：？？21357464、5、2、6、7、3、1工大ACM團(tuán)隊(duì)（4）層次遍歷對(duì)樹的訪問次序是:1.先訪問根結(jié)點(diǎn)2.再訪問根結(jié)點(diǎn)的子節(jié)點(diǎn)（即第二層節(jié)點(diǎn)）3.再訪問第三層節(jié)點(diǎn)4.……示例如下：工大ACM團(tuán)隊(duì)以上二叉樹的層次遍歷序列是：？？21357461、2、3、4、5、6、7工大ACM團(tuán)隊(duì)幾個(gè)基本概念：初始狀態(tài)：略目標(biāo)狀態(tài)：略狀態(tài)空間：由于求解問題的過程中分枝有很多（主要是求解過程中求解條件的不確定性、不完備性造成的），使得求解的路徑很多，這就構(gòu)成了一個(gè)圖，我們說這個(gè)圖就是狀態(tài)空間。狀態(tài)空間搜索：就是將問題求解過程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個(gè)路徑的過程。通俗點(diǎn)說，就是在解一個(gè)問題時(shí)，找到一條解題的過程，可以從求解的開始到問題的結(jié)果。工大ACM團(tuán)隊(duì)DFS+BFS深度優(yōu)先搜索深度優(yōu)先搜索（DepthFirstSearch）類似于樹的先根遍歷深搜例子：走迷宮，你沒有辦法用分身術(shù)來站在每個(gè)走過的位置。不撞南山不回頭。廣度優(yōu)先搜索（BreadthFirstSearch）類似于樹的按層次遍歷的過程廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠(yuǎn)一點(diǎn)的地方……工大ACM團(tuán)隊(duì)深度優(yōu)先搜索基本思想從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個(gè)結(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個(gè)結(jié)點(diǎn)，再檢查是否為目標(biāo)節(jié)點(diǎn)G，若未出現(xiàn)，繼續(xù)以上操作過程，一直進(jìn)行到葉節(jié)點(diǎn)（即不能再生成新狀態(tài)節(jié)點(diǎn)），當(dāng)它仍不是目標(biāo)狀態(tài)G時(shí)，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜索的分支。生成新狀態(tài)節(jié)點(diǎn)。若仍不是目標(biāo)狀態(tài)，就按該分支一直擴(kuò)展到葉節(jié)點(diǎn)，若仍不是目標(biāo)，采用相同的回溯辦法回退到上層節(jié)點(diǎn)，擴(kuò)展可能的分支生成新狀態(tài)，…，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。工大ACM團(tuán)隊(duì)搜索過程如下：HALIFBCDEJGKS深度優(yōu)先搜索示意圖工大ACM團(tuán)隊(duì)廣度優(yōu)先搜索基本思想從初始狀態(tài)S開始，利用規(guī)則，生成所有可能的狀態(tài)。構(gòu)成樹的下一層節(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，就對(duì)該層所有狀態(tài)節(jié)點(diǎn)，分別順序利用規(guī)則。生成再下一層的所有狀態(tài)節(jié)點(diǎn)，對(duì)這一層的所有狀態(tài)節(jié)點(diǎn)檢查是否出現(xiàn)G，若未出現(xiàn)，繼續(xù)按上面思想生成再下一層的所有狀態(tài)節(jié)點(diǎn)，這樣一層一層往下展開。直到出現(xiàn)目標(biāo)狀態(tài)為止。工大ACM團(tuán)隊(duì)搜索過程如下：OPLWVUTRQABCDGEFS廣度優(yōu)先搜索示意圖工大ACM團(tuán)隊(duì)

BFS、DFS算法比較DFS：使用棧保存未被檢測(cè)的結(jié)點(diǎn)，結(jié)點(diǎn)按照深度優(yōu)先的次序被訪問并依次被壓入棧中，并以相反的次序出棧進(jìn)行新的檢測(cè)。

BFS：使用隊(duì)列保存未被檢測(cè)的結(jié)點(diǎn)。結(jié)點(diǎn)按照寬度優(yōu)先的次序被訪問和進(jìn)、出隊(duì)列。工大ACM團(tuán)隊(duì)8123456781234567入口出口迷宮問題-DFS尋找一條從入口到出口的通路工大ACM團(tuán)隊(duì)東南迷宮問題(續(xù))北(上)西(左)前進(jìn)方向：上(北)、下(南)、左(西)、右(東)首先從下方開始，按照逆時(shí)針方向搜索下一步可能前進(jìn)的位置工大ACM團(tuán)隊(duì)迷宮問題(續(xù))入口出口在迷宮周圍加墻，避免判斷是否出界81234567812345679090工大ACM團(tuán)隊(duì)8123456781234567迷宮問題(續(xù))9090在尋找出口的過程中，每前進(jìn)一步，當(dāng)前位置入棧；每回退一步，棧頂元素出棧棧(1,1)工大ACM團(tuán)隊(duì)i8123456781234567迷宮問題(續(xù))9090棧(1,1)(2,1)向下方前進(jìn)一步工大ACM團(tuán)隊(duì)i迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)i(3,1)向下方前進(jìn)一步工大ACM團(tuán)隊(duì)ii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(4,1)(3,1)i向下方前進(jìn)一步break工大ACM團(tuán)隊(duì)iiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(5,1)(3,1)(4,1)向下方前進(jìn)一步break工大ACM團(tuán)隊(duì)iiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前進(jìn)一步break工大ACM團(tuán)隊(duì)iiiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前進(jìn)一步break工大ACM團(tuán)隊(duì)iiiiii@迷宮問題(續(xù))81234567812345679090向下方、右方、左方均不能前進(jìn)，上方是來路，則后退棧(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)break工大ACM團(tuán)隊(duì)iiiii@@迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前進(jìn)，下方路不通，上方是來路，則后退break工大ACM團(tuán)隊(duì)iiiii@@81234567迷宮問題(續(xù))0981234567812345679090棧(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前進(jìn)一步break工大ACM團(tuán)隊(duì)iiiiii@@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break工大ACM團(tuán)隊(duì)iiiiiii@@81234567迷宮問題(續(xù))0981234567812345679090向下方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)break工大ACM團(tuán)隊(duì)iiiiiii@@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak工大ACM團(tuán)隊(duì)iiiiiii@ii@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break工大ACM團(tuán)隊(duì)iiiiiii@iii@81234567迷宮問題(續(xù))0981234567812345679090向下方前進(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工大ACM團(tuán)隊(duì)iiiiiii@iii@i迷宮問題(續(xù))81234567812345679090向下方前進(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工大ACM團(tuán)隊(duì)iiiiiii@iii@ii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(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工大ACM團(tuán)隊(duì)iiiiiii@iii@iii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(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)(8,5)(8,6)break工大ACM團(tuán)隊(duì)iiiiiii@iii@ii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(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)ii(8,7)break工大ACM團(tuán)隊(duì)iiiiiii@iii@iiii81234567迷宮問題(續(xù))981234567090用棧保存了路徑棧(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)(8,7)工大ACM團(tuán)隊(duì)迷宮問題(最短路徑)-BFS入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)11迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)1122迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)112233迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)11223434迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)11223453455迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)11262345345656迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)17126723453456576迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)17812678234534565786迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090工大ACM團(tuán)隊(duì)1789126782345345657896迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909工大ACM團(tuán)隊(duì)178912678234510310456105789610迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909工大ACM團(tuán)隊(duì)1789126782345101131110114561011578961011迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909工大ACM團(tuán)隊(duì)17891267812234510113111011124561011125789610121112迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909工大ACM團(tuán)隊(duì)1789131267812234510113111011124561011121357896101312111213迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909工大ACM團(tuán)隊(duì)1789131267812234510113111011124561011121357896101312111213迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909工大ACM團(tuán)隊(duì)小結(jié) 廣度和深度優(yōu)先搜索有一個(gè)很大的缺陷,就是他們都是在一個(gè)給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測(cè)的情況下就不可取了。他的效率實(shí)在太低，甚至不可完成。

所以，在這里再次強(qiáng)調(diào)“剪枝”！剪枝：通過某種判斷，避免一些不必要的遍歷過程，形象的說剪去了搜索樹中的某些“枝條”。工大ACM團(tuán)隊(duì)HDOJ_1010TempteroftheBone

ProblemDescriptionThedoggiefoundaboneinanancientmaze,whichfascinatedhimalot.However,whenhepickeditup,themazebegantoshake,andthedoggiecouldfeelthegroundsinking.Herealizedthatthebonewasatrap,andhetrieddesperatelytogetoutofthismaze.

ThemazewasarectanglewithsizesNbyM.Therewasadoorinthemaze.Atthebeginning,thedoorwasclosedanditwouldopenattheT-thsecondforashortperiodoftime(lessthan1second).ThereforethedoggiehadtoarriveatthedooronexactlytheT-thsecond.Ineverysecond,hecouldmoveoneblocktooneoftheupper,lower,leftandrightneighboringblocks.Onceheenteredablock,thegroundofthisblockwouldstarttosinkanddisappearinthenextsecond.Hecouldnotstayatoneblockformorethanonesecond,norcouldhemoveintoavisitedblock.Canthepoordoggiesurvive?Pleasehelphim工大ACM團(tuán)隊(duì)HDOJ_1010TempteroftheBone

InputTheinputconsistsofmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1<N,M<7;0<T<50),whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen,respectively.ThenextNlinesgivethemazelayout,witheachlinecontainingMcharacters.Acharacterisoneofthefollowing:

'X':ablockofwall,whichthedoggiecannotenter;

'S':thestartpointofthedoggie;

'D':theDoor;or

'.':anemptyblock.

Theinputisterminatedwiththree0's.Thistestcaseisnottobeprocessed工大ACM團(tuán)隊(duì)HDOJ_1010TempteroftheBone

OutputForeachtestcase,printinoneline"YES"ifthedoggiecansurvive,or"NO"otherwise.工大ACM團(tuán)隊(duì)HDOJ_1010TempteroftheBone

SampleInput445S.X...X...XD....345S.X...X....D000工大ACM團(tuán)隊(duì)HDOJ_1010TempteroftheBone

SampleOutputNOYES工大ACM團(tuán)隊(duì)要點(diǎn)分析：典型的迷宮搜索，做出該題將具有里程碑式的意義！能不能枚舉出所有抵達(dá)方案，再在通過檢查時(shí)間時(shí)間是否吻合，得到結(jié)果，用DFS進(jìn)行搜索。DFS搜索完成后，發(fā)現(xiàn)超時(shí)，得剪枝才行。工大ACM團(tuán)隊(duì)想到了什么剪枝條件？每個(gè)block只能走一次要求恰好某個(gè)給定的時(shí)間到達(dá)出口如果可走的block的總數(shù)小于時(shí)間，將會(huì)產(chǎn)生什么情況？還想到什么剪枝？工大ACM團(tuán)隊(duì)奇偶性剪枝可以把map看成這樣：010101101010010101101010010101從為0的格子走一步，必然走向?yàn)?的格子從為1的格子走一步，必然走向?yàn)?的格子即：

0->1或1->0必然是奇數(shù)步

0->0走1->1必然是偶數(shù)步所以當(dāng)遇到從0走向0但是要求時(shí)間是奇數(shù)的，或者，從1走向0但是要求時(shí)間是偶數(shù)的都可以直接判斷不可達(dá)！結(jié)論：工大ACM團(tuán)隊(duì)奇偶性剪枝那么設(shè)所在位置(x,y)與目標(biāo)位置(dx,dy)如果abs(dx-x)+abs(dy-y)為偶數(shù)，則說明abs(dx-x)+和abs(dy-y)的奇偶性相同，需要走偶數(shù)步如果abs(dx-x)+abs(dy-y)為奇數(shù)，那么說明abs(dx-x)和abs(dy-y)的奇偶性不同，需要走奇數(shù)步解為abs(dx-sx)+abs(dy-sy)的奇偶性就確定了所需要的步數(shù)的奇偶性??！而(ti-setp)表示剩下還需要走的步數(shù)，由于題目要求要在ti時(shí)恰好到達(dá)，那么(ti-step)與abs(x-y)+abs(dx-dy)的奇偶性必須相同因此temp=ti-step-abs(dx-x)-abs(dy-y)必然為偶數(shù)！工大ACM團(tuán)隊(duì)核心代碼voidDfsSerch(int

x,int

y,intstep){

inttemp;temp=ti-step-