深度优先算法

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