ACM-DFS-BFS匯總教學講解課件

搜索

DFS+BFS

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

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

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

所以，在這里再次強調(diào)“剪枝”！剪枝：通過某種判斷，避免一些不必要的遍歷過程，形象的說剪去了搜索樹中的某些“枝條”。工大ACM團隊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團隊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團隊HDOJ_1010TempteroftheBone

OutputForeachtestcase,printinoneline"YES"ifthedoggiecansurvive,or"NO"otherwise.工大ACM團隊HDOJ_1010TempteroftheBone

SampleInput445S.X...X...XD....345S.X...X....D000工大ACM團隊HDOJ_1010TempteroftheBone

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

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

0->0走1->1必然是偶數(shù)步所以當遇到從0走向0但是要求時間是奇數(shù)的，或者，從1走向0但是要求時間是偶數(shù)的都可以直接判斷不可達！結(jié)論：工大ACM團隊奇偶性剪枝那么設所在位置(x,y)與目標位置(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時恰好到達，那么(ti-step)與abs(x-y)+abs(dx-dy)的奇偶性必須相同因此temp=ti-step-abs(dx-x)-abs(dy-y)必然為偶數(shù)！工大ACM團隊核心代碼voidDfsSerch(int

x,int

y,intstep){

inttemp;temp=ti-step-