深度優(yōu)先搜索課件

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

m-圖的最大深度深度優(yōu)先搜索算法（Depth-First-Search）DF迷宮問題首先我們來想象一只老鼠，在一座不見天日的迷宮內(nèi)，老鼠在入口處進去，要從出口出來。那老鼠會怎么走？當然可以是這樣的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意選擇其中的一條繼續(xù)往下走，如果遇到死胡同，就退回到最近的一個分叉路口，選擇另一條道路再走下去，如果遇到了出口，老鼠的旅途就算成功結(jié)束了。深度優(yōu)先搜索的基本原則：按照某種條件往前試探搜索，如果前進中遭到失?。ㄕ缋鲜笥龅剿篮﹦t退回頭另選通路繼續(xù)搜索，直到找到滿足條件的目標為止。

迷宮問題首先我們來想象一只老鼠，在一座不見天日的迷宮內(nèi)，老然而要實現(xiàn)這樣的算法，我們需要用到編程的一大利器---遞歸。講一個更具體的例子：從前有座山，山里有座廟，廟里有個老和尚，老和尚在講故事，講什么呢？講：從前有座山，山里有座廟，廟里有個老和尚，老和尚在講故事，講什么呢？講：從前有座山，山里有座廟，廟里有個老和尚，老和尚在講故事，講什么呢？講：…………。好家伙，這樣講到世界末日還講不玩，老和尚講的故事實際上就是前面的故事情節(jié)，這樣不斷地調(diào)用程序本身，就形成了遞歸。萬一這個故事中的某一個老和尚看這個故事不順眼，就把他要講的故事?lián)Q成：“你有完沒完啊！”，這樣，整個故事也就嘎然而止了。我們編程就要注意這一點，在適當?shù)臅r候，就必須要有一個這樣的和尚挺身而出，把整個故事給停下來，或者說他不再往深一層次搜索，要不，我們的遞歸就會因計算機?？臻g大小的限制而溢出，稱為stackoverflow。然而要實現(xiàn)這樣的算法，我們需要用到編程的一大利器---遞歸。順序按數(shù)字編號順序先后訪問。那么我們怎么來保證這個順序呢？

基本思想：從初始狀態(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為止。順序按數(shù)字編號順序先后訪問。那么我們怎么來保證這個順序呢？ Booleanvisited[MAX];Status(*VisitFunc)(intv);//頂點的訪問函數(shù)voidDFSTraverse(graphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(G.vertices[v].data);for(w=FirstAdjvex(G,v);w;w=NextAdjvex(G,v,w))if(!visited[w])DFS(G,w);}Booleanvisited[MAX];馬的走法1、問題描述在一個4×5的棋盤上，馬的起始位置坐標(縱，橫)位置由鍵盤輸入，求馬能返回初始位置的所有不同走法的總數(shù)(馬走過的位置不能重復，馬走“日”字)。輸入輸出樣例：馬的走法1、問題描述在一個4×5的棋盤上，馬的起始位置坐2、問題分析由于4×5的棋盤的問題規(guī)模比較小，用回溯法可以較好的解決問題。如下圖所示，如果從(1,1)出發(fā)，那么馬首先從(1,1)點走向(3,2)點，再到(2,4)點，這樣過程可以一步一步遞推下去，最后要么找到一條路徑，要么進入“死胡同”，這時函數(shù)find(p1,p2)就不能遞歸調(diào)用自己了，因此實現(xiàn)了回溯。為了避免走重復的位置，可以定義一個數(shù)組chess[5][4]表示棋盤，若chess[i][j]=1，則表示馬已經(jīng)走過，在遞推時就不能走此位置，應該換一個方向。對于馬走的方向，可以定義數(shù)組d[2][8]，每列表示一個馬可以走的方向。2、問題分析由于4×5的棋盤的問題規(guī)模比較小，用回3、參考代碼#include<stdio.h>intchess[5][4];intd[2][8]={{-1,-1,-2,-2,2,2,1,1},{2,-2,1,-1,1,-1,2,-2}};intsx,sy,tot;voidfind(intp1,intp2){inti,pi,pj;for(i=0;i<8;i++)

{pi=p1+d[0][i];pj=p2+d[1][i];if((pi==sx)&&(pj==sy))//一定要放在前面tot++;elseif((pi>=0)&&(pi<5)&&(pj>=0)&&(pj<4)&&(chess[pi][pj]==0)){chess[pi][pj]=1;find(pi,pj);

chess[pi][pj]=0;}}}3、參考代碼#include<stdio.h>intmain(void){inti,j;while(scanf("%d%d",&sy,&sx)==2){for(i=0;i<5;i++)for(j=0;j<4;j++)chess[i][j]=0;tot=0;sx--;sy--;find(sx,sy);printf("%d\n",tot);}return0;}3、參考代碼intmain(void)3、參考代碼水仙花數(shù)一個三位數(shù)abc如果滿足abc=a^3+b^3+c^3那么就把這個數(shù)叫做水仙花數(shù)。如果一個N位數(shù)所有數(shù)碼的N次方的和加起來等于這個數(shù)字本身，我們把這樣的數(shù)叫做廣義水仙花數(shù)，容易看出來N=3是廣義水仙花數(shù)?，F(xiàn)在，我們的任務是，輸入一個m(m<7)，讓你求出所有滿足N=m的廣義水仙花數(shù)。3(153370371407)5(547489272793084)水仙花數(shù)一個三位數(shù)abc如果滿足abc=a^3+b方法：數(shù)據(jù)規(guī)模很小，可以直接枚舉所有情況，然后判斷是否滿足條件。難點：循環(huán)層數(shù)不確定怎么實現(xiàn)這個m重循環(huán)？答案：遞歸。方法：數(shù)據(jù)規(guī)模很小，可以直接枚舉所有情況，然后判斷是否滿足條m重循環(huán)的實現(xiàn)：voiddfs(intdeep){ if(deep>m) { //checkanswer } elseif(deep<=m) { for(i=1;i<=n;i++) dfs(deep+1); }}m重循環(huán)的實現(xiàn)：#include<iostream>#include<cstdio>usingnamespacestd;intm;intPow(intx,intn){ intres=1; while(n--)res*=x; returnres;}#include<iostream>voiddfs(intdeep,intcurNum,intcurSum){if(deep>m)//類似于basecase{if(curNum==curSum)printf("%d\n",curNum);}elseif(deep<=m){intstart=(deep==1);//第一位不為0for(inti=start;i<=9;i++)dfs(deep+1,curNum*10+i,curSum+Pow(i,m));//縮小問題規(guī)模}}voiddfs(intdeep,intcurNum,intmain(){ while(scanf("%d",&m)==1) { dfs(1,0,0); } return0;}intmain()深度優(yōu)先搜索解決問題的框架voiddfs(intdeep,StatecurState){if(deep>Max)//深度達到極限{ if(curState==target)//找到目標{//...}}else{for(i=1;i<=totalExpandMethod;i++){dfs(deep+1,expandMethod(curState,i));}}}深度優(yōu)先搜索解決問題的框架voiddfs(intdeep大逃亡

