




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
搜索
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-
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 環(huán)保設(shè)計(jì)活動(dòng)方案
- 理發(fā)店周年活動(dòng)方案
- 玩具商場(chǎng)活動(dòng)方案
- 現(xiàn)場(chǎng)簽單活動(dòng)方案
- 物業(yè)春節(jié)送白菜活動(dòng)方案
- 瑜伽與畫畫活動(dòng)方案
- 煙草公司五一活動(dòng)方案
- 愛心大篷車送餐活動(dòng)方案
- 現(xiàn)場(chǎng)備課擂臺(tái)賽活動(dòng)方案
- 班級(jí)室內(nèi)活動(dòng)方案
- 2025至2030中國(guó)銅冶煉行業(yè)發(fā)展現(xiàn)狀及應(yīng)用需求現(xiàn)狀分析報(bào)告
- 打架傷人和解協(xié)議書范本
- 2025至2030全球及中國(guó)浮式液化天然氣行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025年湖北省中考生物、地理合卷試卷真題(含答案)
- 藥品陳列養(yǎng)護(hù)管理制度
- 物理●湖北卷丨2024年湖北省普通高中學(xué)業(yè)水平選擇性考試物理試卷及答案
- 專利基礎(chǔ)知識(shí)教學(xué)課件
- 智能制造MES項(xiàng)目實(shí)施方案(注塑行業(yè)MES方案建議書)
- 四年級(jí)奧數(shù)講義
- 江蘇省南京市2024屆高一數(shù)學(xué)下學(xué)期期末試題(含解析)
- 多旋翼無人機(jī)專業(yè)培訓(xùn)教材ppt課件
評(píng)論
0/150
提交評(píng)論