搜索算法的通用优化方法

搜索算法的通用优化方法

ID:23882763

大小:49.50 KB

页数:8页

时间:2018-11-11

搜索算法的通用优化方法_第1页
搜索算法的通用优化方法_第2页
搜索算法的通用优化方法_第3页
搜索算法的通用优化方法_第4页
搜索算法的通用优化方法_第5页
资源描述:

《搜索算法的通用优化方法》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、搜索算法的通用优化方法[DFS][搜索剪枝]在很多情况下,我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解,搜索到后也只能回溯。为了避免出现这种情况,我们需要灵活地去定制回溯搜索的边界。*例题计算机网络连接要将n(n<=30)台计算机连成网络,连接方法:去除首尾两台计算机与一台计算机相连以外,其他计算机只与两台计算机相连。连接的长度则为计算机连接的电缆的长度。求:一种连接方式,使需要电缆的长度最短。分析这个题目用回溯搜索来解决。但是,由于回溯搜索的搜索量比较大,达到了n!,是不可能搜索完n=30的情况的,所以,我们考虑对它进行优化:假如目前搜

2、索到了一组解,电缆总长度为kx,那么,如果说以后搜索到的连接方法(不一定是最终连接方法)的连接长度>=kx,那么这个方案的总长度一定不小于kx,那么,就不必要搜索下去了,直接换下一个结点继续搜索。路径A1-A2-…An与路径An-An-1-…A1这两条路径是一个“正反”的关系,本质上是相同的,于是我们可以规定起点始的下标总是小于终点的下标假如路径的A-B-C-D的长度

3、以节省很多的时间吗?打一个比方,前面有一个路径,别人已经提示:“这是死路,肯定不通”,而你的程序仍然很“执着”地要继续朝这个方向走,走到头来才发现,别人的提示是正确的。这样,浪费了很多的时间。针对这种情况,我们可以把“死路”给标记一下不走,就可以得到更高的搜索效率。*例题皇后问题分析取n=4为例采用一般的回溯,就是每一行的每个格子放与不放都搜索一下:然后回溯一次,换下一个点继续搜索。这个算法的效率,是实际上,在放置了(1,1)这个皇后,再把皇后放置在(2,1)就是毫无意义的:前面一个皇后一定能攻击到它。为了避免这种情况,我们这样做:走了一个棋子以后,把它的“势力范围”给圈出来

4、,并且告诉以后的皇后:这里不能放置。举简单的例子:放置皇后(1,1),由于打“.”的格子在放了(1,1)这颗子之后,被标注为了“不能走”,所以这些点我们就不去理会了。这样就节省了很多时间,大大提高了搜索的效率。而对于很多回溯的题目,我们都可以采用分枝定界法,把搜索树中不必要的枝剪去,大大提高了搜索的效率。[记忆化]对于一些有最优子结构的问题,我们往往采用动态规划算法来实现。采用动态规划算法,需要弄清状态以及状态是如何转移的,接着列出状态转移方程。首先举一个非常简单的例子    *例题数字三角形    分析无论对与新手还是老手,这都是再熟悉不过的题了,很容易地,我们写出状态转移

5、方程:      f(i,j)=a[i,j]+min{f(i+1,j)+f(i,j+1)}对于动态规划算法解决这个问题,我们根据状态转移方程和状态转移方向,比较容易地写出动态规划的循环表示方法。但是,当状态和转移非常复杂的时候,也许写出循环式的动态规划就不是那么简单了。我们尝试从正面的思路去分析问题,如上例,不难得出一个非常简单的递归过程:if(i==0)return(a[i,j]);f1=f(i+1,j);f2=f(i,j+1);iff1>f2returna[i,j]+f1;elsereturna[i,j]+f2;显而易见,这个算法就是最简单的搜索算法。时间复杂度为2n,明

6、显是会超时的。分析一下搜索的过程,实际上,很多调用都是不必要的,也就是把产生过的最优状态,又产生了一次。为了避免浪费,很显然,我们存放一个opt数组:Opt[i,j]-每产生一个f(i,j),将f(i,j)的值放入opt中,以后再次调用到f(i,j)的时候,直接从opt[i,j]来取就可以了。      于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,而且在相当多的情况下,递归算法能更好地避免浪费,在比赛中是非常实用的。    总结记忆化搜索是对动态规划状态转移方程的直观表示。本质上来说,它仍然是用搜索算法

7、的核心,只不过使用“记录求过的状态”的办法,来避免重复搜索,这样,记忆化搜索的每一步,也可以对应到动态规划算法中去。记忆化搜索有优化方便、调试容易、思维直观的优点,但是效率上比循环的动态规划差一个常数,但是时间和空间复杂度是同一数量级的(尽管空间上也差一个常数,那就是堆栈空间)。当n比较小的时候,我们可以忽略这个常数,从而记忆化搜索可以和动态规划达到完全相同的效果。[BFS]    [双向搜索]      在bfs算法所能解决的问题当中,有相当一部分,是给你初状态和末状态,让你求一条从初状态到末状态的最

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。