深度优先搜索.docx
《深度优先搜索.docx》由会员分享，可在线阅读，更多相关《深度优先搜索.docx（36页珍藏版）》请在冰点文库上搜索。
深度优先搜索
深度优先搜索
所谓"深度"是对产生问题的状态结点而言的，"深度优先"是一种控制结点扩展的策略，这种策略是优先扩展深度大的结点，把状态向纵深发展。
深度优先搜索也叫做DFS法（DepthFirstSearch）。
深度优先搜索的递归实现过程：
proceduredfs（i）;
forj:
=1tordo
if
if
子结点子结点
mr符合条件then产生的子结点
mr是目标结点then输出
mr入栈；
elsedfs（i+1）;
栈顶元素出栈（即删去mr）;
endif;
endfor;
[例1]骑士游历:
设有一个n*m的棋盘，在棋盘上任一点有一个中国象棋马.
马走的规则为:
1.马走日字
2.马只能向右走。
当N,M输入之后,找出一条从左下角到右上角的路径。
例如:
输入N=4,M=4，
输出:
路径的格式:
（1,1）->（2,3）->（4,4），若不存在路径,则输出"no"
算法分析：
我们以4×4的棋盘为例进行分析，用树形结构表示马走的所有过程，求从起点到终点的路径,实际上就是从根结点开始深度优先搜索这棵树。
马从（1，1）开始，按深度优先搜索法，走一步到达（2，3），判断是否到达终点，若没有，则继续往前走，再走一步到达（4，4），然后判断是否到达终点，若到达则退出，搜索过程结束。
为了减少搜索次数，在马走的过程中，判断下一步所走的位置是否在棋盘上，如果不在棋盘上，则另选一条路径再走。
程序如下：
const
dx:
array[1..4]ofinteger=（2,2,1,1）;
dy:
array[1..4]ofinteger=（1,-1,2,-2）;
type
map=record
x,y:
integer;
end;
var
i,n,m:
integer;
a:
array[0..50]ofmap;
proceduredfs（i:
integer）;
varj,k:
integer;
begin
forj:
=1to4do
if（a[i-1].x+dx[j]>0）and（a[i-1].x+dx[j]<=n）
and（a[i-1].y+dy[j]>0）and（a[i-1].y+dy[j]<=n）then{判断是否在棋盘上
begin
a[i].x:
=a[i-1].x+dx[j];
a[i].y:
=a[i-1].y+dy[j];{入栈}
if（a[i].x=n）and（a[i].y=m）then
}
begin
write（'（',1,',',1,'）'）;
fork:
=2toidowrite（'->（',a[k].x,',',a[k].y,'）'）;
halt;{输出结果并退出程序}
end;
dfs（i+1）;{搜索下一步}
a[i].x:
=0;a[i].y:
=0;{出栈}
end;
end;
begin
a[1].x:
=1;a[1].y:
=1;
readln（n,m）;
dfs
（2）;
writeln（'no'）;
end.
从上面的例子我们可以看出，深度优先搜索算法有两个特点：
1、己产生的结点按深度排序，深度大的结点先得到扩展，即先产生它的子结点。
2、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。
对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和编程技巧上又都不相同，甚至会有很大的差别。
我们再看看另一个例子。
[例2]选数（存盘名：
NOIP2002pj）
[问题描述]:
已知n个整数x1,x2,,,xn，以及一个整数k（k＜n）。
从n个整
数中任选k个整数相加，可分别得到一系列的和。
例如当n=4，k＝3，4个整
数分别为3，7，12，19时，可得全部的组合与它们的和为：
3＋7＋12=223
＋7＋19＝297＋12＋19＝383＋12＋19＝34。
现在，要求你计算出和为
素数共有多少种。
例如上例，只有一种的和为素数：
3＋7＋19＝29。
[输入]：
键盘输入，格式为：
n,k（1<=n<=20，k＜n）
x1,x2，,,xn（1<=xi<=5000000）
[输出]：
屏幕输出，格式为：
一个整数（满足条件的种数）。
[输入输出样例]:
输入：
43
371219
输出：
1
算法分析：
本题是求从n个数中选k个数的组合，并使其和为素数。
求解此题时，先用深度优先搜索法生成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:
array[1..20]ofLongint;
procedureprime（s:
longint）;{判断K个数的和是否为素数}var
i:
integer;
begin
i:
=2;
while（sqr（i）<=s）and（smodi<>0）doinc（i）;
ifsqr（i）>stheninc（ans）{若为素数则总数加1}end;
proceduredfs（i,m:
byte）;{搜索第i个数，}
var
j:
byte;{j表示第i个数的位置
begin
forj:
=mton-k+ido{枚举第i个数}
begin
inc（s,a[j]）;{入栈}
ifi=kthenprime（s）
elsedfs（i+1,j+1）;{继续搜第i+1个数}
dec（s,a[j]）{出栈}
end
end;
begin
readln（n,k）;
fori:
=1tondoread（a[i]）;
ans:
=0;s:
=0;
dfs（1,1）;
writeln（ans）;
end.
从上面的两个例子我们可以看出，用递归实现深度优先搜索比非递归更加方便。
在使用深度搜索法解题时，搜索的效率并不高，所以要重视对算法的优化，尽可能的减少搜索范围，提高程序的速度。
[例3]
设有一个4*4的棋盘，用四个棋子布到格子中，要求满足以下条件:
（1）任意两个棋子不在同一行和同一列上;
（2）任意两个棋子不在同一条对角线上。
试问有多少种棋局，编程把它们全部打印出来。
解：
PASCAL程序：
Programlt9_1_1;
usescrt;
constn=4;
vara:
array[1..n]ofinteger;
total:
integer;
functionpass（x，y:
integer）:
boolean;
vari，j:
integer;
begin
pass:
=true;
fori:
=1tox-1do
if（a[i]=y）or（abs（i-x）=abs（a[i]-y））then
beginpass:
=false;exit;end;
end;
procedureprint;
vari，j:
integer;
begin
inc（total）;
writeln（'['，total，']'）;
fori:
=1tondo
begin
forj:
=1tondo
ifj=a[i]thenwrite（'O'）
elsewrite（'*'）;
writeln;
end;
end;
proceduretry（k:
integer）;
vari:
integer;
begin
fori:
=1tondo
ifpass（k，i）then
begin
a[k]:
=i;
ifk=nthenprint
elsetry（k+1）;
a[k]:
=0;
end;
end;
begin
clrscr;
fillchar（a，sizeof（a），0）;
total:
=0;
try
（1）;
end.
分析:
这里要求找出所有满足条件的棋局，因此需要穷举所有可能的布子方案，可以按如下方法递归产生:
令D为深度，与棋盘的行相对应，初始时D=1;Proceduretry（d:
integer）;
begin
fori:
=1to4do
if第i个格子满足条件then
begin
往第d行第i列的格子放入一枚棋子;
如果d=4则得一方案，打印
否则试探下一行，即try（d+1）;
恢复第d行第i列的格子递归前的状态;
end;
end;
这种方法是某一行放入棋子后，再试探下一行，将问题向纵深发展;若本行试探完毕则回到上一行换另一种方案。
这样必定可穷举完所有可能的状态。
从本题可以看出，前面所说的递归回溯法即体现了深度优先搜索的思想。
上面对深度优先算法的描述就是回溯法常见的模式。
[例4]
在6*6的方格中，放入24个相同的小球，每格放一个，要求每行每列都有
4个小球（不考虑对角线），编程输出所有方案。
解:
Pascal程序:
Programlx9_1_2;
usescrt;
constn=6;
varmap:
array[1..n，1..n]ofboolean;
a:
array[1..n]ofinteger;
total:
longint;
procedureprint;
vari，j:
integer;
begin
inc（total）;gotoxy（1，3）;
writeln（'['，total，']'）;
fori:
=1tondo
begin
forj:
=1tondo
ifmap[i，j]thenwrite（'*'）
elsewrite（'O'）;
writeln;
end;
end;
proceduretry（k:
integer）;
vari，j:
integer;
begin
fori:
=1ton-1do
ifa[i]<2thenbegin
map[k，i]:
=true;
inc（a[i]）;
forj:
=i+1tondo
ifa[j]<2thenbegin
map[k，j]:
=true;
inc（a[j]）;
ifk=nthenprint
elsetry（k+1）;
map[k，j]:
=false;
dec（a[j]）;
end;
map[k，i]:
=false;
dec（a[i]）;
end;
end;
begin
clrscr;
fillchar（map，sizeof（map），false）;
fillchar（a，sizeof（a），0）;
try
（1）;
end.
分析:
本题实际上是例一的变形;
（1）把枚举每行每列四个小球转化成为每行每列填入2个空格;
（2）用两重循环实现往一行中放入两个空格;
（3）用数组B记录搜索过程中每列上空格的个数;
（4）本题利用深度搜索求解时要注意及时回溯，以提高效率，同时要注意退出递归时全局变量的正确恢复。
[例5]
跳马问题:
在半张中国象棋盘上，有一匹马自左下角往右上角跳，今规定只许往右跳，不许往左跳，图（A）给出的就是一种跳行路线。
编程计算共有多少种不同的跳行路线，并将路线打印出来。
解：
PASCAL程序：
Programlt9_1_2;
usescrt;
constd:
array[1..4
，1..2]ofshortint=（（2
，1），（1，2），（-1
，2），（-2
，
1））;
vara:
array[1..10
，1..2]ofshortint;
total:
integer;
functionpass（x，y，i:
integer）:
boolean;
begin
if（x+d[i
，1]<0）or（x+d[i
，1]>4）or（y+d[i
，2]>8）
thenpass:
=falseelsepass:
=true;
end;
procedureprint（k:
integer）;
vari:
integer;
begin
inc（total）;
write（'['
，total，']:
（0
，0）'）;
fori:
=1tokdo
write（'->（'
，a[i，1]，'，'，a[i
，2]，'）'）;
writeln;
end;
proceduretry（x，y，k:
integer）;
vari:
integer;
begin
fori:
=1to4do
ifpass（x，y，i）then
begin
a[k，1]:
=x+d[i，1];a[k，2]:
=y+d[i，2];
if（a[k，1]=4）and（a[k，2]=8）thenprint（k）
elsetry（a[k，1]，a[k，2]，k+1）;
end;
end;
begin
clrscr;
total:
=0;
try（0，0，1）;writeln（'Pressanykeytoexit..repeatuntilkeypressed;end.
。
'）;
分析:
（1）这里可以把深度d定为马跳行的步数，马的位置可以用它所在的行与列
表示因此初始时马的位置是（0，0）;
（2）位置在（x，y）上的马可能四种跳行的方向，如图（B），这四种方向，可
以按x，y的增量分别记为（2，1），（1，2），（-1，2），（-2，1）
（3）一种可行的跳法是指落下的位置应在棋盘中。
深度优先搜索的非递归算法
programDFS（dep）;
dep:
=0;
repeat
dep:
=dep+1;
j:
=j+1;
ifmr符合条件then
产生子结点mr并将其记录
if子结点是目标then输出并出栈
elsep:
=true;
else
ifj>maxjthen回溯elsep:
=false;
endif;
untilp=true;
untildep=0;
其中回溯过程如下：
procedurebacktracking;
dep:
=dep-1;
ifdep>0then取回栈顶元素
elsep:
=true;
练习一:
1、有一括号列S由N个左括号和N个右括号构成，现定义好括号列如下:
（1）若A是好括号列，则（A）也是;
（2）若A和B是好括号列，则AB也是好的。
例如:
（（）（（）））是好的，而（（）））（（）则不是，现由键盘输入N，求满足条件的所的好括号列，并打印出来。
解:
Pacal程序:
Programlx9_1_1;
usescrt;
varn:
integer;
total:
longint;
proceduretry（x，y:
integer;s:
string）;
vari:
integer;
begin
if（x=n）and（y=n）thenbegin
inc（total）;writeln（'['，total
end
elsebegin
ifxifyend;
end;
，']'
，s）;
begin
clrscr;
write（'N='）;readln（n）;
total:
=0;try（0，0，''）;
end.
分析:
从好括号列的定义可知，所谓的"好括号列"就是我们在表达式里所说的正
确匹配的括号列，其特点是:
从任意的一个位置之前的右括号的个数不能超过左
括号的个数。
由这个特点，可以构造一个产生好括号列的方法:
用x，y记录某一状态中左右括号的个数;若左括号的个数小于N（即x
2、排列组合问题：
从数码1-9中任选N个不同的数作不重复的排列（或组合），求出所有排列（或组合）的方案及总数。
3、填数游戏一:
以下列方式向5*5的矩阵中填入数字。
设数字i（1<=i<=25）己被置于座标位置（x，y），则数字i+1的座标位置应为（z，w），（z，w）可根据下列关系由（x，y）算出。
（1）（z，w）=（x±3，y）
（2）（z，w）=（x，y±3）
（3）（z，w）=（x±2，y±2）
例如数字1的起始位置座标被定为（2，2），则数字2的可能位置座标是：
（5，
2），（2，5），或（4，4）。
编写一个程序，当数字1被指定于某一起始位置时，列举其它24个数字应在的位置，列举出该条件下的所有可有的方案。
解:
同例二类似，只不过方向增量变为（3，0），（-3，0），（0，3），（0，-3），（2，
2），（2，-2），（-2，2），（-2，-2）。
Pascal程序:
Programlx9_1_3;
usescrt;
constn=5;
d:
array[1..8
，1..2]ofshortint=（（3
，0），（-3，0），（0，3），（0，-3），
（2
，2），（2，-2），（-2，2），（-2，
-2））;
varx0，y0:
byte;
a:
array[1..n
，1..n]ofbyte;
total:
longint;
procedureprint;
vari，j:
integer;
begin
inc（total）;
gotoxy（1，3）;
writeln（'['
，total，']'）;
fori:
=1tondo
begin
forj:
=1tondo
write（a[i
，j]:
3）;
writeln;
end;
end;
proceduretry（x
，y，k:
byte）;
vari，x1，y1:
integer;
begin
fori:
=1to8do
begin
x1:
=x+d[i，1];y1:
=y+d[i
，2];
if（x1>0）and（y1>0）and（x1<=n）
and（y1<=n）and（a[x1
，y1]=0）then
begin
a[x1，y1]:
=k;
ifk=n*nthenprint
elsetry（x1，y1，k+1）;
a[x1，y1]:
=0;
end;
end;
end;
begin
clrscr;
write（'x0，y0='）;readln（x0，y0）;
fillchar（a，sizeof（a），0）;
total:
=0;a[x0，y0]:
=1;
try（x0，y0，2）;
writeln（'Total='，total）;
writeln（'Pressanykeytoexit..。
'）;
repeatuntilkeypressed;
end.
5、填数游戏二。
有一个M*N的矩阵，要求将1至M*N的自然数填入矩阵中，满足下列条件:
（1）同一行中，右边的数字比左边的数字大;
（2）同一列中，下面的数字比上面的数字大。
打印所有的填法，并统计总数。
解:
Pascal程序:
$Q-，R-，S-
Programlx9_1_4;
usescrt;
constm=3;n=6;
vara:
array[0..m，0..n]ofinteger;
used:
array[1..m*n]ofboolean;
total:
longint;
procedureprint;
vari，j:
integer;
begin
inc（total）;gotoxy（1
writeln（'['，total
，3）;
，']'）;
fori:
=1tomdo
begin
forj:
=1tondo
write（a[i，j]:
3）;
writeln;
end;
end;
proceduretry（x，y:
integer）;
vari:
integer;
begin
fori:
=x*ytom*n-（m-x+1）*（n-y+1）+1do
ifnotused[i]and（i>a[x-1，y]）and（i>a[x
begin
a[x，y]:
=i;used[i]:
=true;
ifi=m*n-1thenprint
elsebegin
ify=nthentry（x+1，1）
elsetry（x，y+1）;
end;
used[i]:
=false;
end;
，y-1]）then
end;
begin
clrscr;
fillchar（used
，sizeof（used）
，false）;
升级会员 