第八講深度優(yōu)先搜索算法22014.04.12回顧深度優(yōu)先搜索算法1.跳馬問題2.數(shù)字三角形3.簡單的0-1背包問題搜索算法：為了得到問題的解，列舉出解的所有或部分可能的情況，根據(jù)要求進行逐一判斷，從而求出問題解的一種算法。常見的類型：（1）尋找一個滿足條件的解；（2）統(tǒng)計滿足條件的解的個數(shù)；（3）尋找滿足條件的最優(yōu)解。（最常見類型）深度優(yōu)先搜索（DFS：DepthFirstsearch）思想：

從當前初始狀態(tài)開始，按深度方向搜索，能往下走就走，不能走就返回到上一層，繼續(xù)找沒有被訪問的結(jié)點，直至所有結(jié)點都被訪問為止。關(guān)鍵：1.定義合適的狀態(tài)描述（有用的狀態(tài)）2.初始狀態(tài)(起點)、目標狀態(tài)3.明確從某一狀態(tài)出發(fā)向下一個狀態(tài)擴展的規(guī)則和方法

設(shè)有下圖所示的一個棋盤，在棋盤上的A(0,0)點有一個中國象棋馬，并約定馬走的規(guī)則：

(1)、馬只向右走；

(2)、馬走“日“字。找出一條從A到B的路徑。輸入：B的坐標n，m（<=30）。輸出：一條路徑(坐標)。如：輸入：84輸出：(0,0)(2,1)(4,0)(5,2)(6,0)(7,2)(8,4)1.跳馬問題分析：1.狀態(tài)描述：坐標位置(x,y)2.初始狀態(tài)=（0,0）；目標狀態(tài)=（n,m）3.狀態(tài)擴展規(guī)則：當前狀態(tài)(x[i],y[i])，下一個可能的狀態(tài)(x[i]+dx[k],y[i]+dy[k])k=1,2,3,4proceduredfs(i:longint);vark:longint;beginif(x[i]=n)and(y[i]=m)thenprint(i);fork:=1to4doif(x[i]+dx[k]<=n)and(y[i]+dy[k]>=0)and(y[i]+dy[k]<=m)thenbeginx[i+1]:=x[i]+dx[k];y[i+1]:=y[i]+dy[k];dfs(i+1);end;end;Horse1.pas定義常量數(shù)組并賦值（定義變量之前定義常量）constdx:array[1..4]oflongint=(1,2,2,1);dy:array[1..4]oflongint=(-2,-1,1,2);beginreadln(n,m);x[1]:=0;y[1]:=0;cnt:=0;dfs(1);end.主程序：一條路線找到halt最短路線（在所有路線中比較；在最優(yōu)的可能中比較）提供源程序同學體驗一下：horse21.pasHorse22.pas哪個方便？2.數(shù)字三角形【IOI1994】有一個數(shù)字三角形，編程求從最頂層到最底層的一條路所經(jīng)過位置上數(shù)字之和的最大值。每一步只能向左下或右下方向走。下圖數(shù)據(jù)的路應(yīng)為7->3->8->7->5，和為30。輸入：第一行：n(1<=n<=100),數(shù)字三角形共有n行；以下R行：依次表示數(shù)字三角形中每行中的數(shù)字。每個數(shù)都是非負的，且<=100.輸出：一個正整數(shù)，路徑上數(shù)字之和的最大值。

