深度優(yōu)先算法

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

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

3、if I 到 k 點(diǎn)有直接聯(lián)邊 并且 k 點(diǎn)沒有遍歷過 then then begintry(k);把 AI,K 累加入路徑長度 tot;k 標(biāo)記為已遍歷； 現(xiàn)場恢復(fù)； 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;主程序數(shù)據(jù)輸入 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);主程序預(yù)處理和調(diào)用子程序 tot:=0;min:=maxint;b1:=1; try(1);writeln('tot=',min);(三) 遞歸程序結(jié)構(gòu)框架Procedure try(i:integer);Var k:integer; BeginIf 所有階段都已求解thenBeg in比較最優(yōu)

5、解并保存；回溯；endelsebegi nfor k:=i深度可能決策范圍；do begin窮舉當(dāng)前階段所有可能的決策（方案、結(jié)點(diǎn)）kif k 方案可行 then begin記錄狀態(tài)變化；try（i+1）;狀態(tài)恢復(fù)（回溯）；endend;end;En d;二、深度優(yōu)先搜索的應(yīng)用例1:有A, B, C, D, E 5本書，要分給張、王、劉、趙、錢 5位同學(xué)，每人只選一本。每 人將喜愛的書填寫下表，輸出每人都滿意的分書方案。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:中國象棋棋盤如下圖馬自左下角往右上角跳.規(guī)定只許往左跳，不許往右跳（如圖跳法） 編程找出所有跳法。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.三、深度優(yōu)先搜索在奧賽中的應(yīng)用1、NOIP1999 郵票面值設(shè)計(jì)給定一個(gè)信封，最多只允許粘貼 N張郵票，計(jì)算在給定K( N+k<=40 種郵票的情況下(假 定所有的郵票數(shù)量都足夠)，如何設(shè)計(jì)郵票的面值，能得到最大max，使得1-ma>之間的每一個(gè)郵資值都能得到。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 數(shù)的劃分將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。 例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。1， 1， 5; 1 ， 5， 1; 5 ， 1，

13、1; 問有多少種不同的分法。輸入： n， k (6<n<=200 ， 2<=k<=6) 輸出：一個(gè)整數(shù)，即不同的分法。procedure work(dep,pre,s:longint); 入口為 work(1,1,n)dep為當(dāng)前試放的第dep個(gè)數(shù),pre為前一次試放的數(shù),s為當(dāng)前剩余可分的總數(shù)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