学习笔记（三）搜索

一般来讲，搜索主要分为两条路bfs和dfs，本节主要研究两种方式搜索一些延申及优化。

一、DFS -> 剪枝 -> IDDFS

void dfs(int s, int t, int depth) {
	if (s == t && depth <= n) {
		//输出答案
		return;
	}
	if (check(s) || depth > n) //剪枝
		return;
	for (int i = 0;;) { //寻找当前节点的子节点，即树的下一层
		int new_s = s + i; //新的状态
		if (!vis[new_s]) { //记忆化剪枝
			vis[new_s] = true;
			dfs(new_s, t, depth + 1); //下一层
			vis[new_s] = false; //回溯
		}
	}
}

基础dfs模板如上，根据不同题进行修改，这里不过多描述。

剪枝对于dfs来讲是个无比重要的一步，能大大减少时间复杂度，搜索必剪枝。

1.记忆化剪枝

最常见的一种方式，将n叉树缩减为排列树，时间复杂度也从O(n^n)降为O(n!)，但这还远远不够，一般暴力都是默认带记忆化剪枝的。

2.分支限界（即最优化剪枝+可行性剪枝）

当前状态下以后每步都走最优步依旧不如当前记录的最优状态，则舍弃当前状态，剪枝。

实际上bfs中的A*优化和分支限界是同理的，只不过A*是走最优步，分支限界是直接剪枝。

例如在权值均为1的图中寻路，给出起点终点，当前节点与重点的曼哈顿距离即为最优距离，A*算法中为h函数，分支限界中已经有一条记录的路径，如果当前走过的路加曼哈顿距离大于记录的长度，则剪枝。（这个问题更常用IDA*处理）

例：洛谷P1118 hdu1010

3.冗余项剪枝

一棵对称二叉树，遍历左子树就好了，右子树剪枝掉，同理如果在处理过程中遇到下一层多个节点及以后都一致，搜索一个就够了。

4.优化顺序

如果本身重点可能在树偏右下的位置，优化顺序后，优化到树偏左下位置，能大大减少搜索次数。对于这种情况，另一种方式就是采用IDDFS，减少搜索次数。

这里介绍几个比较特殊的例子（待补充）

1.洛谷P1433 原题是从起点到终点最短路径问题，只不过要经过所有点，即TSP问题。考虑搜索便是全排列加分支限界，只不过比较难过。这类题常规解法为状压DP，本蒟蒻试了一下退火模拟，没过去，有lao可以尝试一下。

2.hdu1010 本题为刚好k步走到终点，先做奇偶判断，然后分支限界。考虑IDA*也可以，不过也是要加上奇偶判断。

IDDFS即通过bfs方式进行dfs，优化了bfs占用空间过大，dfs搜索次数多的缺点，形成一个时间空间复杂度都还不错的算法。

void IDDFS(int s, int t, int max_depth) {
	for (int depth = 0, depth <= max_depth; depth++) {
		dfs(s, t, depth);
		if (flag)
			break;
	}
}

限制深度的dfs，对于最短路径之类的问题，帮助很大。

二、BFS -> Dijkstra -> A* -> IDA*

基础bfs是通过队列，一层一层遍历的。

void bfs(int s,int t){
	queue<int> q; //队列
	q.push(s); //起点
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u==t) {
			//输出答案
			return;
		}
		for(int i=0;;){
			int new_u=u+i;
			if(!vis[new_u]){ //记忆化
				vis[new_u]=true;
				q.push(new_u); //下一层子节点
			}
		}
	}
}

一般bfs队列中储存的是点和答案的二元组，方便记录最短路径，如果要输出路径，还要记录一个pre数组。

typedef struct aa{
	int data,dis;
}A;
queue<A> q;

Dijkstra算法则是将队列改为优先队列（稀疏图用优先队列，稠密图用双重循环），dijkstra算法更适用于权值不为1的时候计算。优先队列的顺序为到起点长度从小到大排列，只看起点，所以该算法一般会把图上所有点都搜索完，终点碰巧就搜索出来了。

typedef struct aa{
	int data,dis;
	bool operator<(const aa& b){
		return dis<b.dis;
	}
}A;
priority_queue<A> pq;

A*算法是该算法在一定程度上的改进，通过估价函数f=g+h，g为dj算法，h为贪心策略，找到一个下界，一种当前状态到终点的最优路径（类似分支限界），一般贪心只考虑终点，dj算法只考虑起点，A*综合二者，均考虑，二者相加即为A*算法中优先队列的顺序。

typedef struct aa{
	int data,dis;
	bool operator<(const aa& b){
		return dis+h(data)<b.dis+h(b.data);
	}
}A;
priority_queue<A> pq;

IDA*就是IDDFS的延申，通过估价函数，对IDDFS进行剪枝，类似于IDDFS的分支限界。

三、BFS -> 双端队列+BFS

对于特殊图（权值均为0或者1）而言，双端队列可以将dj算法搜索的O（(n+m)logn）时间复杂度降为O（n）。

扩展边权为0的邻居点时，把他放在前端，扩展边权为1的邻居点是，把他放在后端，然后正常bfs就好了，这样就能保证先走边权为0的路径再走边权为1的路径，找到最短路径。

例：洛谷P4667

四、BFS -> 双向BFS -> 双向IDA*

对于多叉树搜索最短路径的时候，每扩展下一层，扩展状态呈指数增长，如果知道起点和终点状态，可以从起点和终点同时bfs，相遇即找到答案，一般双向bfs都用两个队列，先扩展队列中数量少的队列，用两个vis数组储存，如果扩展第一个队列时一个点在第二个vis中，则相遇了。这样可以大大减少时间复杂度，例如5^10能缩短为2*5^5，如果线性增长，则双向提升不大。

双向IDA*可以在这个基础上进一步优化，答案就为两个深度之和-1。

总结：dfs重点在剪枝，bfs重点在不同题干选择的队列不同，优先队列（两种），双端队列，两个队列等等，对于排列组合搜索题一般采用dfs，最短路径一般采用bfs。

补充：稠密图一般采用邻接矩阵，稀疏图一般采用邻接表或者链式前向星，不同储存结构可能会产生不同的时间复杂度。