/problem.php?pid=1022Description

love8909遇到危險了！??！他被困在一個迷宮中，彷徨而無助?，F(xiàn)在需要你來幫助他走出困境。他只能記住指定長度的指令(指令的長度由MinLen和MaxLen限定)，并循環(huán)執(zhí)行，而且他只會向下或向右（很奇怪吧^_^）。他在地圖的左上角，你需要告訴他一個運動序列，即向下（D）或向右（R），使他能夠成功走出這個圖且不碰到陷阱。

如果還不明白，可以參看圖片。圖片1,2對應樣例的第1組，圖片3對應樣例的第2組。

大逃亡

/prInput

第一行為1個整數(shù)T，表示有T組測試數(shù)據(jù)

第二行為4個整數(shù)Height,Width,MinLen,MaxLen，分別表示地圖的高，寬，命令序列的最小和最大長度。3<=Height,Width<=60,2<=MinLen<=MaxLen<=35

第三行至第Height+2行為地圖信息。其中'.'表示空地，'X'表示陷阱。

Output

只有一行，為命令序列（只含D,R）。

注意：如果有多解，輸入命令長度最短的；依然有多解，輸出字典序最小的（D的字典序比R小），數(shù)據(jù)保證一定存在一組解。

字典序：字符串從前往后依次比較，第一個字符不同的位置，字符較小的字符串字典序較小，詳情參見字典。

Input

SampleInput2

3322

.X.

...

X..

5523

..X.X

....X

.....

.XX..

XX..X

SampleOutputDR

DRR

SampleInput方法：暴力復雜度為O(2^L)，L是序列長度仔細思考之后會發(fā)現(xiàn)，人的活動范圍與D和R的順序無關(guān)。即當D和R的個數(shù)確定以后，他的活動范圍一定在若干個首尾相接（左上角和右下角相連）的矩形內(nèi)。這樣，我們枚舉序列中D和R的個數(shù)，然后將各個將要經(jīng)過的矩形并起來，組成一個新的矩形，若這個矩形從左上角至右下角可達，則有解。方法：暴力#include<iostream>#include<cstdio>intHeight,Width,MinLen,MaxLen,sH,sW;charMAP[64][64];boolin(intx,inty){returnx>=0&&x<Height&&y>=0&&y<Width;}boolcheck(intx,inty){while(in(x,y)){if(MAP[x][y]=='X')returnfalse;x+=sH;y+=sW;//與while配合確保重復執(zhí)行不會遇障礙}returntrue;}參考程序#include<iostream>參考程序charres[128];booldfs(intx,inty,intD,intR){ if(check(x,y)==false) returnfalse; if(D==0&&R==0) { res[x+y]='\0'; printf("%s\n",res); returntrue; } if(D>0)//由于字典序，先考慮向下再考慮向右 { res[x+y]='D'; if(dfs(x+1,y,D-1,R)) returntrue; } if(R>0) { res[x+y]='R'; if(dfs(x,y+1,D,R-1)) returntrue; } returnfalse;}charres[128];intmain(){intT;scanf("%d",&T);while(T--){scanf("%d%d%d%d",&Height,&Width,&MinLen,&MaxLen);for(inti=0;i<Height;i++)scanf("%s",MAP[i]);boolfind=false;for(intL=MinLen;!find&&L<=MaxLen;L++)for(sH=L;!find&&sH>=0;sH--)find=dfs(0,0,sH,sW=L-sH);}return0;}intmain()作業(yè)：與大逃亡很相似的題目TempteroftheBone/showproblem.php?pid=1010作業(yè)：與大逃亡很相似的題目RestoreEquations

