一些基础搜索算法的思想

ps：此博客是蒟蒻写的，可能并不是很正确。

再ps：该博客长期施工。

搜索

是暴力求解法的一种重要方法。就是通过不停的搜索将部分（甚至所有）情况找出，然后选出题目中需要的最优解。

ps：因为搜索算法好像没什么模板可言，所以下面只讲思想（其实就是我懒）。

BFS

BFS，广度优先搜索，是按照广度优先的一种搜索方法。

思想

利用队列，先把初始状态入队，然后每次取出队首，用队首搜索出所有由队首能够一步到达的状态并将之前没有出现过的状态入队。队列为空时，搜索完毕。到达某状态的步数就是该状态的最优解。因为只求最优解，所以不能搜索出所有情况。

BFS正确的前提是上面说的“一步”全部相同，因此BFS不能求有不同边权的最短路。而且BFS也不能走回之前的状态。

效率

O(n) ，n表示状态数。

DFS

DFS，深度优先搜索，是按照深度优先的一种搜索方法。

思想

利用栈（通常用系统栈，当然也可以用手工栈），从初始状态开始不停递归，有没走过的地方就去走（防止无限递归），这样就可以搜索出所有情况，但是不能在第一时间找到最优解（因为这么走不满足走到一处就一定是最优解）。

DFS必然是正确的（搜索了所有状态），但是状态数可能非常大，所以效率不是很高。

效率

O(S) ，S表示情况数。

IDDFS

IDDFS，迭代加深搜索，有种BFS和DFS结合的感觉。

思想

思想是很简单的，IDDFS枚举了一个深度depth，然后进行朴素DFS搜索，但有一个限制，就是DFS深度不能超过depth，一旦超过depth就不继续处理了。这样处理的话，一旦当前depth验证成功了，就不用继续处理depth+1了（像BFS一样立刻得到最优解）。IDDFS在答案大小不能完全确定，状态数比较多（BFS队列的空间复杂度为 O(n) ，n较大就扛不住了）的时候能发挥非常大的作用。

效率

玄学，但是由于depth最大为n，当depth小的时候DFS不会搜索太多情况（远小于S），所以效率还是很可观的。

IDA*

IDA*，IDDFS+A*，感觉想法比A*简单（虽然是IDDFS和A*的综合）。

思想

还是枚举深度depth，进行朴素IDDFS搜索，但是和A*一样，有估价函数（感觉估价函数到DFS里就变成剪枝了:P），就是在当前状态加上“最好”情况（这个“最好”情况通常不是实际最好情况），如果加上之后还不可能到达目标状态，这条路肯定就走不通了。

效率

玄学，复杂度取决于估价函数的好坏。

A*

因为比较神奇，专门写了一下，传送门。

折半搜索

因为比较神奇，专门写了一下，传送门。

双向BFS

双向BFS，顾名思义，是双向的广度优先搜索。

思想

就是用两个广度优先搜索，一个从起点开始，一个从终点开始，走到一起时搜索完毕。

显然BFS需要遍历到的格子是很多的。如果用双向BFS，那么就可以减少需要便利到的格子数。这看起来并没有什么很明显的作用，因为效率还是 O(n) 的，但是实际上前面所说的 O(n) 忽略掉了一个“常数”X，也就是每次拓展的状态数。当这个“常数”X比较大的时候，双向BFS就会明显体现出它的优势。

效率

O(n) 。