1、日I!所謂"深度展的策略，這種策略是優先擴展深度大的結點， 索也叫做 DfS 法(Depth First Search)深度優先搜索對產生問題的狀態結點而言的，”深度優先”是一種控制結點擴 把狀態向縱深發展。 深度優先搜 。深度優先搜索的遞歸實現過程：procedure dfs(i);for j:=1 to r doif 子結點mr符合條件then產生的子結點 mr入棧;if 子結點 mr是目標結點then 輸出else dfs(i+1);棧頂元素出棧(即刪去mr);en dif;en dfor;例1騎士游歷:設有一個n*m的棋盤，在棋盤上任一點有一個中國象棋馬IU當N,M輸入之后,

2、找出一條從左下角到右上角的路徑。例如：輸入N=4,M=4，輸出:路徑的格式:(1,1)->(2,3)->(4,4)，若不存在路徑,則輸出"no"算法分析：我們以4 X4的棋盤為例進行分析，用樹形結構表示馬走的所有過程，求從起點到終點的路徑,實際上就是從根結點開始深度優先搜索這棵樹。馬從(1 , 1)開始，按深度優先搜索法，走一步到達(2, 3)，判斷是否到達終 點，若沒有，則繼續往前走，再走一步到達 (4，4)，然后判斷是否到達終點，若到達則退出， 搜索過程結束。 為了減少搜索次數， 在馬走的過程中， 判斷下 一步所走的位置是否在棋盤上，如果不在棋盤上，則另選一

3、條路徑再走。1.4of in teger=(2,2,1,1); 仁4of in teger=(1,-1,2,-2);程序如下：con stdx:ady:afrtypemap=recordx,y:i nteger; end;vari,n ,m:i nteger;a:array0.50of map;procedure dfs(i:i nteger);var j,k:i nteger;begi nfor j:=1 to 4 doif(ai-1.x+dxj>0)a nd(ai-1.x+dxjv=n)an d(ai-1.y+dyj>0)a nd(ai-1.y+dyjv=n) the n判斷是

4、否在棋盤上beginai.x:=ai-1.x+dxj;ai.y:=ai-1.y+dyj;入棧if (ai.x=n)an d(ai.y=m)the nbeginwrite('(',1,',',1,')');for k:=2 to i do write('->(',ak.x,',',ak.y,')');halt;輸出結果并退出程序end;dfs(i+1);搜索下一步ai.x:=0;ai.y:=0;出棧end;end;begi na1.x:=1;a1.y:=1;readl n(n ,m);dfs(2

5、);write In (' no');end.從上面的例子我們可以看出，深度優先搜索算法有兩個特點：1、 己產生的結點按深度排序，深度大的結點先得到擴展，即先產生它的子結點。2、深度大的結點是后產生的，但先得到擴展，即“后產生先擴展”，與棧的 工作原理相同，因此用堆棧作為該算法的主要數據結構，存儲產生的結點。對于不同的問題，深度優先搜索算法基本上是一樣的，但在具體處理方法和編程技巧上又都不相同，甚至會有很大的差別。我們再看看另一個例子。k(k v n)。從 n個整 n=4 , k = 3, 4 個整3 + 7 + 12=223例2選數(存盤名： NOIP2OO2pj )問題描述

6、:已知n 個整數x1,x2,xn，以及一個整數數中任選k個整數相加，可分別得到一系列的和。例如當 數分別為3 , 7, 12, 19時，可得全部的組合與它們的和為:+ 7 + 19 = 297 + 12 + 19 = 383 + 12 + 19 = 34。現在，要求你計算出和為素數共有多少種。例如上例，只有一種的和為素數：3 + 7 + 19 = 29。輸入:鍵盤輸入，格式為：n , k (1<=n<=20, kv n)x1,x2 , ,xn (1<=xi<=5000000 )輸出:屏幕輸出，格式為：一個整數(滿足條件的種數)。輸入輸出樣例:輸入：4 33 7 12 1