/problem.php?pid=1145Description

AninterstellarexpeditionteamhasrecentlydiscoveredonplanetMarssomemultiplicationequations,whicharebelievedtobetheproofthatMarshasoncebeenthehomeofsomeintellectualspecies.HowevertheseequationsareincompletewheresomedigitsaremissingbecauseoftheerodingpowerofMars'nature.Hereisoneexample.

Description

AninterstellarexpeditionteamhasrecentlydiscoveredonplanetMarssomemultiplicationequations,whicharebelievedtobetheproofthatMarshasoncebeenthehomeofsomeintellectualspecies.HowevertheseequationsareincompletewheresomedigitsaremissingbecauseoftheerodingpowerofMars'nature.Hereisoneexample.

RestoreEquations

http://acm.uOnewaytorestorethisequationistoassumethe3missingdigitsare3,5,3,respectively,obtaining123x45=5535,whichindicatesthisequationmayindeedbetheintellectualoutputofMars'ancienthabitants,ratherthanjustsomerandomnumbers.

Therehasbeenhotdebateoverthis,becausepeoplearen'tsurewhethertheycanrestorealltheequationsdiscoveredonMars,i.e.restorethemissingdigitssuchthatthemultiplicationequationholds.AsaprogrammerinNASA,youareassignedthetaskofcheckingifalltheequationsarerestorable.OnewaytorestorethiseqInput

ThefirstlineisanintegerT,numberofequationstocheck.NextTlineseachcontainsthreenon-emptystringsA,BandC,separatedbyspaces.Eachstringcontainsdigits('0'-'9')and/orasterisks'*'only,whereanasteriskstandsforamissingdigit.Nostringbeginswiththedigit'0'.

Output

Foreachtestcase,output"Yes"(Quotesforclarityonly)onalineifonecanreplacetheasteriskswithdigitssuchthatafterwardsthenumbersrepresentedbyA,BandCsatisfyAxB=C.Otherwiseoutput"No"instead.Notethatanasteriskmustbereplacedwithexactlyonedigit('0'-'9')andtheresultingnumbersA,BandCcan'tstartwithzeros(Seesampleinput/outputformoreclarification).ThelengthofstringAandBareatmost3,andthelengthofCisatmost6.Thelengthofeachstringisgreaterthanzero.Atleastone'*'willbepresentineachequation.

Input

SampleInput212*45*5*51111*121SampleOutputYesNo

SampleInput枚舉兩個乘數(shù)再檢查是否滿足等式。遞歸搜索完成這個題目和GoogleCodeJamChina2006第二輪的500分類似。枚舉兩個乘數(shù)再檢查是否滿足等式。#include

<iostream>

#include

<string>

#include

<algorithm>//算法頭文件調(diào)用

reverse算法

string

A,B,C;

int

lena,lenb,lenc;

int

a[3],b[3];

bool

flag=false;

int

main()

{

int

ncase;scanf("%d",&ncase);

while(ncase--){

scanf("%s

%s

%s",A,B,C);

lena=A.length();

lenb=B.length();

lenc=C.length();

reverse(A.begin(),A.end());

reverse(B.begin(),B.end());

reverse(C.begin(),C.end());

for(int

i=0;i<3;++i)a[i]=0,b[i]=0;

flag=false;

dfs(0);

if(flag)printf("Yes\n");

else

printf("No\n");

}

return

0;}

#include

<iostream>

void

check(){

int

x=a[0]+a[1]*10+a[2]*100;

int

y=b[0]+b[1]*10+b[2]*100;

int

z=x*y;

for(int

i=0;i<lenc-1;++i){

if(C[i]=='*'){

z/=10;continue;

}

if(z%10+'0'!=C[i])return;

z/=10;

}

if((z==0&&C[lenc-1]!='0')||z>=10)return;

if(z==C[lenc-1]-'0'