BFS¶
应用¶
- 寻找最短路径，由于水波扩散特点，bfs找到的路径一定是最短路径。
例题¶
多源bfs（折半搜索）¶
- 从起点和终点同时搜索，复杂度2n->2*2n/2，通过是否相遇判断是否存在路径
- 在已知初始状态和结束状态时使用
-
对于指数级增长的bfs很有用，但对于一些类型（如棋盘移动）使用去重在大部分情况就足够了（color）
-
两种实现方式：
- 合用一个队列，适合正反两个BFS平衡的情况，正向搜索和逆向搜索交替进行
-
分成两个队列，正向和逆向队列分开，适合反正两个BFS不平衡的情况，可以让子状态（队列中元素数目，比较两个queue的size）较少的进行BFS扩展下一层
-
对于路径不存在（两边搜索不会相遇）的情况，当一方搜索结束时就可以终止了（说明不可能再相遇了）
- 特殊，用queue超时，每到一层先直接检查所有元素，用两个set存储方便遍历
- P3067Balanced Cow Subsets G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
-
本题是dfs但是思想类似，拆分为一半，对两半分别进行搜索
-
一个有\(20\)头奶牛，那么考虑对于每一头奶牛来说有\(3\)种状态，放在一组，放在另一组，不放任何一组，如果暴力枚举时间复杂度为\(O(3^n)>1E9\)，无法接受。考虑将\(n\)头奶牛分为两半，每组分别暴力求解，时间复杂度\(O(3^\frac{n}{2})\)可以通过。
- 注意这样的到的可能重复（对一个子集的不同平衡分割），还需要用状态压缩表示子集进行去重
1.带有状态压缩参数的bfs¶
-
特殊bfs，可以重复访问节点，防止重复访问不能仅仅记录一个点是否访问过，而应记录的是，在访问过的节点相同时，是否重复去访问一个节点。
c++
int shortestPathLength(vector<vector<int>>& graph) {
int n=graph.size();
queue<tuple<int,int,int>>q;//记录当前位置，点的访问状态，路径长度（这个也可以不记录在这里，可以加一层循环来计算）
vector<vector<bool>>seen(n,vector<bool>(1<<n));//判断是否到过，用访问状态和当前点共同判断。
for(int i=0;i<n;i++)//初始化
{
q.emplace(i,1<<i,0);
seen[i][1<<i]=true;
}
int ans=0;
while(!q.empty())
{
auto [u,mask,dist]=q.front();
q.pop();
if(mask==(1<<n)-1)//结束
{
ans=dist;
break;
}
for(int v:graph[u])
{
int mask_v=mask|(1<<v);
if(!seen[v][mask_v])//去重
{
q.emplace(v,mask_v,dist+1);
seen[v][mask_v]=true;
}
}
}
return ans;
}
-
也是可以重复通过一个点，如果持有相同钥匙两次通过一个点那么就是重复的（与第一题这是相似第）。
-
另类图遍历
与双端队列结合¶
- 处理图的边权仅为0/1的问题
- 在dj算法中替换优先队列维护优先级，直接0插到队头，1插到队尾即可
- 普通图中dj的时间复杂度为\(O((n+m)log_2n)\)
-
在01特殊图中可以使用"BFS+双端队列"在\(O(n)\)内取得最短路径
与优先队列结合¶
- poj2227：一个棋盘，给每个店的高度，二维接雨水
- 从边界向内部进行反向bfs
- 现将边界节点加入到优先队列（小根堆），每次出队的为边界中最小的点
- 出队之后检查周边还没有加入过队列的点，作为移除优先队列front节点后新的边界，如果比移除的点高，则不能存水，否则可以存水，计算差值并将高度修改为原先移除节点的高度
while(!q.empty()) {
tp=q.top();
q.pop();
for(int i=0;i<4;i++) {
int xx=tp.x+to[i][0],yy=tp.y+to[i][1];
if( 0<=xx&&xx<n && 0<=yy&&yy<m && !vis[xx][yy]) {
vis[xx][yy]=1;
t.x=xx,t.y=yy,t.h=mp[xx][yy];
if(t.h<tp.h) ans+=(tp.h-t.h),t.h=tp.h;
q.push(t);
}
}
}
A*启发式搜索¶
-
常用于求解确定起点、终点的最短路径
-
普通BFS：只看起点
-
A*：既看起点，又看终点
-
贪心最优搜索并不一定能得到最优结果“只看终点不看起点”（如使用曼哈顿距离估计，在有障碍图上不一定可以获取正确结果）
-
A算法既看起点也看终点*，能得到最优解，估价函数
f(i)=g(i)+h(i) -
g(i)表示从s到i的代价，由dj保证最优性 h(i)表示从i到t的代价，由贪心计算-
由于在终点有h(i)=0，即f(i)=g(i)保证了算法的正确性
-
h函数设计
-
4方向移动：
abs(i.x-t.x)+abs(i.y-t.y) - 8方向：
max{abs(i.x-t.x),abs(i.y-t.y)} -
任意：
sqrt((i.x-t.x)^2+(i.y-t.y)^2) -
原则：
-
g与h采用相同的距离计算方式
- h要正确反映远近关系
-
h(i)要小于等于i-t的实际最短距离
-
```c++ truct node { // 使用A*时所需的结构体 int x; double v;
bool operator<(node a) const { return v + f[x] > a.v + f[a.x]; } };
```
- 在dj算法的基础上进行修改
例题¶
-
h函数可以定义为，不在应该在的位置的数字个数。
- f=已经移动的次数+h()
-
依据f放入优先队列中进行类bfs
-
-
```c++ #include
using namespace std;
// #define int long long
typedef long long ll; typedef unsigned long long ull; typedef pair
const int N = 1e4 + 9; const int INF = 0x3f3f3f3f;
int n, m, st, ed, k; int dist[N], cnt[N];
struct Edge { int u, w; // 出点，权值 bool operator < (const Edge &u) const { return w > u.w; } }; // 存边用的结构体
vector
g[N]; // 正向建图 vector rg[N]; // 反向建图 struct Node { int f, g, idx; // 估价值 + 真实值，真实值，编号 bool operator<(const Node &u) const { return f > u.f; } };
void dijkstra() // 求出终点到起点时扩展过的所有点的路（被用来当作估价函数，因为其值不会小于实际距离） { priority_queue
heap; bitset vis; memset(dist, 0x3f, sizeof dist); heap.push({ed, 0}); dist[ed] = 0; while (!heap.empty()) { auto t = heap.top(); heap.pop(); int u = t.u; if (vis[u]) continue ; vis[u] = true; for (auto y : rg[u]) { int v = y.u, w = y.w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; heap.push({v, dist[v]}); } } }}
int astar() { priority_queue
heap; heap.push({dist[st], 0, st}); // 初始点到终点的f值为dist[st] + 0，起点到自身的距离为 0 while (!heap.empty()) { auto t = heap.top(); heap.pop(); int idx = t.idx, distance = t.g; // 取出编号和st点到该点的实际距离 cnt[idx] ++; // 小优化 if (cnt[ed] == k) return distance; // 如果终点遍历了 k 次，直接return掉 for (auto y : g[idx]) { int v = y.u, w = y.w; if (cnt[v] < k) heap.push({distance + w + dist[v], distance + w, v}); // 该状态仍可扩展 } } return -1; // 无解时直接return}
signed main() { // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 1; i <= m; i ++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); // 正向建图 rg[v].push_back({u, w}); // 反向建图 }
cin >> st >> ed >> k; if (st == ed) k ++; // 题目要求，至少要有一条路 dijkstra(); // cout << dist[st] << '\n'; // if (dist[st] == INF) cout << -1 << '\n'; cout << astar() << '\n'; // 输出 k 短路 return 0;} ```
DFS¶
例题¶
- 863. 二叉树中所有距离为 K 的结点
- 一次 dfs 构图，一次 bfs 找到结果
- P8779 [蓝桥杯 2022 省 A] 推导部分和 - 洛谷 | 计算机科学教育新生态
- 难建图
回溯¶
记忆化搜索¶
思想¶
动态规划是一种自底向上的思想，而记忆化搜索是一种自顶向下的思想。 当便利顺序难以确认时，使用记忆化搜索由dfs自动决定 逻辑上相比动态规划更为清晰简单。
剪枝¶
- 1059. 从始点到终点的所有路径
- 记忆化+剪纸，卡的很
例题¶
- 698.h划分为k个相同的子集
- 638. 大礼包
- 多元组用背包动态规划不如记忆化搜索简单（直接map）
- 691. 贴纸拼词
- 1301. 最大得分的路径数目
- 241. 为运算表达式设计优先级
- 递归分治（枚举最后一个完成的运算符）+记忆化搜索
- 332. 重新安排行程
- 对机票计数，而不是通过删除set中的元素，避免迭代器发生问题
- 也可以使用欧拉回路解决
- 1815. 得到新鲜甜甜圈的最多组数
剪枝¶
思路¶
- 搜索顺序剪枝：先排序再搜搜
- 可行性剪枝：条件不合法则不再继续
- 最优性剪枝：与已经得到的最优解进行比较
- 排除冗余
- 记忆化搜索
- 优化搜索顺序
实例¶
- 棋盘问题
- 如使用曼哈顿距离估计图上剩余最短距离，如果当前距离加上最短距离都超了那么就剪掉
- 奇偶判断，图上两点间所有路径的奇偶性一定与其曼哈顿距离是一致的（绕路不会改变奇偶性）
- 通常在main中而不是dfs中完成
- 背包问题
-
从大到小的开始装
-
数独
- 从未知量少的行开始搜索
例题¶
优化¶
IDDFS¶
- BFS与DFS结合，减少空间浪费（BFS）和无效搜索（DFS）
- 限制深度的dfs
- 每次从第一层进行有层数上限的dfs
- 第一次搜索1
- 第二次1~2
- ...
- 第k次1~k
IDA*¶
-
与A*相比IDA*的应用更为广泛
-
在IDDFS基础上添加预测，如果当前深度+未来需要的步数>深度限制则立即返回false（使用估价函数剪枝）
-
c++ const int N = 100; //最大层次 int num[N]; //记录一条路径上的数字，num[i]是路径上第i层的数字 int n, depth; bool dfs(int now, int d) { //now:当前路径走到的数字，d：now所在的深度 if (d > depth) return false; //当前深度大于层数限制 if (now == n) return true; //找到目标。注意：这一句不能放在上一句前面 if (now << (depth - d) < n) //剪枝：剩下的层数用最乐观的倍增也不能达到n return false; num[d] = now; //记录这条路径上第d层的数字 for(int i = 0; i <= d; i++) { //遍历之前算过的数，继续下一层 if (dfs(now + num[i], d + 1)) return true; //加 else if (dfs(now - num[i], d + 1)) return true; //减 } return false; } int main() { while(~scanf("%d", &n) && n) { for(depth = 0;; depth++) { //IDDFS：每次限制最大搜索depth层 memset(num, 0, sizeof(num)); if (dfs(1, 0)) break; //从数字1开始，当前层0 } printf("%d\n", depth); } return 0; }
例题¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
vector<vector<int>>g(4,vector<int>(4,0));
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
char c;
cin>>c;
if(c=='B')
g[i][j]=1;
else if(c=='W')
g[i][j]=2;
}
}
auto check=[&]()->bool{
bool res=false;
for(int i=0;i<4;i++){
if(g[i][0]==g[i][1]&&g[i][1]==g[i][2]&&g[i][2]==g[i][3])
res=true;
if(g[0][i]==g[1][i]&&g[1][i]==g[2][i]&&g[2][i]==g[3][i])
res=true;
}
if(g[0][0]==g[1][1]&&g[1][1]==g[2][2]&&g[2][2]==g[3][3])
res=true;
if(g[0][3]==g[1][2]&&g[1][2]==g[2][1]&&g[2][1]==g[3][0])
res=true;
return res;
};
set<vector<vector<int>>>st;
vector<vector<int>>moves={{1,0},{-1,0},{0,1},{0,-1}};
function<bool(int,int,int)>dfs;
dfs=[&](int sum,int target,int n)->bool{
vector<vector<int>>state=g;
state[0].push_back(n);
if(sum>target||st.count(state))
return false;
st.insert(state);
if(check())
return true;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(g[i][j]==0){
for(auto move:moves){
int x=i+move[0];
int y=j+move[1];
if(x>=0&&x<4&&y>=0&&y<4){
if(g[x][y]==n+1){
swap(g[i][j],g[x][y]);
if(dfs(sum+1,target,n^1))
return true;
swap(g[i][j],g[x][y]);
}
}
}
}
}
}
return false;
};
int res;
for(int i=0;i<INT_MAX;i++){
st.clear();
if(dfs(0,i,0)||dfs(0,i,1)){
res=i;
break;
}
}
cout<<res<<endl;
return 0;