资源描述：
《深度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、深度优先搜索所谓"深度"是对产生问题的状态结点而言的，"深度优先"是一种控制结点扩展的策略，这种策略是优先扩展深度大的结点，把状态向纵深发展。深度优先搜索也叫做DFS法(DepthFirstSearch)。深度优先搜索的递归实现过程：proceduredfs(i);forj:=1tordoifif子结点子结点mr符合条件then产生的子结点mr是目标结点then输出mr入栈；elsedfs(i+1);栈顶元素出栈（即删去mr）;endif;endfor;[例1]骑士游历:设有一个n*m的棋盘，在棋盘上任一点有一个中国象棋马.马走的规则为:1.马走日字2.马
2、只能向右走。当N,M输入之后,找出一条从左下角到右上角的路径。例如:输入N=4,M=4，输出:路径的格式:(1,1)->(2,3)->(4,4)，若不存在路径,则输出"no"算法分析：我们以4×4的棋盘为例进行分析，用树形结构表示马走的所有过程，求从起点到终点的路径,实际上就是从根结点开始深度优先搜索这棵树。马从（1，1）开始，按深度优先搜索法，走一步到达（2，3），判断是否到达终点，若没有，则继续往前走，再走一步到达（4，4），然后判断是否到达终点，若到达则退出，搜索过程结束。为了减少搜索次数，在马走的过程中，判断下一步所走的位置是否在棋盘上，如果不在棋盘上，
3、则另选一条路径再走。程序如下：constdx:array[1..4]ofinteger=(2,2,1,1);dy:array[1..4]ofinteger=(1,-1,2,-2);typemap=recordx,y:integer;end;vari,n,m:integer;a:array[0..50]ofmap;proceduredfs(i:integer);varj,k:integer;beginforj:=1to4doif(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-
4、1].y+dy[j]<=n)then{判断是否在棋盘上begina[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}beginwrite('(',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;begina[1].x:=1;a[1].y:=1;rea
5、dln(n,m);dfs(2);writeln('no');end.从上面的例子我们可以看出，深度优先搜索算法有两个特点：1、己产生的结点按深度排序，深度大的结点先得到扩展，即先产生它的子结点。2、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和编程技巧上又都不相同，甚至会有很大的差别。我们再看看另一个例子。[例2]选数（存盘名：NOIP2002pj）[问题描述]:已知n个整数x1,x2,,,xn，以及一个整数k(k
6、＜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）[输出]：屏幕输出，格式为：一个整数（满足条件的种数）。[输入输出样例]:输入：43371219输出：1算法分析：本题是求从n个数中选k个数的
7、组合，并使其和为素数。求解此题时，先用深度优先搜索法生成k个数的组合，再判断k个数的和是否为素数，若为素数则总数加1。在程序实现过程中，用数组a存放输入的n个数，用s表示k个数的和，ans表示和为素数的个数。为了避免不必要的搜索，程序对搜索过程进行了优化，限制搜索范围，在搜索过程dfs(i,m)中，参数m为第i个数的上限，下限为n-k+i。源程序：varn,k,i:byte;ans,s:longint;a:array[1..20]ofLongint;procedureprime(s:longint);{判断K个数的和是否为素数}vari:integer;begi
8、ni:=2;while(