7、9輸出：1算法分析：本題是求從n個數中選k個數的組合，并使其和為素數。求解此題時，先用深度優先搜索法生成k個數的組合， 再判斷k個數的和是否為素數，若為素數則總數加1。在程序實現過程中，用數組 a存放輸入的n個數，用s表示k個數的和，ans表示 和為素數的個數。為了避免不必要的搜索，程序對搜索過程進行了優化，限制搜索范圍，在搜索過程dfs(i,m)中，參數m為第i個數的上限，下限為n-k+i。源程序： varn ,k,i: byte;an s,s:l ongint;a: array1 . 20 of Longint;procedure prime(s:longint);判斷K個數的和是否為素數

8、 vari:i nteger;begi ni:=2;while (sqr(i)<=s)a nd(s mod i<>0) do in c(i);if sqr(i)>s then in c(a ns) 若為素數則總數加 1 end;procedure dfs(i,m:byte);搜索第 i 個數，varj:byte;j 表示第i個數的位置begi nfor j:=m to n-k+i do枚舉第 i 個數begininc(s,aj);入棧if i=k then prime(s)else dfs(i+1,j+1);繼續搜第 i+1 個數dec(s,aj) 出棧endend;b

9、egi nreadl n(n ,k);for i:=1 to n do read(ai);an s:=0; s:=0;dfs(1,1);writel n(a ns);end.從上面的兩個例子我們可以看出，用遞歸實現深度優先搜索比非遞歸更加方便。 在使用深度搜索法解題時，搜索的效率并不高，所以要重視對算法的優化,可能的減少搜索范圍，提高程序的速度。例3設有一個4*4的棋盤，用四個棋子布到格子中，要求滿足以下條件：(1) 任意兩個棋子不在同一行和同一列上；(2) 任意兩個棋子不在同一條對角線上。 試問有多少種棋局，編程把它們全部打印出來。解：PASCAL程序：Program It9_1_1;use

