深度優(yōu)先搜索

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

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

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

4、，或者說他不再往深一層次搜索，要不，我們的遞歸就會因計算機?？臻g大小的限制而溢出，稱為stack overflow。 順序按數(shù)字編號順序先后訪問。那么我們怎么來保證這個順序呢？基本思想：從初始狀態(tài)S開始，利用規(guī)則生成搜索樹下一層任一個結(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個結(jié)點，再檢查是否為目標(biāo)節(jié)點G，若未出現(xiàn)，繼續(xù)以上操作過程，一直進(jìn)行到葉節(jié)點（即不能再生成新狀態(tài)節(jié)點），當(dāng)它仍不是目標(biāo)狀態(tài)G時，回溯到上一層結(jié)果，取另一可能擴展搜索的分支。生成新狀態(tài)節(jié)點。若仍不是目標(biāo)狀態(tài)，就按該分支一直擴展到葉節(jié)點，若仍不是目標(biāo)，采用相同的回溯辦法回退到上層節(jié)點，擴展可能的分

5、支生成新狀態(tài)，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。Boolean visitedMAX;Status (*VisitFunc)(int v);/VisitFunc() 為頂點的訪問函數(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 = TRUE ; Visit

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

7、花數(shù)，容易看出來N = 3是廣義水仙花數(shù)。現(xiàn)在，我們的任務(wù)是，輸入一個m (m m)/check answerelse if (deep = m)for (i = 1; i = n; i+)dfs(deep + 1);#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 caseif (curNum = cur

8、Sum)printf(%dn, curNum);else if (deep = m)int start = (deep = 1); /第一位不為0for (int i = start; i Max) /深度達(dá)到極限 if (curState = target) /找到目標(biāo)/.elsefor (i = 1; i = totalExpandMethod; i+)dfs(deep + 1, expandMethod(curState, i);大逃亡 Description love8909遇到危險了！他被困在一個迷宮中，彷徨而無助?，F(xiàn)在需要你來幫助他走出困境。他只能記住指定長度的指令(指令的長度由M

9、inLen和MaxLen限定)，并循環(huán)執(zhí)行，而且他只會向下或向右（很奇怪吧_）。他在地圖的左上角，你需要告訴他一個運動序列，即向下（D）或向右（R），使他能夠成功走出這個圖且不碰到陷阱。如果還不明白，可以參看圖片。圖片1，2對應(yīng)樣例的第1組，圖片3對應(yīng)樣例的第2組。Input 第一行為1個整數(shù)T，表示有T組測試數(shù)據(jù)第二行為4個整數(shù)Height, Width, MinLen,MaxLen，分別表示地圖的高，寬，命令序列的最小和最大長度。3 = Height, Width = 60, 2 = MinLen = MaxLen = 35第三行至第Height+2行為地圖信息。其中.表示空地，X表示陷阱

10、。 Output 只有一行，為命令序列（只含D, R）。注意：如果有多解，輸入命令長度最短的；依然有多解，輸出字典序最小的（D的字典序比R小），數(shù)據(jù)保證一定存在一組解。字典序：字符串從前往后依次比較，第一個字符不同的位置，字符較小的字符串字典序較小，詳情參見字典。 Sample Input 23 3 2 2.X.X.5 5 2 3.X.X.X.XX.XX.XSample Output DRDRR 方法：暴力復(fù)雜度為O(2L)，L是序列長度 D和R的順序并不需要固定當(dāng)D和R的個數(shù)確定以后，我們枚舉序列中D和R的個數(shù)，搜尋一條可走的矩形路線。 #include #include #include

11、#include int Height, Width, MinLen, MaxLen, sH, sW;char MAP6464;bool in(int x, int y)return x = 0 & x = 0 & y Width;bool check(int x, int y)while (in(x, y)if (MAPxy = X)return false;x += sH; y += sW;return true;int main()int T;scanf(%d, &T);while (T-)scanf(%d %d %d %d, &Height, &Width, &MinLen, &Max

12、Len);for (int i = 0; i Height; i+)scanf(%s, MAPi);bool find = false;for (int L = MinLen; !find & L = 0; sH-)find = dfs(0, 0, sH, sW = L - sH);return 0;char res128;bool dfs(int x, int y, int D, int R)if (check(x, y) = false)return false;if (D = 0 & R = 0)resx + y = 0;printf(%sn, res);return true;if (

13、D 0)resx + y = D;if (dfs(x + 1, y, D - 1, R)return true;if (R 0)resx + y = R;if (dfs(x, y + 1, D, R - 1)return true;return false;作業(yè)：與大逃亡很相似的題目Tempter of the Bone Restore EquationsDescription An interstellar expedition team has recently discovered on planet Mars some multiplication equations, which a

14、re believed to be the proof that Mars has once been the home of some intellectual species. However these equations are incomplete 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,

15、5, 3, respectively, obtaining 123 x 45 = 5535, which indicates this equation may indeed be the intellectual output of Mars 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

16、Mars, i.e. restore the missing digits such that the multiplication equation holds. As a programmer in NASA, you are assigned 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 string

17、s A, B and C, separated by spaces. Each string contains digits(0-9) and/or asterisks * only, where an asterisk stands for a 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 tha

18、t afterwards the numbers represented by A, B and C satisfy A x B = C. Otherwise output No instead. Note that an asterisk must 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

19、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 present in each equation. Sample Input 212* 45 *5*511 11 *121 Sample Output YesNo 枚舉兩個乘數(shù)再檢查是否滿足等式。遞歸搜索完成這個題目和Google Code Jam China 2006 第二輪的500分類似。 The reverse() AlgorithmA useful

20、 STL algorithm is reverse(). This algorithm reverses the order of elements in a specified sequence. reverse() takes two iterators that mark the sequences beginning and end, respectively. Here is an example of reversing the order of a char array: #include #include #include/算法頭文件調(diào)用reverse算法 stringA,B,C; intlena,lenb,lenc; inta3,b3; boolflag=false; intmain() intncase;scanf(