8. 深度優(yōu)先搜索.ppt

1、第七講,搜索專題 深度優(yōu)先（DFS）,ACM算法與程序設(shè)計(jì),深度優(yōu)先搜索算法（Depth-First-Search）,DFS是由獲得計(jì)算機(jī)領(lǐng)域的最高獎(jiǎng)-圖靈獎(jiǎng)的霍普克洛夫特與陶爾揚(yáng)發(fā)明 DFS是搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。屬于盲目搜索。 DFS的時(shí)間復(fù)雜度不高（為線性時(shí)間復(fù)雜度），遍歷圖的效率往往非常高。因此，鑒于深度優(yōu)先搜索

2、算法的強(qiáng)大功能以及高效性往往被研究圖論問題的專家所推崇。 時(shí)間復(fù)雜度：O( )；空間復(fù)雜度：O(bm)；b - 分支系數(shù)m - 圖的最大深度,迷宮問題,首先我們來想象一只老鼠，在一座不見天日的迷宮內(nèi)，老鼠在入口處進(jìn)去，要從出口出來。那老鼠會(huì)怎么走？當(dāng)然可以是這樣的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意選擇其中的一條繼續(xù)往下走，如果遇到死胡同，就退回到最近的一個(gè)分叉路口，選擇另一條道路再走下去，如果遇到了出口，老鼠的旅途就算成功結(jié)束了。 深度優(yōu)先搜索的基本原則：按照某種條件往前試探搜索，如果前進(jìn)中遭到失?。ㄕ缋鲜笥龅剿篮﹦t退回頭另選通路繼續(xù)搜索，直到找到滿足條件的目標(biāo)為

3、止。,然而要實(shí)現(xiàn)這樣的算法，我們需要用到編程的一大利器-遞歸。 講一個(gè)更具體的例子：從前有座山，山里有座廟，廟里有個(gè)老和尚，老和尚在講故事，講什么呢？講：從前有座山，山里有座廟，廟里有個(gè)老和尚，老和尚在講故事，講什么呢？講：從前有座山，山里有座廟，廟里有個(gè)老和尚，老和尚在講故事，講什么呢？講：。好家伙，這樣講到世界末日還講不玩，老和尚講的故事實(shí)際上就是前面的故事情節(jié)，這樣不斷地調(diào)用程序本身，就形成了遞歸。萬一這個(gè)故事中的某一個(gè)老和尚看這個(gè)故事不順眼，就把他要講的故事?lián)Q成：“你有完沒完??！”，這樣，整個(gè)故事也就嘎然而止了。 我們編程就要注意這一點(diǎn)，在適當(dāng)?shù)臅r(shí)候，就必須要有一個(gè)這樣的和尚挺身而出，

4、把整個(gè)故事給停下來，或者說他不再往深一層次搜索，要不，我們的遞歸就會(huì)因計(jì)算機(jī)棧空間大小的限制而溢出，稱為stack overflow。,順序按數(shù)字編號(hào)順序先后訪問。那么我們?cè)趺磥肀ＷC這個(gè)順序呢？,基本思想：從初始狀態(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)，采用相同的回溯辦法回退到上