10、s crt;const n=4;var a:array1. n of in teger;total:i nteger;function pass(x，y:integer):boolean;var i ，j:integer;beginpass:=true;for i:=1 to x-1 doif (ai=y) or (abs(i-x)=abs(ai-y) the n beg in pass:=false;exit;e nd;end;procedure print;var i ，j:integer;beginin c(total);writeln(''，total ，'&#

11、39;);for i:=1 to n dobeginfor j:=1 to n doif j=ai then write('O ')else write('* ');write In;end;end;procedure try(k:i nteger);var i:i nteger;beginfor i:=1 to n doif pass(k , i) thenbegi nak:=i;if k=n the n printelse try(k+1);ak:=0;end;end;begi nclrscr;fillchar(a , sizeof(a) , 0);tota

12、l:=0;try(1);end.分析:這里要求找出所有滿足條件的棋局，因此需要窮舉所有可能的布子 方案，可以按如下方法遞歸產生:令D為深度，與棋盤的行相對應，初始時D=1;Procedure try(d:i nteger);beginfor i:=1 to 4 doif 第i個格子滿足條件thenbegin往第d行第i列的格子放入一枚棋子；如果d=4則得一方案，打印否則試探下一行，即try(d+1);恢復第d行第i列的格子遞歸前的狀態；end;end;這種方法是某一行放入棋子后，再試探下一行，將問題向縱深發展；若本行試探完畢則回到上一行換另一種方案。這樣必定可窮舉完所有可能的狀態。從本題可以看

13、出，前面所說的遞歸回溯法即體現了深度優先搜索的思想。上面對深度優先算法的描述就是回溯法常見的模式。例4在6*6的方格中，放入24個相同的小球，每格放一個，要求每行每列都有 4個小球(不考慮對角線)，編程輸出所有方案。解:Pascal程序: Program Ix9_1_2;uses crt;const n=6;var map:array仁n, 仁n of boolean;a:array仁 n of in teger;total:l ongint;procedure print;var i , j:integer;beginin c(total);gotoxy(1, 3);writeln('

14、;', total ,'');for i:=1 to n dobeginfor j:=1 to n doif mapi, j then write('* ')else write('O ');write In;end;end;procedure try(k:i nteger);var i , j:integer;beginfor i:=1 to n-1 doif ai<2 the n begi nmapk , i:=true;inc(ai);for j:=i+1 to n doif aj<2 the n beg inmapk,

15、 j:=true;inc(aj);if k=n the n printelse try(k+1);mapk, j:=false;dec(aj);end;mapk , i:=false;dec(ai);end;end;begi nclrscr;fillchar(map , sizeof(map) , false);fillchar(a , sizeof(a) , 0);try(1);end.分析:本題實際上是例一的變形；(1) 把枚舉每行每列四個小球轉化成為每行每列填入2個空格；(2) 用兩重循環實現往一行中放入兩個空格；(3) 用數組B記錄搜索過程中每列上空格的個數；(4) 本題利用深度搜索求

16、解時要注意及時回溯，以提高效率， 同時要注意退出遞歸時全局變量的正確恢復。例5跳馬問題:在半張中國象棋盤上，有一匹馬自左下角往右上角跳，今規定只 許往右跳，不許往左跳，圖(A)給出的就是一種跳行路線。編程計算共有多少種 不同的跳行路線，并將路線打印出來。解：PASCAL程序：Program It9_1_2;uses crt;const d:array1.4 ， 1.2 of shortint=(2， 1)，(1， 2)，(-1 ， 2)， (-2，1);var a:array1.10， 1.2 of shorti nt;total:i nteger;function pass(x，y， i:i

17、nteger):boolean;beginif (x+di ，1<0) or (x+di ，1>4) or (y+di ，2>8)the n pass:=false else pass:=true;end;procedure prin t(k:i nteger);var i:i nteger;beginin c(total);write(''，total ， ' : (0， 0)');for i:=1 to k dowrite('->('，ai，1，ai，2，')');write In;end;proced

18、ure try(x , y, k:integer); var i:i nteger;beginfor i:=1 to 4 doif pass(x , y, i) thenbegi nak, 1:=x+di, 1;ak, 2:=y+di, 2;if (ak, 1=4) and (ak , 2=8) then prin t(k)else try(ak,1 , ak ,2 , k+1);end;end;begi nclrscr;total:=0;');try(0 , 0 , 1); writelnPress any key to exit. repeat un til keypressed;

19、 end.分析:（1）這里可以把深度d定為馬跳行的步數,馬的位置可以用它所在的行與列表示因此初始時馬的位置是（0 , 0）;（2）位置在（x，y）上的馬可能四種跳行的方向，如圖 （B），這四種方向，可 以按 x，y 的增量分別記為（2，1），（1，2），（-1，2），（-2，1）（3）一種可行的跳法是指落下的位置應在棋盤中。深度優先搜索的非遞歸算法program DFS(dep); dep:=0;repeatdep:=dep+1;j:=j+1;if mr符合條件then產生子結點mr并將其記錄if子結點是目標the n 輸出并出棧else p:=true;elseif j>maxj th

20、en回溯 else p:=false;en dif;un til p=true;un til dep=0;其中回溯過程如下： procedure backtrack ing;dep:=dep-1;if dep>0 then取回棧頂元素else p:=true;練習一:1、有一括號列S由N個左括號和N個右括號構成，現定義好括號列如下：(1) 若A是好括號列，則(A)也是；(2) 若A和B是好括號列，則 AB也是好的。例如：()()是好的，而()()則不是，現由鍵盤輸入N，求滿足條件的所的好括 號列，并打印出來。解:Pacal程序:Program Ix9_1_1;uses crt;var n

21、:i nteger;total:l ongint;procedure try(x ，y:integer;s:string); var i:i nteger;begin，''，s);if (x=n) and (y=n) the n begi ninc(total);writeln(''， totalendelse beg inif x<n then try(x+1，y，s+'(');if y<x then try(x，y+1，s+')');end;end;begi nclrscr;write('N=');

22、readl n(n); total:=0;try(0 ，0，''); end.分析:從好括號列的定義可知，所謂的 "好括號列"就是我們在表達式里所說的正 確匹配的括號列，其特點是 ：從任意的一個位置之前的右括號的個數不能超過左括號的個數。 由這個特點， 可以構造一個產生好括號列的方法 :用x，y記錄某一 狀態中左右括號的個數；若左括號的個數小于N(即x<N)，則可加入一個左括號；若 右括號的個數小于左括號的個數， 則可加入一個右括號， 如此重復操作， 直至產 生一個好括號列。2、排列組合問題： 從數碼1-9中任選N個不同的數作不重復的排列(或組合) 求

23、出所有排列(或組合)的方案及總數。3、填數游戲一:以下列方式向5*5的矩陣中填入數字。設數字i（1v=i<=25）己被置 于座標位置（x , y），則數字i+1的座標位置應為（z , w）, （z , w）可根據下列關系由 （x， y）算出。（1） （z ，w）=（x ± 3，y）（z ，w）=（x，y ± 3）（z ，w）=（x ± 2，y ± 2）例如數字1的起始位置座標被定為（2，2），則數字2的可能位置座標是：（5，2），（2，5），或（4，4）。編寫一個程序，當數字1被指定于某一起始位置時，列 舉其它24個數字應在的位置，列舉出該條件下的

24、所有可有的方案。解:同例二類似，只不過方向增量變為（3，0），（-3，0），（0，3），（0，-3），（2，2），（2，-2），（-2，2），（-2，-2）。Pascal 程序:Program Ix9_1_3;uses crt; const n=5;d:array1.8， 1.2 of short in t=（3，0），（-3，0），（0，3），（0，-3），（2 ，2），（2，-2），（-2，2），（-2， -2）;var x0 ， y0:byte;a:array仁 n， 1. .n of byte;total:l ongint;procedure print;var i ，j:intege

25、r;beginin c（total）;gotoxy（1 ， 3）;writeln（''，total，''）;for i:=1 to n dobeginfor j:=1 to n dowrite（ai，j:3）;write In;end;end;procedure try（x ，y， k:byte）;var i ，x1，y1:integer;beginfor i:=1 to 8 dobeginx1:=x+di，1;y1:=y+di， 2;if （x1>0） and （y1>0） and （x1<=n）and （y1<=n） and （ax1

26、， y1=0） thenbeginax1, y1:=k;if k=n*n then printelse try(x1, y1 , k+1);ax1, y1:=0;end;end;end;begi nclrscr;write('xO , y0=');readln(xO , y0); fillchar(a , sizeof(a), 0);total:=0;ax0 , y0:=1;try(x0 , y0, 2);writeln('Total=', total);write In ('Press any key to exit.。');repeat un

27、 til keypressed;end.5、填數游戲二。有一個 M*N的矩陣，要求將1至M*N的自然數填入矩陣中，滿 足下列條件:(1) 同一行中，右邊的數字比左邊的數字大;(2) 同一列中，下面的數字比上面的數字大。 打印所有的填法，并統計總數。解:Pascal程序:$Q-， R-， S-Program Ix9_1_4;uses crt;const m=3;n=6;var a:array0.m ，0.n of integer;used:array1.m* n of boolea n;total:l ongint;procedure print;var i ，j:integer;beginin

28、c(total);gotoxy(1， 3);writeln(''，total ，'');for i:=1 to m dobeginfor j:=1 to n dowrite(ai，j：3);write In;end;end;procedure try(x , y:integer);var i:i nteger;beginfor i:=x*y to m*n-( m-x+1)* (n- y+1)+1 doif not usedi a nd (i>ax-1, y) and (i>ax , y-1) thenbegi nax, y:=i;usedi:=tru

29、e;if i=m*n-1 then printelse beg inif y=n the n try(x+1, 1)else try(x, y+1);end;usedi:=false;end;end;begi nclrscr;fillchar(used , sizeof(used) , false);fillchar(a , sizeof(a) , 0);a1, 1:=1;am, n:=m*n;used1:=true;usedm* n:=true;try(1 , 2);writeln('Total=', total);end.分析:本題可以將放入格子中的數字的個數作為深度，先往

30、格子(1 , 1)放第一個數，然后依次往格子(1 , 2) , (1 , 3)，(m, n-1) , (m, n)填數字，每填一個數 時應如何判斷該數是否滿足條件，做到及時回溯，以提高搜索的效率是非常關鍵的。為此需要認真研究題目的特點。根據題意可以知道:在任何一個K*L的格子里，最左上角的數字必定是最小的，而最右下角的數字必定是最大的，故有:(1) 格子(1，1)必定是填數1。格子(m，n)必定填數m*n;(2) 若 A 是格子(x，y)所要填入數，則有：x*yv=A<=m*n-(m-x+1)*(n-y+1)+1;6、反幻方:在3*3的方格中填入1至9,使得橫，豎，對角上的數字之和都不相

31、 等。下圖給出的是一例。請編程找出所有可能的方案。1213458697分析:(1) 深度優先搜索。用一個二維數組A來存儲這個3*3的矩陣。(2) 用x表示行，y表示列，搜索時應注意判斷放入格子(x , y)的數碼是否符合要求；(a) 如果y=3，就計算這一行的數碼和，其值存放在Ax， 4中，如果該和 己出現過，貝U回溯；(b) 如果x=3，則計算這一列的數碼和，其值存放在A4 , y中，并進行判斷 是否需要回溯；(c) 如果x=3 , y=1還應計算從左下至右上的對角線的數碼和；d)如果x=3 , y=3還應計算從左上至右下的對角線的數碼和。為了提高搜索速度，可以求出本質不同的解，其余的解可以

32、由這些本質不同的解通過旋轉和翻轉得到。為了產生非本質解，搜索時做如下規定:(a) 要求 a1 , 1<a3 , 1<a1 , 3<a3 , 3;(b) 要求 a2 , 1>a1 , 2.解：略7、將M*N個0和1填入一個M*N的矩陣中，形成一個數表A,all a12 . a1nA= a21 a22 . a2nam1 am2 . amn數表A中第i行和數的和記為ri(i=1 , 2, . , m)，它們叫做A的行和向量，數表 A第j列的數的和記為qj(j=1 , 2, . , m)，它們叫做A的列和向量?，F由文件讀入 數表A的行和列，以及行和向量與列和向量，編程求出滿足條

33、件的所的數表 A。分析：本題是將例題般化，將若干個1放入一個M*N的方陣中，使得每行和每列上的1的個數滿足所給出的要求。思路:(1)應該容易判斷，若 r1+r2+.+rnv>q1+q2+.+qm，則問題無解；(2) 將放入1的個數看做是深度，1的位置記為(x , y)，其中x代表行，y 代表列，第一個1應從(1 , 1)開始試探；(3) 往k行放入一個1時，若前一個1的位置是(k , y),則它的位置應在第 k行的y+1列至(m-本行還應放入1的個數+1)這個范圍內進行試探；若這一列上 己放入1的個數小于qy，則該格子內放入一個1，并記錄下來；否則換一個位置試 探。Program Ix9

34、_1_6;uses crt;const max=20;var m , n, s1, s2:integer;map:array1.max ,1.max of 0.1;a , b, c, d:array1.max of integer;total:l ongint;procedure error;beginwrite In ('NO ANSWER!');write In ('Press any key to exit.。');repeat un til keypressed;halt;end;procedure in it;var f:tex t;fn:stri n

35、g;i , j:integer;beginwrite('File name:');readl n(fn);assign(f, fn);reset(f);readln(f, m, n);s1:=0;s2:=0;for i:=1 to m dobeg in read(f, ai);s1:=s1+ai;e nd;for i:=1 to n dobeg in read(f, bi);s2:=s2+bi;e nd;close(f);if s1<>s2 then error;fillchar(map , sizeof(map) , 0);fillchar(c, sizeof(c

36、), 0);fillchar(d, sizeof(d), 0);end;procedure print;var i , j:integer;begininc(total);gotoxy(1, 3);writeln('', total ,'');for i:=1 to m dobeginfor j:=1 to n dowrite(mapi, j:3);write In;end;end;procedure try(x , y, t:integer);var i , j:integer;beginfor i:=y+1 to n-(ax-cx)+1 doif (mapx

37、 , i=0) and (di<bi) thenbegi nmapx, i:=1;inc(cx);inc(di);if t=s1 then printelse if (x<=m) the n begi nif cx=ax the n try(x+11 else try(x.end;,0, t+1),i ,t+1);,i:=O;dec(cx);dec(di);mapx end;(一) 問題分析1. 迷宮的表示方法：迷宮可以用一個二維數組A (Y, X)表示，其中，Y表示行，X表示列。數組中的元素由數字 0和1組成，當A(丫，X)=1時表示墻；當A( 丫，X)=0時表示路。2. 搜索方

38、向的識別：對于迷宮中的任意一點A ( 丫，X)，有四個搜索方向：向上 A ( Y-1，X)；向下A(Y+1，X);向左 A (丫，X-1);向右 A (丫，X+1 )3. 搜索方向的表示方法：(0， 1)表示向右；(-1 ， 0)表示向上；(0。-1 ) 表示向左；(1，0 )表示向下4. 向某個方向試探一步：在搜索時一定要注意，任何一點的坐標加上搜索方向的坐標增量后，都要判斷是否超出了迷宮的邊界。當不出界時，A (丫， X) =0表示該方向為通路。5. 當從死胡同退出時，要將路堵死，可將其標記為2。6. 在搜索中還要建立一個堆棧，將所走過的路記錄下來，后退時將退出的路從堆棧中彈出。這樣保證了

39、最終保存的是迷宮的一條出路。棧底元素為入口坐標，棧頂元素為迷宮的出口坐標。(二) 產生式系統1. 數據庫。為了要存儲所走過的路，每個記錄要有：行，列坐標，搜索方向三個數據，而且數據庫應組成堆棧形式，并用DEP作為棧頂指針，同時表示搜索深度。2. 產生規則。共有八條，可用數組DX和Dy表示方向增量： nx=x+dx(j);n y=y+dy(j)if (nx, ny)是通路then (nx, ny)是新結點3. 搜索策略。由于迷宮較大，為了防止溢出應米用非遞歸算法。(三) PASCAL源程序Program labyri nth(output);uses crt;type no de=recordx

40、x,yy:byte;r:byte;end;all=array0.11,0.11 of byte;const dx:array1.4 of integer=(0,1,0,-1); dy:array1.4of in teger=(1,0,-1,0);a:all=(1,1,1,1,1,1,1,1,1,1,1,1),(1,0,0,0,0,0,0,1,0,1,1,1),(1,0,1,0,1,1,0,0,0,0,0,1),(1,0,1,0,1,1,0,1,1,1,0,1),(1,0,1,0,0,0,0,0,1,0,0,1),(1,0,1,1,1,1,1,1,1,1,1,1),(1,0,0,0,1,0,1,0,1,1,1,1),(1,0,1,1,1,0,0,0,0,0,0,1),(1,0,0,0,0,0,1,0,1,1,0,1),(1,1,1,0,1,1,1,0,0,1,1,1),(1,1,1,1,1,1,1,1,0,1,1,1),(1,1,1,1,1,1,1,1,1,1,1,1); var b:all;dep,j,k,x,y,xo,yo, nx,n y:i nteger;path:array0.300 of node;p:boolea n;procedure wai