搜索
BFS
我的理解： 基础的bfs本质上也是动态规划，dist[i,j]表示到达(i,j)转移的最小次数。由于动态规划的无后效性，就是当前状态确定后，不需要管之前的状态转移。bfs是一层一层搜的，搜索的相当于是一个状态，第一个搜到的就是最优的。比如最简单的走迷宫，每个点只会走一次，那么第一次搜到的就是最优的路径，只需要二维st[N] [N]用来避免重复搜索；但是对于有一些点，可能能经过多次，也就是说有多个状态可以到达这个点，那么就需要三维st[N] [N] [K]，K表示的是这点的状态数。那么在搜索的时候，就需要根据该点的不同状态来进行不同方向的搜索（同样这个状态第一次搜到就是最优解）。
对于有些题目，会在转移条件上加上限制，也就是需要我们判断一下到达某个状态，可以从前面的哪些状态转移过来（例如：AcWing1131.拯救大兵瑞恩）。
边权为1的求最短路问题可以用bfs做，因为是一层一层搜的，所以能找到最短路（第一次访问到的就是最短的）
const int N=110;
int g[N][N];//存图
int d[N][N];//存每个点到源点的距离
int n,m;
typedef pair<int,int> PII;
queue<PII> que;
int bfs(){
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};//上下左右
que.push(make_pair(0,0));
memset(d,-1,sizeof d);//初始化距离为-1，表示未经过
d[0][0]=0;// 初始点为0
while(!que.empty()){
PII tmp=que.front();//取出队列中的第一个元素
que.pop();
for(int i=0;i<4;i++){
int x=tmp.first+dx[i],y=tmp.second+dy[i];
if(x>=0 && x<n && y>=0 && y<m && d[x][y]==-1 && g[x][y]==0){
d[x][y]=d[tmp.first][tmp.second]+1;
que.push(make_pair(x,y));
}
}
}
return d[n-1][m-1];
}
多源bfs
对于多起点的bfs，可以在一开始将所有起点都加入队列，然后正常进行bfs，就可以得出所有点到起点的最近距离。
这也类似于多起点的最短路问题，如果边权不为1，需要利用Dijkstra来做，可以通过构建虚拟源点的方式求解，具体见最短路笔记
双端队列bfs
头文件：#include<deque>
常用函数：front()、push_front()、push_back()、pop_front()、pop_back()
双端队列bfs用来解决边权为0或1的最短路问题，相当于是Dijkstra算法的简化版。
Dijkstra流程： 先把源点放入优先队列，接下来重复以下操作(取出队列中距离源点最近的点—优先队列的队头，用该点更新其它与该点相邻的点的距离，再把更新后的距离放入队列)。每个点在出队的时候就说明从源点到该点的最短距离已经找到，因此要对这个点进行标记，后续计算时忽略该点。
双端队列bfs流程： 通过类比，利用贪心的思想，优先队列的作用是为了维护一个单调不减的队列，每次取出最小的元素表示该元素不会再被其他点所更新（因为所有的边权都是非负数）。由于该图的边权为0或1，可以用双端队列来维护一个单调不减的队列，每次取出队头表示该点的最小距离已经找到。
如何用双端队列维护单调不减的队列呢？ 遍历某点的邻边，如果边权为1，表示该点还是有可能会被边权为0的点所更新的，所以将这个点插入到队尾；如果边权为0，表示这个点已经是最小的了（因为bfs是宽搜，最早搜到的点肯定距离源点的距离是最短的），那么就将这个点插入队头。注意： 取点先取队头，队头的优先级最高，表示不会再被更新了，而队尾插入的数还是有可能会被更新的。
A*
A*算法：使用优先队列维护。每个元素可以入队多次，也可以出队多次。某一个元素出队后，并不作任何标记，之后还可以继续入队。但也有入队条件，只有比当前解更好才能入队。也就是说第一次出队的元素并不具备最优解。但是终点出队可以得到最优解，此时从起点到终点上的所有元素都获得最优解。
A*算法求解前k个最优解：
d[u]：起点->u的真实距离 f[u]：u->终点的估计距离 g[u]：u->终点的真实距离。
满足最优的条件是f[u]<=g[u] (估价值<=真实值) (意思是说，构造的估价值一定是<=真实值的才能满足A*算法的使用条件)
A*算法与dijkstra算法类似，都是利用优先队列求解。在dijkstra单源最短路求解求解过程中，每次优先队列弹出d[u]为最优解，但是却没有考虑到"未来"的路径。所以在A *算法中引入了估计函数，优先队列出队的是d[u]+f[u]的最小值，也是估计的路径的最小值。
注意： 引入估计函数的目的就是优化搜索空间。考虑最开始暴力的做法，想要求解到终点的前k个最短路径，每次将u到邻边的距离更新后加入到优先队列中，然后每次出队的终点就是最短路径，然后出队第k个终点后就是答案。但是这种做法毫无目的性，就是每次选出最短距离，并没有考虑到 “未来” 的情况，就是出队的某个点可能根本无法到达终点，但是却因为到起点的距离最近而出队，从而造成了不必要的搜索。引入估价函数后，每次出队的是d[u]+f[u]的最小值，也就是说考虑到了"未来"的情况，能大大缩小搜索空间。
DFS
剪枝策略： 在搜索前，提前判断一下这种情况下是否满足条件，不满足就不需要继续往下搜索了，直接return剪枝（不需要到最终出结果在判断，中间过程就可以判断了）。
强调顺序，然后再dfs完回溯后需要恢复现场，也就是把有一些标记的点重新清除标记。
//全排列代码
//t表示填充第t个位置
void dfs(int t){
for(int i=1;i<=n;i++){
if(!st[i]){
st[i]=true;
a[t]=i;//在第t位上填上数
dfs(t+1);
//恢复现场
st[i]=false;
}
}
}
记忆化搜索
还没学哈哈，敬请期待…
标签：队列,边权,笔记,bfs,int,算法,出队,搜索 From： https://blog.csdn.net/yyyyyyuzy/article/details/143302004