2022年深度优先搜索DFS .pdf

《2022年深度优先搜索DFS .pdf》由会员分享，可在线阅读，更多相关《2022年深度优先搜索DFS .pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、深度优先搜索所谓 深度 是对产生问题的状态结点而言的， 深度优先 是一种控制结点扩展的策略， 这种策略是优先扩展深度大的结点，把状态向纵深发展。 深度优先搜索也叫做 DFS法(Depth First Search)。深度优先搜索的递归实现过程：procedure dfs(i); for j:=1 to r do if 子结点 mr 符合条件 then 产生的子结点 mr入栈；if 子结点 mr 是目标结点 then 输出 else dfs(i+1); 栈顶元素出栈（即删去mr）; endif; endfor; 例 1 骑士游历 : 设有一个 n*m的棋盘，在棋盘上任一点有一个中国象棋马. 马走

2、的规则为 : 1. 马走日字2. 马只能向右走。当 N,M 输入之后 , 找出一条从左下角到右上角的路径。例如: 输入 N=4,M=4，输出: 路径的格式 :(1,1)-(2,3)-(4,4)，若不存在路径 , 则输出 no 算法分析：我们以 44 的棋盘为例进行分析， 用树形结构表示马走的所有过程，求从起点到终点的路径 , 实际上就是从根结点开始深度优先搜索这棵树。马从（ 1，1）开始，按深度优先搜索法，走一步到达（2，3），判断是否到达终点，若没有，则继续往前走， 再走一步到达 （4，4），然后判断是否到达终点，若到达则退出，搜索过程结束。为了减少搜索次数，在马走的过程中，判断下一步所走的

3、位置是否在棋盘上，如果不在棋盘上，则另选一条路径再走。程序如下：const dx:array1.4of integer=(2,2,1,1); dy:array1.4of integer=(1,-1,2,-2); type 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - map=record x,y:integer; end; var i,n,m:integer; a:array0.50of map; procedure dfs

