深度优先算法.doc

常用算法深度优先搜索(degree first serch)吴孝燕一、 深度优先搜索的基本思路把一个具体的问题抽象成了一个图论的模型树（如图）。状态对应着结点，状态之间的关系（或者说决策方案）对应着边。这样的一棵树就叫搜索树。（一）基本思路n1、在每个阶段的决策时，采取能深则深的原则试探所有可行的方案，一旦深入一层则保存当前操作引起的状态。n2、一旦试探失败，为了摆脱当前失败状态，采取回到上一阶段尝试下一方案的策略（回溯策略）；或者在求解所有解时，求得一个解后，回溯到上一阶段尝试下一方案，以求解下一个解。n3、在各个阶段尝试方案时，采取的是穷举的思想。（二）引题【例1】选择最短路径。有如下所示的交通路线图，边上数值表示该道路的长度，编程求从1号地点到达7号地点的最短的路径长度是多少，并输出这个长度。l 数据结构1、邻接矩阵表示图的连接和权值。AI,j=x,或者aI,j=maxint。Bi表示结点i是否已经遍历过。2、用变量min来保存最优解，而用tot变量保存求解过程中临时解（当前路径总长度）。3、状态。Tot的值和结点的遍历标志值。l 程序结构1、递归结构。2、主程序中用try(1)调用递归子程序 。3、子程序结构。nprocedure try(I:integer);nvar k:integer;nbeginn if 到达了终点 then begin 保存较优解；返回上一点继续求解（回溯）；endn elsen beginn 穷举从I出发当前可以直接到达的点k；n if I到k点有直接联边 并且 k点没有遍历过 then n then beginn 把AI,K累加入路径长度tot;k标记为已遍历；try(k);n 现场恢复；n end;n end;l 子程序procedure try(i:integer);var k:integer;begin if i=n then begin if totmin then min:=tot;exit;end else begin for k:=1 to n do if (bk=0) and (ik) and (ai,k5 then print else begin for j:=1 to 5 do if not(j in flag) and (likei,j0) then begin flag:=flag+j; booki:=j; try(i+1); flag:=flag-j; end end;end;begin flag:=; c:=0; try(1); readln;end.例2: 中国象棋棋盘如下图马自左下角往右上角跳.规定只许往左跳,不许往右跳(如图跳法)编程找出所有跳法。program tiaoma;constdi:array1.4 of integer=(1,2,2,1);dj:array1.4 of integer=(2,1,-1,-2);var x,y:array0.20 of integer;c:integer;procedure print(dep:integer); var j:integer; begin c:=c+1;write(c,:); for j:=0 to dep-1 do write(,xj,yj,)-); writeln(,xdep,ydep,); end;procedure try(dep,i,j:integer); var r,ni,nj:byte; begin if (i=8) and (j=4) then print(dep-1) else begin for r:=1 to 4 do begin ni:=i+dir; nj:=j+djr; if (ni0)and(ni=0)and(nj=4) then begin xdep:=ni;ydep:=nj ; try(dep+1,ni,nj) end; end; end; end;begin x0:=0;y0:=0; c:=0; try(1,0,0); readln;end.三、深度优先搜索在奥赛中的应用 1、NOIP1999 邮票面值设计 给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+kbest then begin best:=max;answer:=now; end; exit; end; for i:=last+1 to max+1 do begin nowp+1:=i; h:=0; fillchar(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:=0 2、NOIP2001 数的划分 将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。 例如：n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 输入：n，k (6n=200，2=k=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; begin if dep=k then begin if tot=adep-1 then inc(sum); exit; end; for i:=adep-1 to tot div 2 do begin adep:=i; dec(tot,i); try(dep+1); inc(tot,i); end; end;try 深度优先搜索算法是算法设计中最为基