《搜索算法比较和优化》由会员分享，可在线阅读，更多相关《搜索算法比较和优化（21页珍藏版）》请在金锄头文库上搜索。
1、. .深度优先搜索和广度优先搜索的比拟和优化第一节 比 较一、深度优先搜索的特点是：1、从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但到达目标的深度是不定的。但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序构造都是一样的，即都是深度优先算法一和深度优先算法二中描述的算法构造，不一样的仅仅是存储结点数据构造和产生规那么以及输出要求。2、深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比拟明显时，用递归方法设计好
2、，它可以使得程序构造更简捷易懂。当搜索深度较大时，如例题2-5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比拟好。3、深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点即深度最大的结点先进展扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保存和不全部保存产生的结点的两种情况。而狭义的理解是，仅仅只保存全部产生结点的算法。本书取前一种广义的理解。不保存全部结点的算法属于一般的回溯算法范畴。保存全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。4、不保存全部结点的深度优先搜
3、索法，由于把扩展出的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。5、从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录到达当前目标的路径和相应的路程值，并与前面已记录的值进展比拟，保存其中最优的，等全部搜索完成后，才把保存的最优解输出。二、广度优先搜索法的显著特点是：1、在产生新的子
4、结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的构造。2、无论问题性质如何不同，利用广度优先搜索法解题的根本算法是一样的，但数据库中每一结点内容，产生式规那么，根据不同的问题，有不同的内容和构造，就是同一问题也可以有不同的表示方法。3、当结点到根结点的费用有的书称为耗散值和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，那么得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度或广度优先搜索算法：找到一个目标后，不是立即退
5、出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比拟，留下较优的结点。把所有可能的路径都搜索完后，才输出记录的最优路径。4、广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。5、比拟深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索算法法要快些。 总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时，要综合考虑。决定取舍。第二节 搜索算法的优化一
6、、深度优先搜索的剪枝优化方法就深度优先搜索搜索而言，它本身的时间复杂度都是指数级的，搜索的方向是盲目的，对于一些较大数据的问题是根本不行的，因此需要将搜索算法的效率提高。一般说来，深度优先搜索算法的优化有以下三种方法：1缩小搜索范围；2改变搜索次序；3剪枝。1、缩小搜索范围缩小搜索范围一般可从两个方面考虑优化：第一是在递归前对尚待搜索的信息进展预处理，减少搜索量；第二是增加约束条件，使其在保证不遗漏解的前提下尽可能“苛刻。例题1：因式分解(breeding.exe)【问题描述】将大于1的自然数N进展因式分解，满足 N=a1*a2*a3*am编一个程序，对任意的自然数N1N2,000,000,0
7、00，求N的所有形式不同的因式分解方案总数.如N=12，共有8种方案，它们分别是：12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*3输入：输入文件仅有一行包含一个整数N输出：输出文件仅有一行包含一个整数表示一个自然数N的因式分解方案总数。【样例输入】breeding.in12【样例输出】breeding.out8【问题分析】 如果完全盲目地搜索N的所有因式分解方案，我们可以通过穷举2到N之间的所有自然数，假设该数是N的约数那么递归地对该数进展进一步的分解，直到被分解的数变为1为止，此时就得到了N的一种因式分解方案。但是这种算法的搜索代价相
8、当大，当N较大时，程序出解耗时很长。为了改善搜索效率，我们不妨先将N的所有大于1的因子按从小到大的顺序记录在一个数组中，这样每一层递归搜索时只要穷举当前待分解数的因子即可，而当前待分解数是N的因子，所以它的因子也一定是N的因子，只要穷举N的因子中小于等于当前待分解数的局部因子即可。参考程序-1PROGRAM breeding(input,output);const fi=breeding.in; fo=breeding.out; maxM=1500000;var N,ans:longint; mem:array1.maxMof longint;PROCEDURE Init;var i:long
9、int;begin assign(input,fi); reset(input); readln(N); close(input); fillchar(mem,sizeof(mem),128); mem1:=0;end;FUNCTION Kernel(m:longint):longint;var rtn,i:longint;begin if m=0 then begin Kernel:=memm; exit; end; rtn:=1; for i:=2 to trunc(sqrt(m) do if m mod i=0 then rtn:=rtn+Kernel(m div i)+Kernel(i
10、); if frac(sqrt(m)=0 then rtn:=rtn-Kernel(trunc(sqrt(m); if m=maxM then memm:=rtn; Kernel:=rtn;end;PROCEDURE Print;begin assign(output,fo); rewrite(output); writeln(ans); close(output);end;begin Init; ans:=Kernel(N); Print;end.=参考程序-2program breading(input,output);const maxn=maxint;var f,a:array1.ma
11、xnof longint; n,m,ans:longint;procedure fin; var i,j:longint; begin m:=0; fillchar(a,sizeof(a),0); assign(input,breeding.in); reset(input); readln(input,n); close(input); for i:=1 to trunc(sqrt(n) do if n mod i=0 then begin inc(m); am:=i; end; i:=m; for j:=i downto 1 do if naj*aj then begin inc(m); am:=trunc(n/aj); end; for i:=1 to m do fi:=1; end;function fok(x:longint):longint; var i:longint; begin if fx1 then fok:=fx else begin for i:=2 to x-1 do if ax mod ai=0 then inc(fx,fok(i);