4、(i:integer); var j,k:integer; begin for j:=1 to 4 do if (ai-1.x+dxj0)and(ai-1.x+dxj0)and(ai-1.y+dyj(,ak.x,ak.y,); halt;输出结果并退出程序 end; dfs(i+1);搜索下一步 ai.x:=0;ai.y:=0;出栈 end; end; begin a1.x:=1;a1.y:=1; readln(n,m); dfs(2); writeln(no); end. 从上面的例子我们可以看出，深度优先搜索算法有两个特点：1、己产生的结点按深度排序， 深度大的结点先得到扩展， 即先产生它

5、的子结点。2、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。对于不同的问题， 深度优先搜索算法基本上是一样的，但在具体处理方法和编程技巧上又都不相同，甚至会有很大的差别。我们再看看另一个例子。 例 2 选数（存盘名： NOIP2002pj） 问题描述 : 已知 n 个整数 x1,x2,xn，以及一个整数 k(k n)。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k3，4 个整数分别为 3 ，7，12，19 时，可得全部的组合与它们的和为：3712=22 3名师资料总结 - - -

6、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 71929 7121938 3121934。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：371929。 输入 ：键盘输入，格式为：n , k (1=n=20，kn) x1,x2 ，,xn （ 1=xi=5000000） 输出 ：屏幕输出，格式为：一个整数（满足条件的种数）。 输入输出样例 : 输入： 4 3 3 7 12 19 输出： 1 算法分析：本题是求从 n 个数中选 k

7、个数的组合，并使其和为素数。 求解此题时，先用深度优先搜索法生成k 个数的组合， 再判断 k 个数的和是否为素数， 若为素数则总数加 1。在程序实现过程中，用数组a 存放输入的 n 个数，用 s 表示 k 个数的和， ans 表示和为素数的个数。 为了避免不必要的搜索， 程序对搜索过程进行了优化，限制搜索范围，在搜索过程dfs(i,m)中，参数 m为第 i 个数的上限，下限为n-k+i 。源程序：var n,k,i: byte; ans,s:longint; a: array1 . 20 of Longint; procedure prime(s:longint);判断 K个数的和是否为素数

8、var i:integer; begin i:=2; while (sqr(i)=s)and(s mod i0) do inc(i); if sqr(i)s then inc(ans)若为素数则总数加1 end; procedure dfs(i,m:byte);搜索第 i 个数， var j:byte;j表示第 i 个数的位置begin for j:=m to n-k+i do枚举第 i 个数 begin inc(s,aj);入栈 if i=k then prime(s) else dfs(i+1,j+1);继续搜第 i+1 个数 dec(s,aj)出栈 end end; begin 名师资料

9、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - readln(n,k); for i:=1 to n do read(ai); ans:=0; s:=0; dfs(1,1); writeln(ans); end. 从上面的两个例子我们可以看出，用递归实现深度优先搜索比非递归更加方便。在使用深度搜索法解题时， 搜索的效率并不高， 所以要重视对算法的优化， 尽可能的减少搜索范围，提高程序的速度。 例 3 设有一个 4*4 的棋盘，用四个棋

10、子布到格子中，要求满足以下条件: (1)任意两个棋子不在同一行和同一列上; (2)任意两个棋子不在同一条对角线上。试问有多少种棋局，编程把它们全部打印出来。解：PASCAL 程序：Program lt9_1_1; uses crt; const n=4; var a:array1.n of integer; total:integer; function pass(x，y:integer):boolean; var i，j:integer; begin pass:=true; for i:=1 to x-1 do if (ai=y) or (abs(i-x)=abs(ai-y) then be

11、gin pass:=false;exit;end; end; procedure print; var i，j:integer; begin inc(total); writeln(，total，); for i:=1 to n do begin for j:=1 to n do if j=ai then write(O ) else write(* ); writeln; end; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - -

12、- - - - procedure try(k:integer); var i:integer; begin for i:=1 to n do if pass(k，i) then begin ak:=i; if k=n then print else try(k+1); ak:=0; end; end; begin clrscr; fillchar(a，sizeof(a)，0); total:=0; try(1); end. 分析: 这里要求找出所有满足条件的棋局，因此需要穷举所有可能的布子方案，可以按如下方法递归产生: 令 D为深度，与棋盘的行相对应，初始时D=1; Procedure tr

13、y(d:integer); begin for i:=1 to 4 do if 第 i 个格子满足条件 then begin 往第 d 行第 i 列的格子放入一枚棋子 ; 如果 d=4则得一方案，打印否则试探下一行，即try(d+1); 恢复第 d 行第 i 列的格子递归前的状态 ; end; end; 这种方法是某一行放入棋子后，再试探下一行，将问题向纵深发展; 若本行试探完毕则回到上一行换另一种方案。这样必定可穷举完所有可能的状态。从本题可以看出， 前面所说的递归回溯法即体现了深度优先搜索的思想。上面对深度优先算法的描述就是回溯法常见的模式。 例 4 在 6*6 的方格中，放入 24 个相

14、同的小球，每格放一个，要求每行每列都有4 个小球 ( 不考虑对角线 )，编程输出所有方案。解:Pascal 程序: Program lx9_1_2; uses crt; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - const n=6; var map:array1.n，1.n of boolean; a:array1.n of integer; total:longint; procedure print; var i，j

15、:integer; begin inc(total);gotoxy(1，3); writeln(，total，); for i:=1 to n do begin for j:=1 to n do if mapi，j then write(* ) else write(O ); writeln; end; end; procedure try(k:integer); var i，j:integer; begin for i:=1 to n-1 do if ai2 then begin mapk，i:=true; inc(ai); for j:=i+1 to n do if aj2 then be

16、gin mapk，j:=true; inc(aj); if k=n then print else try(k+1); mapk，j:=false; dec(aj); end; mapk，i:=false; dec(ai); end; end; begin clrscr; fillchar(map，sizeof(map) ，false); fillchar(a，sizeof(a)，0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - -

17、 - - try(1); end. 分析: 本题实际上是例一的变形 ; (1)把枚举每行每列四个小球转化成为每行每列填入2 个空格 ; (2)用两重循环实现往一行中放入两个空格; (3)用数组 B记录搜索过程中每列上空格的个数; (4)本题利用深度搜索求解时要注意及时回溯，以提高效率， 同时要注意退出递归时全局变量的正确恢复。 例 5 跳马问题 : 在半张中国象棋盘上，有一匹马自左下角往右上角跳，今规定只许往右跳，不许往左跳，图(A) 给出的就是一种跳行路线。编程计算共有多少种不同的跳行路线，并将路线打印出来。解：PASCAL 程序：Program lt9_1_2; uses crt; con

18、st d:array1.4，1.2 of shortint=(2，1)，(1 ，2)，(-1 ，2)，(-2 ，1); var a:array1.10，1.2 of shortint; total:integer; function pass(x，y，i:integer):boolean; begin if (x+di，14) or (y+di，28) then pass:=false else pass:=true; end; procedure print(k:integer); var i:integer; begin inc(total); write(，total ， : (0，0)

19、; for i:=1 to k do write(-(，ai ，1 ， ， ，ai ，2 ，); writeln; end; procedure try(x，y，k:integer); var i:integer; begin for i:=1 to 4 do if pass(x，y，i) then begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - ak，1:=x+di，1;ak ，2:=y+di，2; if (ak

20、，1=4) and (ak，2=8) then print(k) else try(ak，1 ，ak ，2 ，k+1); end; end; begin clrscr; total:=0; try(0，0，1); writeln(Press any key to exit.。); repeat until keypressed; end. 分析:(1) 这里可以把深度 d 定为马跳行的步数， 马的位置可以用它所在的行与列表示因此初始时马的位置是(0，0); (2)位置在 (x ，y) 上的马可能四种跳行的方向，如图(B) ，这四种方向，可以按 x，y 的增量分别记为 (2 ，1)，(1，2)

21、，(-1 ，2)，(-2 ，1) (3)一种可行的跳法是指落下的位置应在棋盘中。深度优先搜索的非递归算法program DFS(dep); dep:=0; repeat dep:=dep+1; j:=j+1; if mr 符合条件 then 产生子结点 mr 并将其记录if 子结点是目标 then 输出并出栈else p:=true; else if jmaxj then 回溯 else p:=false; endif; until p=true; until dep=0; 其中回溯过程如下：procedure backtracking; dep:=dep-1; if dep0 then 取回

22、栈顶元素else p:=true; 练习一 : 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - 1、有一括号列 S由 N个左括号和 N个右括号构成，现定义好括号列如下: (1) 若 A是好括号列，则 (A) 也是; (2) 若 A和 B 是好括号列，则 AB也是好的。例如:()()是好的，而 ()()则不是，现由键盘输入N ，求满足条件的所的好括号列，并打印出来。解:Pacal 程序: Program lx9_1_1; use

23、s crt; var n:integer; total:longint; procedure try(x，y:integer;s:string); var i:integer; begin if (x=n) and (y=n) then begin inc(total);writeln(，total ， ，s); end else begin if xn then try(x+1，y，s+(); if yx then try(x，y+1，s+); end; end; begin clrscr; write(N=);readln(n); total:=0;try(0，0，); end. 分析:

24、从好括号列的定义可知，所谓的 好括号列 就是我们在表达式里所说的正确匹配的括号列，其特点是: 从任意的一个位置之前的右括号的个数不能超过左括号的个数。 由这个特点， 可以构造一个产生好括号列的方法: 用 x，y 记录某一状态中左右括号的个数 ; 若左括号的个数小于N(即 xN)，则可加入一个左括号 ;若右括号的个数小于左括号的个数，则可加入一个右括号， 如此重复操作， 直至产生一个好括号列。2、排列组合问题：从数码 1-9 中任选 N个不同的数作不重复的排列（或组合），求出所有排列（或组合）的方案及总数。3、填数游戏一 : 以下列方式向 5*5 的矩阵中填入数字。设数字i(1=i0) and

25、(y10) and (x1=n) and (y1ax-1，y) and (iax，y-1) then begin ax，y:=i;usedi:=true; if i=m*n-1 then print else begin if y=n then try(x+1，1) else try(x，y+1); end; usedi:=false; end; end; begin clrscr; fillchar(used，sizeof(used)，false); fillchar(a，sizeof(a)，0); a1 ，1:=1;am ，n:=m*n; used1:=true;usedm*n:=true

26、; try(1，2); writeln(Total=，total); end. 分析: 本题可以将放入格子中的数字的个数作为深度，先往格子(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) 所要填入数， 则有

27、:x*y=A=m*n-(m-x+1)*(n-y+1)+1; 6、反幻方 : 在 3*3 的方格中填入 1 至 9，使得横，竖，对角上的数字之和都不相等。下图给出的是一例。请编程找出所有可能的方案。1 2 3 4 5 8 6 9 7 图 一分析: (1) 深度优先搜索。用一个二维数组A来存储这个 3*3 的矩阵。(2) 用 x 表示行， y 表示列，搜索时应注意判断放入格子(x ，y) 的数码是否符合要求; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - -

28、 - - - - - - - （a）如果 y=3，就计算这一行的数码和，其值存放在Ax，4 中，如果该和己出现过，则回溯 ; （b）如果 x=3，则计算这一列的数码和，其值存放在A4，y 中，并进行判断是否需要回溯 ; （c）如果 x=3，y=1 还应计算从左下至右上的对角线的数码和; （d）如果 x=3，y=3 还应计算从左上至右下的对角线的数码和。为了提高搜索速度， 可以求出本质不同的解， 其余的解可以由这些本质不同的解通过旋转和翻转得到。为了产生非本质解，搜索时做如下规定: （a）要求 a1 ，1a3 ，1a1 ，3a1 ，2. 解：略7、将 M*N个 0 和 1 填入一个 M*N的矩阵

29、中，形成一个数表A，a11 a12 . a1n A=a21 a22 . a2n .,am1 am2 . amn 数表 A中第 i 行和数的和记为 ri(i=1，2，. ，m)，它们叫做 A的行和向量，数表 A第 j 列的数的和记为qj(j=1 ，2，. ，m)，它们叫做 A 的列和向量。现由文件读入数表 A的行和列，以及行和向量与列和向量， 编程求出满足条件的所的数表 A。分析: 本题是将例题一一般化，将若干个1 放入一个 M*N的方阵中，使得每行和每列上的 1 的个数满足所给出的要求。思路:(1) 应该容易判断，若 r1+r2+.+rnq1+q2+.+qm，则问题无解 ; (2)将放入 1

30、的个数看做是深度， 1 的位置记为 (x ，y) ，其中 x 代表行， y代表列，第一个 1 应从(1 ，1)开始试探 ; (3)往 k 行放入一个 1 时，若前一个 1 的位置是 (k ，y) ，则它的位置应在第k 行的 y+1 列至(m-本行还应放入1 的个数 +1)这个范围内进行试探 ; 若这一列上己放入 1 的个数小于 qy，则该格子内放入一个1，并记录下来 ; 否则换一个位置试探。Program lx9_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:a

31、rray1.max of integer; total:longint; procedure error; begin writeln(NO ANSWER!); writeln(Press any key to exit.。); repeat until keypressed; halt; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - procedure init; var f:text; fn:string;

32、i，j:integer; begin write(Filename:);readln(fn); assign(f，fn);reset(f); readln(f，m ，n);s1:=0;s2:=0; for i:=1 to m do begin read(f，ai);s1:=s1+ai;end; for i:=1 to n do begin read(f，bi);s2:=s2+bi;end; close(f); if s1s2 then error; fillchar(map，sizeof(map) ，0); fillchar(c，sizeof(c)，0); fillchar(d，sizeof(

33、d)，0); end; procedure print; var i，j:integer; begin inc(total);gotoxy(1，3); writeln(，total，); for i:=1 to m do begin for j:=1 to n do write(mapi，j:3); writeln; end; end; procedure try(x，y，t:integer); var i，j:integer; begin for i:=y+1 to n-(ax-cx)+1 do if (mapx，i=0) and (dibi) then begin mapx，i:=1;in

34、c(cx);inc(di); if t=s1 then print else if (x=m) then begin if cx=ax then try(x+1，0，t+1) else try(x，i ，t+1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - end; mapx，i:=0;dec(cx);dec(di); end; end; begin clrscr; init; try(1，0，1); if total

35、=0 then writeln(NO ANSWER!); end. 迷宫问题：（一） 问题分析1 迷宫的表示方法：迷宫可以用一个二维数组A（Y，X）表示，其中， Y表示行，X 表示列。数组中的元素由数字0 和 1 组成，当 A（Y，X）=1时表示墙；当 A（Y，X）=0时表示路。2 搜索方向的识别：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 对于迷宫中的任意一点A（Y，X） ，有四个搜索方向：向上A（Y-1，X） ；向下

36、 A （Y+1，X） ；向左 A（Y，X-1） ；向右 A（Y，X+1）3 搜索方向的表示方法：（0，1）表示向右；（-1，0）表示向上；（0。-1）表示向左；（1，0）表示向下4 向某个方向试探一步： 在搜索时一定要注意， 任何一点的坐标加上搜索方向的坐标增量后，都要判断是否超出了迷宫的边界。当不出界时，A（Y，X）=0表示该方向为通路。5 当从死胡同退出时，要将路堵死，可将其标记为2。6 在搜索中还要建立一个堆栈，将所走过的路记录下来， 后退时将退出的路从堆栈中弹出。这样保证了最终保存的是迷宫的一条出路。栈底元素为入口坐标， 栈顶元素为迷宫的出口坐标。（二） 产生式系统1 数据库。为了要存

37、储所走过的路，每个记录要有：行，列坐标，搜索方向三个数据，而且数据库应组成堆栈形式，并用DEP作为栈顶指针，同时表示搜索深度。2 产生规则。共有八条，可用数组DX 和 DY 表示方向增量：nx=x+dx(j); ny=y+dy(j) if (nx,ny)是通路 then (nx,ny)是新结点3 搜索策略。由于迷宫较大，为了防止溢出应采用非递归算法。（三） PASCAL 源程序Program labyrinth(output); uses crt; type node=record xx,yy:byte; r:byte; end; all=array0.11,0.11 of byte; con

38、st dx:array1.4 of integer=(0,1,0,-1); dy:array1.4 of integer=(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,

39、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,ny:integer; path:array0.300 of node; p:boolean; procedure wait; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - -

40、 - begin for k:=1 to 5000 do end; procedure display(a:all); var i,j:byte; begin for i:=0 to 11 do begin for j:=0 to 11 do write(ai,j); writeln; end; end; function check :boolean; begin nx:=x+dxj; ny:=y+dyj; if (nx11) or (ny11) then check:=false else if any,nx0 then check:=false else check:=true; end

41、; procedure backtrack; begin repeat dec(dep); if dep=0 then p:=true else begin ay,x:=2;gotoxy(x+1,y+1);write(chr(176);wait; x:=pathdep.xx; y:=pathdep.yy; j:=pathdep.r; end; until (dep=0) or (j=4 then backtrack; until p=true; until dep=0; readln; end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -