深度优先搜索

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

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

3、条路径再走。1.4of in teger=(2,2,1,1); 仁4of in teger=(1,-1,2,-2);程序如下：con stdx:ady:afrtypemap=recordx,y:i nteger; end;vari,n ,m:i nteger;a:array0.50of map;procedure dfs(i:i nteger);var j,k:i nteger;begi nfor j:=1 to 4 doif(ai-1.x+dxj>0)a nd(ai-1.x+dxjv=n)an d(ai-1.y+dyj>0)a nd(ai-1.y+dyjv=n) the n判断是

4、否在棋盘上beginai.x:=ai-1.x+dxj;ai.y:=ai-1.y+dyj;入栈if (ai.x=n)an d(ai.y=m)the nbeginwrite('(',1,',',1,')');for k:=2 to i do write('->(',ak.x,',',ak.y,')');halt;输出结果并退出程序end;dfs(i+1);搜索下一步ai.x:=0;ai.y:=0;出栈end;end;begi na1.x:=1;a1.y:=1;readl n(n ,m);dfs(2

5、);write In (' no');end.从上面的例子我们可以看出，深度优先搜索算法有两个特点：1、 己产生的结点按深度排序，深度大的结点先得到扩展，即先产生它的子结点。2、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的 工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和编程技巧上又都不相同，甚至会有很大的差别。我们再看看另一个例子。k(k v n)。从 n个整 n=4 , k = 3, 4 个整3 + 7 + 12=223例2选数(存盘名： NOIP2OO2pj )问题描述

6、:已知n 个整数x1,x2,xn，以及一个整数数中任选k个整数相加，可分别得到一系列的和。例如当 数分别为3 , 7, 12, 19时，可得全部的组合与它们的和为:+ 7 + 19 = 297 + 12 + 19 = 383 + 12 + 19 = 34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3 + 7 + 19 = 29。输入:键盘输入，格式为：n , k (1<=n<=20, kv n)x1,x2 , ,xn (1<=xi<=5000000 )输出:屏幕输出，格式为：一个整数(满足条件的种数)。输入输出样例:输入：4 33 7 12 1

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

8、 vari:i nteger;begi ni:=2;while (sqr(i)<=s)a nd(s mod i<>0) do in c(i);if sqr(i)>s then in c(a ns) 若为素数则总数加 1 end;procedure dfs(i,m:byte);搜索第 i 个数，varj:byte;j 表示第i个数的位置begi nfor j:=m to n-k+i do枚举第 i 个数begininc(s,aj);入栈if i=k then prime(s)else dfs(i+1,j+1);继续搜第 i+1 个数dec(s,aj) 出栈endend;b

9、egi nreadl n(n ,k);for i:=1 to n do read(ai);an s:=0; s:=0;dfs(1,1);writel n(a ns);end.从上面的两个例子我们可以看出，用递归实现深度优先搜索比非递归更加方便。 在使用深度搜索法解题时，搜索的效率并不高，所以要重视对算法的优化,可能的减少搜索范围，提高程序的速度。例3设有一个4*4的棋盘，用四个棋子布到格子中，要求满足以下条件：(1) 任意两个棋子不在同一行和同一列上；(2) 任意两个棋子不在同一条对角线上。 试问有多少种棋局，编程把它们全部打印出来。解：PASCAL程序：Program It9_1_1;use

10、s crt;const n=4;var a:array1. n of in teger;total:i nteger;function pass(x，y:integer):boolean;var i ，j:integer;beginpass:=true;for i:=1 to x-1 doif (ai=y) or (abs(i-x)=abs(ai-y) the n beg in pass:=false;exit;e nd;end;procedure print;var i ，j:integer;beginin c(total);writeln(''，total ，'&#

11、39;);for i:=1 to n dobeginfor j:=1 to n doif j=ai then write('O ')else write('* ');write In;end;end;procedure try(k:i nteger);var i:i nteger;beginfor i:=1 to n doif pass(k , i) thenbegi nak:=i;if k=n the n printelse try(k+1);ak:=0;end;end;begi nclrscr;fillchar(a , sizeof(a) , 0);tota

12、l:=0;try(1);end.分析:这里要求找出所有满足条件的棋局，因此需要穷举所有可能的布子 方案，可以按如下方法递归产生:令D为深度，与棋盘的行相对应，初始时D=1;Procedure try(d:i nteger);beginfor i:=1 to 4 doif 第i个格子满足条件thenbegin往第d行第i列的格子放入一枚棋子；如果d=4则得一方案，打印否则试探下一行，即try(d+1);恢复第d行第i列的格子递归前的状态；end;end;这种方法是某一行放入棋子后，再试探下一行，将问题向纵深发展；若本行试探完毕则回到上一行换另一种方案。这样必定可穷举完所有可能的状态。从本题可以看

13、出，前面所说的递归回溯法即体现了深度优先搜索的思想。上面对深度优先算法的描述就是回溯法常见的模式。例4在6*6的方格中，放入24个相同的小球，每格放一个，要求每行每列都有 4个小球(不考虑对角线)，编程输出所有方案。解:Pascal程序: Program Ix9_1_2;uses crt;const n=6;var map:array仁n, 仁n of boolean;a:array仁 n of in teger;total:l ongint;procedure print;var i , j:integer;beginin c(total);gotoxy(1, 3);writeln('

14、;', total ,'');for i:=1 to n dobeginfor j:=1 to n doif mapi, j then write('* ')else write('O ');write In;end;end;procedure try(k:i nteger);var i , j:integer;beginfor i:=1 to n-1 doif ai<2 the n begi nmapk , i:=true;inc(ai);for j:=i+1 to n doif aj<2 the n beg inmapk,

15、 j:=true;inc(aj);if k=n the n printelse try(k+1);mapk, j:=false;dec(aj);end;mapk , i:=false;dec(ai);end;end;begi nclrscr;fillchar(map , sizeof(map) , false);fillchar(a , sizeof(a) , 0);try(1);end.分析:本题实际上是例一的变形；(1) 把枚举每行每列四个小球转化成为每行每列填入2个空格；(2) 用两重循环实现往一行中放入两个空格；(3) 用数组B记录搜索过程中每列上空格的个数；(4) 本题利用深度搜索求

16、解时要注意及时回溯，以提高效率， 同时要注意退出递归时全局变量的正确恢复。例5跳马问题:在半张中国象棋盘上，有一匹马自左下角往右上角跳，今规定只 许往右跳，不许往左跳，图(A)给出的就是一种跳行路线。编程计算共有多少种 不同的跳行路线，并将路线打印出来。解：PASCAL程序：Program It9_1_2;uses crt;const d:array1.4 ， 1.2 of shortint=(2， 1)，(1， 2)，(-1 ， 2)， (-2，1);var a:array1.10， 1.2 of shorti nt;total:i nteger;function pass(x，y， i:i

17、nteger):boolean;beginif (x+di ，1<0) or (x+di ，1>4) or (y+di ，2>8)the n pass:=false else pass:=true;end;procedure prin t(k:i nteger);var i:i nteger;beginin c(total);write(''，total ， ' : (0， 0)');for i:=1 to k dowrite('->('，ai，1，ai，2，')');write In;end;proced

18、ure try(x , y, k:integer); var i:i nteger;beginfor i:=1 to 4 doif pass(x , y, i) thenbegi nak, 1:=x+di, 1;ak, 2:=y+di, 2;if (ak, 1=4) and (ak , 2=8) then prin t(k)else try(ak,1 , ak ,2 , k+1);end;end;begi nclrscr;total:=0;');try(0 , 0 , 1); writelnPress any key to exit. repeat un til keypressed;

19、 end.分析:（1）这里可以把深度d定为马跳行的步数,马的位置可以用它所在的行与列表示因此初始时马的位置是（0 , 0）;（2）位置在（x，y）上的马可能四种跳行的方向，如图 （B），这四种方向，可 以按 x，y 的增量分别记为（2，1），（1，2），（-1，2），（-2，1）（3）一种可行的跳法是指落下的位置应在棋盘中。深度优先搜索的非递归算法program DFS(dep); dep:=0;repeatdep:=dep+1;j:=j+1;if mr符合条件then产生子结点mr并将其记录if子结点是目标the n 输出并出栈else p:=true;elseif j>maxj th

20、en回溯 else p:=false;en dif;un til p=true;un til dep=0;其中回溯过程如下： procedure backtrack ing;dep:=dep-1;if dep>0 then取回栈顶元素else p:=true;练习一:1、有一括号列S由N个左括号和N个右括号构成，现定义好括号列如下：(1) 若A是好括号列，则(A)也是；(2) 若A和B是好括号列，则 AB也是好的。例如：()()是好的，而()()则不是，现由键盘输入N，求满足条件的所的好括 号列，并打印出来。解:Pacal程序:Program Ix9_1_1;uses crt;var n

21、:i nteger;total:l ongint;procedure try(x ，y:integer;s:string); var i:i nteger;begin，''，s);if (x=n) and (y=n) the n begi ninc(total);writeln(''， totalendelse beg inif x<n then try(x+1，y，s+'(');if y<x then try(x，y+1，s+')');end;end;begi nclrscr;write('N=');

22、readl n(n); total:=0;try(0 ，0，''); end.分析:从好括号列的定义可知，所谓的 "好括号列"就是我们在表达式里所说的正 确匹配的括号列，其特点是 ：从任意的一个位置之前的右括号的个数不能超过左括号的个数。 由这个特点， 可以构造一个产生好括号列的方法 :用x，y记录某一 状态中左右括号的个数；若左括号的个数小于N(即x<N)，则可加入一个左括号；若 右括号的个数小于左括号的个数， 则可加入一个右括号， 如此重复操作， 直至产 生一个好括号列。2、排列组合问题： 从数码1-9中任选N个不同的数作不重复的排列(或组合) 求

23、出所有排列(或组合)的方案及总数。3、填数游戏一:以下列方式向5*5的矩阵中填入数字。设数字i（1v=i<=25）己被置 于座标位置（x , y），则数字i+1的座标位置应为（z , w）, （z , w）可根据下列关系由 （x， y）算出。（1） （z ，w）=（x ± 3，y）（z ，w）=（x，y ± 3）（z ，w）=（x ± 2，y ± 2）例如数字1的起始位置座标被定为（2，2），则数字2的可能位置座标是：（5，2），（2，5），或（4，4）。编写一个程序，当数字1被指定于某一起始位置时，列 举其它24个数字应在的位置，列举出该条件下的

24、所有可有的方案。解:同例二类似，只不过方向增量变为（3，0），（-3，0），（0，3），（0，-3），（2，2），（2，-2），（-2，2），（-2，-2）。Pascal 程序:Program Ix9_1_3;uses crt; const n=5;d:array1.8， 1.2 of short in t=（3，0），（-3，0），（0，3），（0，-3），（2 ，2），（2，-2），（-2，2），（-2， -2）;var x0 ， y0:byte;a:array仁 n， 1. .n of byte;total:l ongint;procedure print;var i ，j:intege

25、r;beginin c（total）;gotoxy（1 ， 3）;writeln（''，total，''）;for i:=1 to n dobeginfor j:=1 to n dowrite（ai，j:3）;write In;end;end;procedure try（x ，y， k:byte）;var i ，x1，y1:integer;beginfor i:=1 to 8 dobeginx1:=x+di，1;y1:=y+di， 2;if （x1>0） and （y1>0） and （x1<=n）and （y1<=n） and （ax1

26、， y1=0） thenbeginax1, y1:=k;if k=n*n then printelse try(x1, y1 , k+1);ax1, y1:=0;end;end;end;begi nclrscr;write('xO , y0=');readln(xO , y0); fillchar(a , sizeof(a), 0);total:=0;ax0 , y0:=1;try(x0 , y0, 2);writeln('Total=', total);write In ('Press any key to exit.。');repeat un

27、 til keypressed;end.5、填数游戏二。有一个 M*N的矩阵，要求将1至M*N的自然数填入矩阵中，满 足下列条件:(1) 同一行中，右边的数字比左边的数字大;(2) 同一列中，下面的数字比上面的数字大。 打印所有的填法，并统计总数。解:Pascal程序:$Q-， R-， S-Program Ix9_1_4;uses crt;const m=3;n=6;var a:array0.m ，0.n of integer;used:array1.m* n of boolea n;total:l ongint;procedure print;var i ，j:integer;beginin

28、c(total);gotoxy(1， 3);writeln(''，total ，'');for i:=1 to m dobeginfor j:=1 to n dowrite(ai，j：3);write In;end;end;procedure try(x , y:integer);var i:i nteger;beginfor i:=x*y to m*n-( m-x+1)* (n- y+1)+1 doif not usedi a nd (i>ax-1, y) and (i>ax , y-1) thenbegi nax, y:=i;usedi:=tru

29、e;if i=m*n-1 then printelse beg inif y=n the n try(x+1, 1)else try(x, y+1);end;usedi:=false;end;end;begi nclrscr;fillchar(used , sizeof(used) , false);fillchar(a , sizeof(a) , 0);a1, 1:=1;am, n:=m*n;used1:=true;usedm* n:=true;try(1 , 2);writeln('Total=', total);end.分析:本题可以将放入格子中的数字的个数作为深度，先往

30、格子(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)所要填入数，则有：x*yv=A<=m*n-(m-x+1)*(n-y+1)+1;6、反幻方:在3*3的方格中填入1至9,使得横，竖，对角上的数字之和都不相

31、 等。下图给出的是一例。请编程找出所有可能的方案。1213458697分析:(1) 深度优先搜索。用一个二维数组A来存储这个3*3的矩阵。(2) 用x表示行，y表示列，搜索时应注意判断放入格子(x , y)的数码是否符合要求；(a) 如果y=3，就计算这一行的数码和，其值存放在Ax， 4中，如果该和 己出现过，贝U回溯；(b) 如果x=3，则计算这一列的数码和，其值存放在A4 , y中，并进行判断 是否需要回溯；(c) 如果x=3 , y=1还应计算从左下至右上的对角线的数码和；d)如果x=3 , y=3还应计算从左上至右下的对角线的数码和。为了提高搜索速度，可以求出本质不同的解，其余的解可以

32、由这些本质不同的解通过旋转和翻转得到。为了产生非本质解，搜索时做如下规定:(a) 要求 a1 , 1<a3 , 1<a1 , 3<a3 , 3;(b) 要求 a2 , 1>a1 , 2.解：略7、将M*N个0和1填入一个M*N的矩阵中，形成一个数表A,all a12 . a1nA= a21 a22 . a2nam1 am2 . amn数表A中第i行和数的和记为ri(i=1 , 2, . , m)，它们叫做A的行和向量，数表 A第j列的数的和记为qj(j=1 , 2, . , m)，它们叫做A的列和向量。现由文件读入 数表A的行和列，以及行和向量与列和向量，编程求出满足条

33、件的所的数表 A。分析：本题是将例题般化，将若干个1放入一个M*N的方阵中，使得每行和每列上的1的个数满足所给出的要求。思路:(1)应该容易判断，若 r1+r2+.+rnv>q1+q2+.+qm，则问题无解；(2) 将放入1的个数看做是深度，1的位置记为(x , y)，其中x代表行，y 代表列，第一个1应从(1 , 1)开始试探；(3) 往k行放入一个1时，若前一个1的位置是(k , y),则它的位置应在第 k行的y+1列至(m-本行还应放入1的个数+1)这个范围内进行试探；若这一列上 己放入1的个数小于qy，则该格子内放入一个1，并记录下来；否则换一个位置试 探。Program Ix9

34、_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:array1.max of integer;total:l ongint;procedure error;beginwrite In ('NO ANSWER!');write In ('Press any key to exit.。');repeat un til keypressed;halt;end;procedure in it;var f:tex t;fn:stri n

35、g;i , j:integer;beginwrite('File name:');readl n(fn);assign(f, fn);reset(f);readln(f, m, n);s1:=0;s2:=0;for i:=1 to m dobeg in read(f, ai);s1:=s1+ai;e nd;for i:=1 to n dobeg in read(f, bi);s2:=s2+bi;e nd;close(f);if s1<>s2 then error;fillchar(map , sizeof(map) , 0);fillchar(c, sizeof(c

36、), 0);fillchar(d, sizeof(d), 0);end;procedure print;var i , j:integer;begininc(total);gotoxy(1, 3);writeln('', total ,'');for i:=1 to m dobeginfor j:=1 to n dowrite(mapi, j:3);write In;end;end;procedure try(x , y, t:integer);var i , j:integer;beginfor i:=y+1 to n-(ax-cx)+1 doif (mapx

37、 , i=0) and (di<bi) thenbegi nmapx, i:=1;inc(cx);inc(di);if t=s1 then printelse if (x<=m) the n begi nif cx=ax the n try(x+11 else try(x.end;,0, t+1),i ,t+1);,i:=O;dec(cx);dec(di);mapx end;(一) 问题分析1. 迷宫的表示方法：迷宫可以用一个二维数组A (Y, X)表示，其中，Y表示行，X表示列。数组中的元素由数字 0和1组成，当A(丫，X)=1时表示墙；当A( 丫，X)=0时表示路。2. 搜索方

38、向的识别：对于迷宫中的任意一点A ( 丫，X)，有四个搜索方向：向上 A ( Y-1，X)；向下A(Y+1，X);向左 A (丫，X-1);向右 A (丫，X+1 )3. 搜索方向的表示方法：(0， 1)表示向右；(-1 ， 0)表示向上；(0。-1 ) 表示向左；(1，0 )表示向下4. 向某个方向试探一步：在搜索时一定要注意，任何一点的坐标加上搜索方向的坐标增量后，都要判断是否超出了迷宫的边界。当不出界时，A (丫， X) =0表示该方向为通路。5. 当从死胡同退出时，要将路堵死，可将其标记为2。6. 在搜索中还要建立一个堆栈，将所走过的路记录下来，后退时将退出的路从堆栈中弹出。这样保证了

39、最终保存的是迷宫的一条出路。栈底元素为入口坐标，栈顶元素为迷宫的出口坐标。(二) 产生式系统1. 数据库。为了要存储所走过的路，每个记录要有：行，列坐标，搜索方向三个数据，而且数据库应组成堆栈形式，并用DEP作为栈顶指针，同时表示搜索深度。2. 产生规则。共有八条，可用数组DX和Dy表示方向增量： nx=x+dx(j);n y=y+dy(j)if (nx, ny)是通路then (nx, ny)是新结点3. 搜索策略。由于迷宫较大，为了防止溢出应米用非递归算法。(三) PASCAL源程序Program labyri nth(output);uses crt;type no de=recordx

40、x,yy:byte;r:byte;end;all=array0.11,0.11 of byte;const dx:array1.4 of integer=(0,1,0,-1); dy:array1.4of in teger=(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,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,n y:i nteger;path:array0.300 of node;p:boolea n;procedure wai