7388102744452651112輸入樣例：5738810274445265輸出樣例：30路徑數(shù)字最大和：7+3+8+7+5=3013i,ji+1,ji+1,j+114分析：1.定義狀態(tài):從（1,1）走到（i,j）的經(jīng)過的數(shù)字的和。(i,j,sum)2.初始狀態(tài)=（1,1,a[1,1]）；目標狀態(tài)=（n,j,sum）3.狀態(tài)擴展規(guī)則：當前狀態(tài)(i,j,sum)，下一個狀態(tài):(i+1,j,sum+a[i+1,j]);(i+1,j+1,sum+a[i+1,j+1])i,ji+1,ji+1,j+1深度優(yōu)先搜索算法：Proceduredfs(i,j,sum)//從(1,1)走到（i，j）位置所求和sumBeginifi=nthen//走到最后一行ifsum>ansthenans=sum;ifi=nthenexit;//必須的dfs(向左下方走)；dfs(向右下方走)；End;16//二維數(shù)組a[i,j]存儲數(shù)字三角形。proceduredfs(i,j,sum:integer);beginifi=nthenifsum>ansthenans:=sum;ifi=nthenexit;//必須的dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;初始：dfs(1,1,a[1,1]);結(jié)果：ans17i,ji+1,ji+1,j+1有一個背包，最大載重量為m。有n種貨物：重量為W[i](<1000)；

價值為V[i](<1000).今從ｎ種物品中選取若干件放入背包，使其重量的和不超過m，而所選貨物的價值的和為最大。n<=20,M<1000.

求最大價值。3.簡單的0-1背包19輸入樣例1：

410

4357

1572025

輸出樣例1：

35輸入樣例2：

420

291015

291016

輸出樣例2：

19分析：1.定義狀態(tài):從1到第i件物品中選擇若干后背包的剩余重量及獲得的價值。(i,left,sum)2.初始狀態(tài)=（0,m,0）；目標狀態(tài)=（n,x,sum）3.狀態(tài)擴展規(guī)則：當前狀態(tài)(i,left,sum)，下一個狀態(tài):

不選第i+1件物品：(i+1,left,sum)

選第i+1件物品(left>=w[i+1])：

(i+1,left-w[i+1],sum+v[i+1])proceduredfs(i,left,sum:longint);//在前i件物品中選了若干件放入到背包中，其價值為value，背包還能裝的重量為left。beginifi=nthenifsum>ansthenans:=sum;

ifi=nthenexit;//防止越界

dfs(i+1,left,sum);//不裝i+1ifleft>=w[i+1]then//裝i+1

dfs(i+1,left-w[i+1],sum+v[i+1]);end;深度優(yōu)先搜索算法:n<=20時間:O(2n)dfs(0,m,0);還可以這樣定義：1.定義狀態(tài):從1到第i件物品中所選物品的重量及的價值。(i,all,sum)2.初始狀態(tài)=（0,0,0）；目標狀態(tài)=（n,x,sum）3.狀態(tài)擴展規(guī)則：當前狀態(tài)(i,all,sum)，下一個狀態(tài):

不選第i+1件物品：(i+1,all,sum)

選第i+1件物品(all+w[i+1]<=m)：

