1、常用算法深度優先搜索（degree first serch）吳孝燕O O一、深度優先搜索的基本思路把一個具體的問題抽象成了一個圖論 的模型樹（如圖）。狀態對應著結點，狀態之間的關系 （或者說決策方案）對應著邊。這樣 的一棵樹就叫搜索樹。（一）基本思路1、在每個階段的決策時，采取能深則深的原則試探所有可行的方案，一旦深入一層則 保存當前操作引起的狀態。2、一旦試探失敗，為了擺脫當前失敗狀態，采取回到上一階段嘗試下一方案的策略 （回溯策略）；或者在求解所有解時，求得一個解后，回溯到上一階段嘗試下一方案，以求 解下一個解。3、在各個階段嘗試方案時，采取的是窮舉的思想。（二）引題【例1】選擇最短路徑。

2、有如下所示的交通路線圖，邊上數值表示該道路的長度，編程求 從1號地點到達7號地點的最短的路徑長度是多少，并輸出這個長度。數據結構。Bi表示結點i是否已經遍歷過2、用變量min來保存最優解，而用tot變量保存求解過程中臨時解（當前路徑總長 度）。3、狀態。Tot的值和結點的遍歷標志值。程序結構1、遞歸結構。2、主程序中用try（1）調用遞歸子程序。3、子程序結構。procedure try（I:i nteger）;var k:i nteger;beg inif到達了終點then beg in保存較優解；返回上一點繼續求解（回溯）；endelsebegin窮舉從 I 出發當前可以直接到達的點 k；

3、if I 到 k 點有直接聯邊 并且 k 點沒有遍歷過 then then begintry(k);把 AI,K 累加入路徑長度 tot;k 標記為已遍歷； 現場恢復； end;end;子程序procedure try(i:integer);var k:integer;beginif i=n then begin if tot<min then min:=tot;exit;end else begin for k:=1 to n doif (bk=0) and (i<>k) and (ai,k<32700) then begin bk:=1;tot:=tot+ai,k;

4、try(k);bk:=0;tot:=tot-ai,k; end;end;end;主程序數據輸入 readln(fi,n); for i:=1 to n do begin for j:=1 to n do read(fi,ai,j); readln(fi); end; close(fi);主程序預處理和調用子程序 tot:=0;min:=maxint;b1:=1; try(1);writeln('tot=',min);(三) 遞歸程序結構框架Procedure try(i:integer);Var k:integer; BeginIf 所有階段都已求解thenBeg in比較最優

5、解并保存；回溯；endelsebegi nfor k:=i深度可能決策范圍；do begin窮舉當前階段所有可能的決策（方案、結點）kif k 方案可行 then begin記錄狀態變化；try（i+1）;狀態恢復（回溯）；endend;end;En d;二、深度優先搜索的應用例1:有A, B, C, D, E 5本書，要分給張、王、劉、趙、錢 5位同學，每人只選一本。每 人將喜愛的書填寫下表，輸出每人都滿意的分書方案。ABCDE張11王111劉11趙1錢11program allotbook;type five=1.5;const like:arrayfive,five of O.1 =(0

6、,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1);n ame:arrayfive of stri ng5=('zha ng','wa ng','liu','zhao','qia n'); var book:arrayfive of five;flag:set of five;c:i nteger;procedure print;var i:i nteger;begi nin c(c);write In ('a nswer',c,

7、9;:');for i:=1 to 5 dowritel n(n amei:10,':',chr(64+booki); end;procedure try(i:i nteger);var j:i nteger;begi nif i>5 the n printelse beg infor j:=1 to 5 doif not(j in flag) and (likei,j>0) the n beg in flag:=flag+j;booki:=j;try(i+1); flag:=flag-j;endend; end; begi n flag:=;c:=0; t

8、ry(1); readl n;end.例2:中國象棋棋盤如下圖馬自左下角往右上角跳.規定只許往左跳，不許往右跳（如圖跳法） 編程找出所有跳法。program tiaoma;constdi:array1.4 of in teger=(1,2,2,1);dj:array1.4 of in teger=(2,1,-1,-2);var x,y:array0.20 of integer;c:i nteger;procedure prin t(dep:i nteger);var j:i nteger;begi nc:=c+1;write(c,':');for j:=0 to dep-1 d

9、o write('(',xj,',',yj,')->');writeln('(',xdep,',',ydep,')');end;procedure try(dep,i,j:integer);var r,ni,nj:byte;beginif (i=8) and (j=4) then print(dep-1)else beginfor r:=1 to 4 dobeginni:=i+dir;nj:=j+djr;if (ni>0)and(ni<=8)and(nj>=0)and(nj&

10、lt;=4) thenbeginxdep:=ni;ydep:=nj ;try(dep+1,ni,nj)end;end;end;end;beginx0:=0;y0:=0;c:=0;try(1,0,0);readln;end.三、深度優先搜索在奧賽中的應用1、NOIP1999 郵票面值設計給定一個信封，最多只允許粘貼 N張郵票，計算在給定K( N+k<=40 種郵票的情況下(假 定所有的郵票數量都足夠)，如何設計郵票的面值，能得到最大max，使得1-ma>之間的每一個郵資值都能得到。program noip4;varn,k:integer;procedure get(p:integer

11、,var maxn:integer);varbegint:=can;for i:=1 to p dofor j:=0 to maxn doif canj then tj+nowi:=true;can:=t; maxn:=maxn+nowp;end;procedure solve(p,last,max:integer); begin if p=k then begin if max>best then begin best:=max;answer:=now;end;exit;end;for i:=last+1 to max+1 do begin nowp+1:=i;h:=0; fillch

12、ar(can,sizeof(can),false);can0:=true;for j:=1 to n do get(p+1,h);for j:=1 to h+1 do if not canj then begin ma:=j-1;break;end;solve(p+1,i,ma);end;end;main begin readln(n,k);best:=0; solve(0,0,0);i:=02、NOIP2001 數的劃分將整數n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。 例如：n=7，k=3，下面三種分法被認為是相同的。1， 1， 5; 1 ， 5， 1; 5 ， 1，

13、1; 問有多少種不同的分法。輸入： n， k (6<n<=200 ， 2<=k<=6) 輸出：一個整數，即不同的分法。procedure work(dep,pre,s:longint); 入口為 work(1,1,n)dep為當前試放的第dep個數,pre為前一次試放的數,s為當前剩余可分的總數var j:longint;beginif dep=n then beginif s>=pre then inc(r); exit;end;for j:=pre to s div 2 do work(dep+1,j,s-j);end;也可利用回溯思想procedure try(dep:integer);var i:integer;beginif dep=k then beginif tot>=adep-1 then inc(sum);exit; end;for i:=adep-1 to tot div 2 do b