深度優(yōu)先搜索

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

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

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

4、，或者說(shuō)他不再往深一層次搜索，要不，我們的遞歸就會(huì)因計(jì)算機(jī)?？臻g大小的限制而溢出，稱(chēng)為stack overflow。 順序按數(shù)字編號(hào)順序先后訪問(wèn)。那么我們?cè)趺磥?lái)保證這個(gè)順序呢？基本思想：從初始狀態(tài)S開(kāi)始，利用規(guī)則生成搜索樹(shù)下一層任一個(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ù)以上操作過(guò)程，一直進(jìn)行到葉節(jié)點(diǎn)（即不能再生成新?tīng)顟B(tài)節(jié)點(diǎn)），當(dāng)它仍不是目標(biāo)狀態(tài)G時(shí)，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜索的分支。生成新?tīng)顟B(tài)節(jié)點(diǎn)。若仍不是目標(biāo)狀態(tài)，就按該分支一直擴(kuò)展到葉節(jié)點(diǎn)，若仍不是目標(biāo)，采用相同的回溯辦法回退到上層節(jié)點(diǎn)，擴(kuò)展可能的分

5、支生成新?tīng)顟B(tài)，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)G為止。Boolean visitedMAX;Status (*VisitFunc)(int v);/VisitFunc() 為頂點(diǎn)的訪問(wè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 = 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)典實(shí)例：階乘int factorial(int n) if (n = 0) /基線條件(base case) return 1; else return n * factorial(n - 1); /將問(wèn)題規(guī)模逐漸縮小 水仙花數(shù) 一個(gè)三位數(shù)abc如果滿(mǎn)足abc = a3 + b3 + c3 那么就把這個(gè)數(shù)叫做水仙花數(shù)。如果一個(gè)N位數(shù)所有數(shù)碼的N次方的和加起來(lái)等于這個(gè)數(shù)字本身，我們把這樣的數(shù)叫做廣義水仙

7、花數(shù)，容易看出來(lái)N = 3是廣義水仙花數(shù)?，F(xiàn)在，我們的任務(wù)是，輸入一個(gè)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) /類(lèi)似于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遇到危險(xiǎn)了！他被困在一個(gè)迷宮中，彷徨而無(wú)助?，F(xiàn)在需要你來(lái)幫助他走出困境。他只能記住指定長(zhǎng)度的指令(指令的長(zhǎng)度由M

9、inLen和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，分別表示地圖的高，寬，命令序列的最小和最大長(zhǎng)度。3 = Height, Width = 60, 2 = MinLen = MaxLen = 35第三行至第Height+2行為地圖信息。其中.表示空地，X表示陷阱

10、。 Output 只有一行，為命令序列（只含D, R）。注意：如果有多解，輸入命令長(zhǎng)度最短的；依然有多解，輸出字典序最小的（D的字典序比R?。?，數(shù)據(jù)保證一定存在一組解。字典序：字符串從前往后依次比較，第一個(gè)字符不同的位置，字符較小的字符串字典序較小，詳情參見(jiàn)字典。 Sample Input 23 3 2 2.X.X.5 5 2 3.X.X.X.XX.XX.XSample Output DRDRR 方法：暴力復(fù)雜度為O(2L)，L是序列長(zhǎng)度 D和R的順序并不需要固定當(dāng)D和R的個(gè)數(shù)確定以后，我們枚舉序列中D和R的個(gè)數(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 枚舉兩個(gè)乘數(shù)再檢查是否滿(mǎn)足等式。遞歸搜索完成這個(gè)題目和Google Code Jam China 2006 第二輪的500分類(lèi)似。 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(