(i+1,all+w[i+1],sum+v[i+1])Dfs最簡單的框架：Proceduredfs(i:當前狀態(tài)x[i]）beginif當前狀態(tài)i是目標then處理；if越界退出；

按k個規(guī)則擴展新狀態(tài)xx；if狀態(tài)xx符合要求thenbegin

記下狀態(tài)x[i+1]=xxdfs(i+1:狀態(tài)x[i+1]);//新狀態(tài)作為新起點繼續(xù)搜索end;end;新知識跳馬擴展n=2m=2(2,2)(0,0)n=2m=2(2,2)(0,0)問題擴展：可以往回跳（8個方向）n=2m=2(2,2)(0,0)問題擴展：可以往回跳（8個方向）horse22.pas怎么修改？horse22.pas怎么修改？1.方向由4個變?yōu)?個。2.最大步數(shù)30*30。2.邊界的判斷。3.怎么樣避免重復（已走過的位置）？a:array[0..30,0..30]oflongint;用a[xx,yy]標記（xy，yy）是否走過？0：沒走過1：走過了（當前路線）能走的地方a[xy,yy]=0才能走走過后做標記a[xy,yy]=1不能走了返回或者找到一條路線要去掉標記a[xy,yy]=0fork:=1to8dobeginxx:=x[i]+dx[k];yy:=y[i]+dy[k];//記錄新狀態(tài)if(xx>=0)and(xx<=n)and(yy>=0)and(yy<=m)and(a[xx,yy]=0)thenbeginx[i+1]:=xx;y[i+1]:=yy;

a[xx,yy]:=1;//加標記dfs(i+1);

a[xx,yy]:=0;//去掉標記，不去掉會怎樣？end;end;

設(shè)有一個N*M(N,M<=10)方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中分別放有0和1，0表示可通，1表示不能.迷宮走的規(guī)則如下圖所示：即從某點開始，有八個方向可走，前進方格中數(shù)字為0時表示可通過，為1時表示不可通過。輸入例子：（從文件中讀取數(shù)據(jù),有空格）880001101010110110010010010011010101000110011111010011101111000000入口：（1，1）出口：（1，8）//行列為標準輸出要求：找出一條從入口（左上角）到出口（又上角）的路徑。同一條路線不能有重復的點。

4.迷宮問題000110101011011001001001001101010100011001111101001110111100000012345678123456781):(1,1)(2,2)(3,3)(3,4)(4,5)(3,6)(3,7)(2,8)(1,8)2):(11)(12)(22)(33)(34)(25)(36)(37)(28)(18)3):(11)(12)(13)(22)(33)(34)(25)(36)(37)(28)(18)(行，列)入口出口1:黑色格子，不能走；0：白色格子，能走迷宮問題與跳馬擴展的區(qū)別：1.跳馬是坐標；迷宮是行x[i]與列y[i]。2.迷宮8個方向的位移不一樣了。3.出口判斷:。4.迷宮如果a[x,y]=1，不能走。不出界并且沒有墻才能走。5.讀入數(shù)據(jù)格式不一樣。(x,y)constmaxn=100;dx:array[1..8]ofinteger=(-1,-1,0,1,1,1,0,-1);dy:array[1..8]ofinteger=(0,1,1,1,0,-1,-1,-1);文件輸入輸出建立文件關(guān)聯(lián)：assign為讀操作準備：reset為寫操作準備：rewrite關(guān)閉文件：closeassign(input,’輸入文件’);Reset(input);…….Close(input);assign(output,’輸出文件’);Rewrite(output);…..Close(output);不去掉標記發(fā)生什么情況？一條路線halt最短路線0001101010110110010010010011010101000110011111010011101111000000關(guān)于邊界問題的改進：方法：迷宮的四周加上1定義：a:array[0..11,0..11]oflongint;readln(n,m);fori:=0ton+1doforj:=0tom+1doa[i,j]:=1;//開始全是1fori:=1tondoforj:=1tondoread(a[i,j]);(xx>=1)and(xx<=n)and(yy>=1)and(yy<=n)and(a[xx,yy]=0)a[xx,yy]=0Dfs最基本的框架：Proceduredfs(i:當前狀態(tài)x[i]）beginif當前狀態(tài)i是目標then處理；if越界退出；

按k個規(guī)則擴展新狀態(tài)xx；if狀態(tài)xx符合要求thenbegin

記下狀態(tài)x[i+1]=xx；[標記新狀態(tài)，避免重復走；]dfs(i+1:狀態(tài)x[i+1]);//新狀態(tài)作為新起點繼續(xù)搜索[去掉標記，供后面繼續(xù)走；]end;end;5.借書問題

學校放暑假時，信息學輔導教師有n本書要分給參加培訓的n個學生。如：A，B，C，D，E共5本書要分給參加培訓的張、劉、王、李、孫5位學生，每人只能選1本。教師事先讓每個人將自己喜愛的書填寫在如下的表中，然后根據(jù)他們填寫的表來分配書本，希望設(shè)計一個程序幫助教師求出可能的分配方案，使每個學生都滿意。ABCDE張11000王10000劉00111孫00100李00011輸入：第一行一個數(shù)n（學生的個數(shù)，書的數(shù)量）以下共n行，每行n個0或1（由空格隔開），第i行數(shù)據(jù)表示第i個同學對所有書的喜愛情況。0表示不喜歡該書，1表示喜歡該書。輸出：所有的分配方案，每種方案一行：依次輸出每個學生分到的書號。樣例輸入：51100010000001110010000011樣例輸出：2143521534分析：Constmaxn=10;varlike:array[1..maxn,1..maxn]oflongint;//1:第i個人喜歡第j本書；0：不喜歡；a:array[1..maxn]oflongint;//第i個人借書編號；can:array[1..maxn]oflongint;//0:可以第i本借；1：不能再借，已被借走算法設(shè)計:proceduredfs(i:longint);{第i個人可以借的書a[i]}varj:longinte;beginifi=nthen輸出結(jié)果，數(shù)組a[1..n];

