什么是搜索
百度百科中写到“搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法。”因为问题的多样性,简简单单的搜索产生了许多种方法已针对不同的问题,下文简单介绍简单的BFS与DFS及其优化。
DFS 深度优先搜索
深度优先搜索(缩写 DFS)是对一个连通图进行遍历的算法。
其思想是从一个顶点v0 开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,反复进行上述过程,从另一条路开始走到底,这样就可以较为有序地遍历所有的节点,这种尽量往深处走的概念即是深度优先的概念。
这样可以按顺序遍历所有的点,时间复杂度较高,所以称为暴力搜索,我们通常采用递归的形式编写程序,这样的搜索可以通过剪枝优化与储存搜索结果,从而使重复的搜索与计算减少。
剪枝:
- 可行性剪枝
当目前状态和题意不符,并且由于题目可以推出,往后的所有情况和题意都不符,那么就可以进行剪枝,直接把这种情况及后续的所有情况判断不可行,直接返回。
- 排除等效冗余
当几个字树具有完全相同的效果的时候,只选择其中一个搜索。
- 最优性剪枝
在我们用搜索方法解决最优化问题的时候的一种常用剪枝。当搜索还未结束时,记录的状态已经比当前保存的最优解更劣,那么此方案一定无效,停止搜索并回溯即可。
- 顺序剪枝
普遍来讲,搜索的顺序是不固定的,对一个问题来说,算法可以进入搜索树的任意的一个子节点。
但假如我们要搜索一个最小值,而非要从最大值存在的那个节点开搜,就可能存在搜索到最后才出解。我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲,有单调性存在的搜索问题可以和贪心思想结合,进行顺序剪枝。
记忆化搜索:
记忆化搜索实际上是递归来实现的,但是递归的过程中有许多的结果是被反复计算的,这样会大大降低算法的执行效率。而记忆化搜索是在递归的过程中,将已经计算出来的结果保存起来,当之后的计算用到的时候直接取出结果,避免重复运算,因此极大的提高了算法的效率。与此同时,储存结果的方法有很多,最常见为储存在一个array中,也可以构造一个优秀的hash。
BFS 广度优先搜索
深度优先搜索(缩写 BFS)也是对一个连通图进行遍历的算法。
我们首先访问顶点vi ,然后访问vi 的所有未被访问的邻接点w1 ,w2 ,…,wk 。依次从这些邻接点出发,访问它们的所有未被访问的邻接点; 依此类推,直到图中所有访问过的顶点的邻接点都被访问。
这时候我们需要利用队列来保证我们访问节点的顺序,此时我们的效率比深搜大大提高,原因是我们能够省去很多的重复步骤。
双端队列BFS
对于每次访问如果有不同的“代价”,而我们又想找到起始状态到每个状态的最小“代价”,相较于dp来说BFS对于边权为1或0的无向图是更优的。相较于一般BFS,只需在访问边权为0边时将沿该分支到达的新节点从队头入队即可。这样可以同时保持BFS后的单调性与双端性。
Hash判重
同样类似dp,在某种状态转移规则下找到最佳或所以路径时也可使用BFS。同时使用Hash表进行判重可以很好的提高时间与空间效率,甚至优于dp。而重点就在于构造优秀的Hash表。一般来说Hash表的构造方法有:
- 状态压缩——运用2进制来记录状态
- 直接取余——直接对109+7(或大质数)取模
- 平方取中——计算关键值平方,再取中间n位构造一个大小为2n 的表
- (折叠——将字符相加)
个人水平相对有限,欢迎大家对文中出现的错误加以指正,谢谢。