5、層節(jié)點(diǎn)，擴(kuò)展可能的分支生成新狀態(tài)，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。,Boolean visitedMAX; Status (*VisitFunc)(int v); /VisitFunc() 為頂點(diǎn)的訪問函數(shù)。 void DFSTraverse(graph G,Status(*Visit)(int v) VisitFunc = Visit ; for( v=0;vG.vexnum;+v) visitedv = FALSE; for ( v=0;vG.vexnum;+v) if( !visitedv) DFS(G,v); ,void DFS(Graph G, int v) visitedv

6、= TRUE ; VisitFunc(G.verticesv.data ); for(w=FirstAdjvex(G,v);w;w=NextAdjvex(G,v,w) if( !visitedw) DFS(G,w);,遞歸的經(jīng)典實(shí)例：階乘,int factorial(int n) if (n = 0) /基線條件(base case) return 1; else return n * factorial(n - 1); /將問題規(guī)模逐漸縮小 ,水仙花數(shù),一個(gè)三位數(shù)abc如果滿足abc = a3 + b3 + c3 那么就把這個(gè)數(shù)叫做水仙花數(shù)。 如果一個(gè)N位數(shù)所有數(shù)碼的N次方的和加起來等于這個(gè)

7、數(shù)字本身，我們把這樣的數(shù)叫做廣義水仙花數(shù)，容易看出來N = 3是廣義水仙花數(shù)。 現(xiàn)在，我們的任務(wù)是，輸入一個(gè)m (m 7) ，讓你求出所有滿足N = m的廣義水仙花數(shù)。 3 (153 370 371 407) 5 (54748 92727 93084),方法：數(shù)據(jù)規(guī)模很小，可以直接枚舉所有情況，然后判斷是否滿足條件。 難點(diǎn)：循環(huán)層數(shù)不確定 怎么實(shí)現(xiàn)這個(gè)m重循環(huán)？ 答案：遞歸。,m重循環(huán)的實(shí)現(xiàn)： void dfs(int deep) if (deep m) /check answer else if (deep = m) for (i = 1; i = n; i+) dfs(deep + 1);

8、 ,#include #include using namespace std; int m; int Pow(int x, int n) int res = 1; while (n-) res *= x; return res; ,void dfs(int deep, int curNum, int curSum) if (deep m) /類似于base case if (curNum = curSum) printf(%dn, curNum); else if (deep = m) int start = (deep = 1); /第一位不為0 for (int i = start; i

9、 = 9; i+) dfs(deep + 1, curNum * 10 + i, curSum + Pow(i, m); /縮小問題規(guī)模 ,int main() while (scanf(%d, ,深度優(yōu)先搜索解決問題的框架,void dfs(int deep, State curState) if (deep Max) /深度達(dá)到極限 if (curState = target) /找到目標(biāo) /. else for (i = 1; i = totalExpandMethod; i+) dfs(deep + 1, expandMethod(curState, i); ,大逃亡,Descript

10、ion love8909遇到危險(xiǎn)了！他被困在一個(gè)迷宮中，彷徨而無助?，F(xiàn)在需要你來幫助他走出困境。他只能記住指定長度的指令(指令的長度由MinLen和MaxLen限定)，并循環(huán)執(zhí)行，而且他只會(huì)向下或向右（很奇怪吧_）。他在地圖的左上角，你需要告訴他一個(gè)運(yùn)動(dòng)序列，即向下（D）或向右（R），使他能夠成功走出這個(gè)圖且不碰到陷阱。如果還不明白，可以參看圖片。圖片1，2對(duì)應(yīng)樣例的第1組，圖片3對(duì)應(yīng)樣例的第2組。,Input 第一行為1個(gè)整數(shù)T，表示有T組測(cè)試數(shù)據(jù)第二行為4個(gè)整數(shù)Height, Width, MinLen,MaxLen，分別表示地圖的高，寬，命令序列的最小和最大長度。3 = Height,

11、Width = 60, 2 = MinLen = MaxLen = 35第三行至第Height+2行為地圖信息。其中.表示空地，X表示陷阱。 Output 只有一行，為命令序列（只含D, R）。注意：如果有多解，輸入命令長度最短的；依然有多解，輸出字典序最小的（D的字典序比R?。?，數(shù)據(jù)保證一定存在一組解。字典序：字符串從前往后依次比較，第一個(gè)字符不同的位置，字符較小的字符串字典序較小，詳情參見字典。,Sample Input 23 3 2 2.X.X.5 5 2 3.X.X.X.XX.XX.X Sample Output DRDRR,方法：暴力 復(fù)雜度為O(2L)，L是序列長度 D和R的順序并

12、不需要固定 當(dāng)D和R的個(gè)數(shù)確定以后，我們枚舉序列中D和R的個(gè)數(shù)，搜尋一條可走的矩形路線。,#include #include #include #include int Height, Width, MinLen, MaxLen, sH, sW; char MAP6464; bool in(int x, int y) return x = 0 ,int main() int T; scanf(%d, ,char res128; bool dfs(int x, int y, int D, int R) if (check(x, y) = false) return false; if (D =

13、0 ,作業(yè)：與大逃亡很相似的題目 Tempter of the Bone ,Restore Equations,Description An interstellar expedition team has recently discovered on planet Mars some multiplication equations, which are believed to be the proof that Mars has once been the home of some intellectual species. However these equations are inco

14、mplete where some digits are missing because of the eroding power of Mars nature. Here is one example.,One way to restore this equation is to assume the 3 missing digits are 3, 5, 3, respectively, obtaining 123 x 45 = 5535, which indicates this equation may indeed be the intellectual output of Mars

15、ancient habitants, rather than just some random numbers. There has been hot debate over this, because people arent sure whether they can restore all the equations discovered on Mars, i.e. restore the missing digits such that the multiplication equation holds. As a programmer in NASA, you are assigne

16、d the task of checking if all the equations are restorable.,Input The first line is an integer T, number of equations to check. Next T lines each contains three non-empty strings A, B and C, separated by spaces. Each string contains digits(0-9) and/or asterisks * only, where an asterisk stands for a

17、 missing digit. No string begins with the digit 0. Output For each test case, output Yes(Quotes for clarity only) on a line if one can replace the asterisks with digits such that afterwards the numbers represented by A, B and C satisfy A x B = C. Otherwise output No instead. Note that an asterisk mu

18、st be replaced with exactly one digit(0-9) and the resulting numbers A, B and C cant start with zeros(See sample input/output for more clarification). The length of string A and B are at most 3, and the length of C is at most 6. The length of each string is greater than zero. At least one * will be

19、present in each equation.,Sample Input 212* 45 *5*511 11 *121 Sample Output YesNo,枚舉兩個(gè)乘數(shù)再檢查是否滿足等式。 遞歸搜索完成 這個(gè)題目和Google Code Jam China 2006 第二輪的500分類似。 The reverse() Algorithm A useful STL algorithm is reverse(). This algorithm reverses the order of elements in a specified sequence. reverse() takes two iterators that mark the