ifi=nthenexit;

forj:=1tondoif第i+1個人可以借第j本書thenbegin

記錄下a[i+1];

標記第j本數(shù)已被借;dfs(i+1);

刪除書的被借標志;end;end;proceduredfs(i:longint);varj:longint;beginifi=nthenprint;ifi=nthenexit;forj:=1tondoif(like[i+1,j]=1)and(can[j]=0)thenbegina[i+1]:=j;can[j]:=1;dfs(i+1);

can[j]:=0;//不去標記結(jié)果？end;end;【問題描述】輸入自熱數(shù)n，輸出前n個自然數(shù)的所有全排列。n<=10.【輸入】自然數(shù)n?！据敵觥克械娜帕?，每行一種排列?！据斎胼敵鰳永縫ailie.inpailie.out31:1232:1323:2134:2315:3126:3216.自然數(shù)的全排列分析：a:array[1..maxn]oflongint;//記錄生成的排列can:array[1..maxn]ofboolean;//標記是否可用n:longint;//前n個自熱數(shù)的全排列ans:longint;//記錄生成的排列數(shù)量assign(input,'pailie.in');reset(input);assign(output,'pailie.out');rewrite(output);readln(n);ans:=0;fillchar(can,sizeof(can),true);dfs(0);close(input);close(output);proceduredfs(i:longint);varj:longint;beginifi=nthenprint;ifi=nthenexit;forj:=1tondoifcan[j]=truethenbegina[i+1]:=j;can[j]:=false;dfs(i+1);can[j]:=true;end;end;7、自然數(shù)n的分解輸入自然數(shù)n（n<100），輸出所有和的形式。不能重復。如：4=1+1+2；4=1+2+1;4=2+1+1屬于一種分解形式。樣例：輸入：7輸出：1:7=1+62:7=1+1+53:7=1+1+1+44:7=1+1+1+1+35:7=1+1+1+1+1+26:7=1+1+1+1+1+1+17:7=1+1+1+2+28:7=1+1+2+39:7=1+2+410:7=1+2+2+211:7=1+3+312:7=2+513:7=2+2+314:7=3+4分析：為了保證不重復，約定分解的項是非遞減的。n=a[1]+a[2]+…+a[i]a[1]<=a[2]<=…<=a[i]算法思想：假設(shè)當前的一種分解方案：

n=a[1]+a[2]+…+a[i]

滿足：a[1]<=a[2]<=…<=a[i]如：15=1+1+2+11下一步？方法很多，選擇一種好理解易于實現(xiàn)的一種：15=1+1+2+11把最后一項11按要求繼續(xù)分解為兩項的和的形式15=1+1+2+2+915=1+1+2+3+815=1+1+2+4+715=1+1+2+5+6一般情況：假設(shè)當前的一種分解方案：

n=a[1]+a[2]+…+a[i-1]+a[i]滿足：a[1]<=a[2]<=…<=a[i-1]<=a[i]繼續(xù)：n=a[1]+a[2]+…+a[i-1]+a[i]+a[i+1]a[i]a[i]+a[i+1]x=a[i]滿足：a[i-1]<=a[i]<=a[i+1](=x-a[i])a[i]的范圍:a[i-1]..xdiv2beginreadln(n);s:=0;a[0]:=1;a[1]:=n;dfs(1);ceduredfs(i:longint);varj,x:longint;begin