搜索算法的通用优化方法

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

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算法所能解决的问题当中，有相当一部分，是给你初状态和末状态，让你求一条从初状态到末状态的最