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,')');
for j:=2 to i do write('->(',a[j].x,',',a[j].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、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的
工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。 对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和编程技巧上又都不相同，甚至会有很大的差别。我们再看看另一个例子。 题二 选数（存盘名：NOIP2002pj）
[问题描述]:已知 n 个整数 x1,x2,?,xn，以及一个整数 k(k＜n)。从n 个整数
中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29。 [输入]：键盘输入，格式为： n , k (1<=n<=20，k＜n)
x1,x2，?,xn （1<=xi<=5000000） [输出]：屏幕输出，格式为：
一个整数（满足条件的种数）。 [输入输出样例]: 输入：4 3 3 7 12 19 输出：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] of Longint;
procedure prime(s:longint);{判断K个数的和是否为素数} var
i:integer; begin
i:=2;
while (sqr(i)<=s)and(s mod i<>0) 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,a[j]);{入栈} if i=k then prime(s)
else dfs(i+1,j+1);{继续搜第i+1个数} dec(s,a[j]){出栈} end end; begin
readln(n,k);
for i:=1 to n do read(a[i]); ans:=0; s:=0; dfs(1,1);
writeln(ans);
end.
从上面的两个例子我们可以看出，用递归实现深度优先搜索比非递归更加方便。
在使用深度搜索法解题时，搜索的效率并不高，所以要重视对算法的优化，尽可能的减少搜索范围，提高程序的速度。
在下一篇中将继续介绍另一种搜索方法——广度优先搜索法。
算法在信息学奥赛中的应用（搜索法二） 在深度优先搜索算法中，深度越大的结点越先得到扩展，若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。
广度优先搜索基本算法： program bfs;
初始化；建立队列data;
设队列首指针closed:=0;队列尾指针open:=1; repeat
closed 增1，取出closed所指结点进行扩展； for i:=1 to r do begin if 子结点符合条件then begin
open增1，并把新结点存入数据库队尾；
if新结点与原有结点有重复 then 删于该结点(open减1) else if 新结点即目标 then 输出并退出 ;
end{if};
end{for};
until closed>=open;{队列为空}
使用广度优先搜索时，离根结点最近的结点先扩展，所以广度优先搜索法比较适合求步数最少的解，由于深度优先使用了标志法，使得存储空间大大减少，而广度优先要保留所有搜索过的节点，随着搜索程度的加深，所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间，如下面的例子。
广度优先算法应用
例 字串变换（NOIP2002tg）
[问题描述]:已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）: A1$ -> B1$ A2$ -> B2$ 规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。例如：A$＝'abcd' B$＝'xyz' 变换规则为：‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换，使得 A$ 变换为B$。 [输入]:键盘输人文件名。文件格式如下： A$ B$
A1$ B1$ \\
A2$ B2$ |-> 变换规则 ... ... /
所有字符串长度的上限为 20。 [输出]:输出至屏幕。格式如下： 若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出\[输入输出样例] b.in: abcd xyz abc xu ud y y yz 屏幕显示：3
算法分析：此题是求变换的最少步数，很显然可以使用广度优先搜索法，如果直接从初状态搜到目标状态，最坏情况下存储的结点数超过6的10次方幂，搜索空间过大，因此我们考虑使双向搜索，同时从初始状态和目标状态向中间状态搜索，当相遇时搜索结束。采用双向搜索，存储的结点数还有可能超限，我们在前向搜索队列中存储5步内变换的结点，在后向搜索队列中，由于第5步产生的结点只
是用来与前向队列中的结点比较，所以可以不存储在队列中，后向搜索队列只需存储4步内的结点，这样就解决了存储空间问题。
为了使用方便，在程序设计中用一个数组a[1..max]存储两个队列，前向搜索队列为a[1..mid]，后向搜索队列为a[mid..max]，用st存储搜索方向，st=0表示前向搜索，st=1表示后向搜索，用op[st]和cl[st]分别表示队列尾指针和首指针，用be表示队列起始位置，循环产生每一个结点，若在10内无解退出循环，若在10内找到解则输出解并退出程序。
源程序：
const mid=12000;max=16000; type
node=record s:string;x:byte;end; var
i,mark:integer;
a:array [1..max]of ^node;
x:array[0..6,0..1]of string[20]; d,fil:string;
op,cl:array [0..1] of integer; procedure Init;{读取数据，初始化} var f:text;t:string; begin
readln(fil);
assign(f,fil);reset(f);i:=0; while not eof(f) do begin readln(f,t);
x[i,0]:=copy(t,1,pos(' ',t)-1);
x[i,1]:=copy(t,pos(' ',t)+1,length(t)); inc(i); end;{while}
mark:=i-1;close(f); end;
{判断是否到达目标状态}
procedure bool(be,st:integer); begin
for i:=mid-be+1 to cl[1-st] do
if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x); halt; end;{if} end;
{判断节点是否与前面的结点重复} procedure check(be,st:integer);
信息学奥赛 - 算法入门教程
