SZTUACM寒假周报(2022.12.24~2023.1.1)
杂项——搜索专题知识整理
前言：因为之前搜索学得很随意，知识点很杂，加上期末一直在赶ddl，投入训练时间很少，所以本周决定整理一下有关搜索的知识点，就当作复健了.
BFS
说明
- BFS是从初始状态出发, 逐层进行扩展, 在扩展过程中记录并寻找答案的过程, 与队列配合使用.
- 由于BFS是逐层进行扩展的，当状态的边权相同时，按照入队先后顺序的状态序列具有答案单调性，所以第一次扩展到某个状态时, 此时记录的步数等信息就是最优的. 因此常用于求解最小操作次数，边权相同的最短路问题
int bfs(int s, int t) {
// s, t 始态, 终态
if (s == t) return 0;
// 初始化始态信息
...
// 初始化队列
queue<int> q;
q.push(s);
while (q.size()) {
int u = q.front();
q.pop();
// 扩展过程, 如遇到终态, 此时的答案便是最优的, 返回即可
...
}
return -1; // 无解
}
例 立体推箱子
BFS变种(多源BFS, 双端队列BFS, 优先队列BFS)
多源bfs: 顾名思义, bfs的起点有多个等价状态, 这种情况只需要在初始化队列时, 入队并初始化多个等价状态, 即可.
例 矩阵距离
还有一种情况, 即有起点, 终点同时有多个等价状态, 此时从起点做多源bfs, 暴搜所有终点状态, 如果题目求得是最小步数, 那么还需要统计到达每个终点状态求得最值.
例 公交路线
补充: 可以将上述情况看成用一个源点连接各个起点, 用一个汇点连接各个终点, 只不过这些边的边权都是0.
双端队列BFS, 优先队列BFS
说明
- BFS的过程之所以具有单调性的前提是:边权相同, 当边权不同时, 将队列改为双端队列或者优先队列, 就能继续保持单调性.
- 只不过, 获取某个状态的最优解的时刻, 不是该状态第一次被扩展到的时候, 而是其第一次出队的时候.
双端队列BFS: 使用双端队列进行BFS, 适用于状态之间有两种边权的情况, 在扩展过程中, 将边权小的状态插进队头, 边权更大的则插进队尾, 便能不破坏单调性.
例 电路维修
优先队列BFS: 当由多种边权时候, 这个时候就只能用优先队列了, dijkstra的堆优化版就是优先队列BFS.
例 装满的油箱
BFS两种优化(双向BFS, A*)
双向bfs : 从起始状态和目标状态两端分别进行bfs, 当两者重合时, 即找到答案.
大致模板
// 形参列表中省略号(...)表示扩展过程中需要用到的变量
// 返回值表示本次扩展中是否重合
bool extend(queue<int>& q, ... ) {
// 扩展一整层
int sz = q.size();
while (sz--) {
int u = q.front();
q.pop();
// 扩展过程扩展过程中检查是否重合, 重合返回true;
// 否则, 检查是否访问过, 将未访问的结点入队
...
}
return false;
}
// s, t分别表示起始状态, 目标状态
int bfs(int s, int t) {
if (s == t) return 0;
// 初始化起始和目标状态
...
// 定义两个队列并初始化
queue<int> qs, qt;
qs.push(s);
qt.push(t);
int step = 0;
// 当一端无法扩展且两头还没有重合, 说明无解
while (!qs.empty() && !qt.empty()) {
++step;
// 两端各扩展一遍
if (extend(qs, ... )) return step;
++step;
if (extend(qt, ... )) return step;
}
return -1;
}
使用场景1: 当搜索空间很大的时候, 双向bfs可以有效减少搜索空间, 从而加快搜索效率. 常常用于求解最小步数问题.
例 P1032 [NOIP2002 提高组] 字串变换
例 The Morning after Halloween
使用场景2 : 当起始状态, 目标状态可变时, 且两者扩展方式不同(例如两者移动步数不同), 此时转换成单向bfs代码可能比较麻烦, 考虑使用二维状态分别保存两者各自状态的话, 搜索空间可能过大, 则需要用到双向bfs.
补充
- 实现双向bfs的方式主要有两种, 第一种是每次分别对两端各扩展一层, 第二种是选择队列中元素较少的那一端进行扩展(理论上, 层数越多, 扩展结点越多, 搜索空间也就越大), 第二种方式是对第一种的优化, 但是有局限性, 不适于每一步都需要两端进行扩展的情况.
- 一般能用朴素bfs做的, 双向bfs也能做, 但只有当搜索空间够足大时, 优化效果才足够明显.
A*: 加入了估价函数的优先队列BFS
说明
- 估价函数: 当前状态距离终点状态的预估距离, 应满足小于等于真实距离的条件
- 估价函数的选择需要经验, 可以从扩展过程中的改变量入手
- A*算法的单调性只针对终点状态, 即只有终点态第一次出队才具有最有的性质.
例 八数码
例 第K短路
DFS: 每次选择一条分支, 不断深入, 直到递归边界回溯后再选择另一条分支进行相同过程, 以递归形式出现.
void dfs(int u, ... ) {
// 递归边界
if () {...}
// 扩展过程
... // dfs(u + 1, ...), 形式不一
}
剪枝: 剪去搜索树中不必要的分支, 从而缩小搜索空间, 提高搜索效率.
- 优化搜索顺序: 不同的搜索顺序产生的分支数量不同, dfs过程应选择分支较少的搜索顺序
- 排除等效冗余:如果多个分支产生的状态是相同的, 就只需选择一条进行搜索即可
- 可行性剪枝: 如果发现当前分支无法达到终点, 便可提前回溯
- 最忧性剪枝: 如果发现当前分支无法产生优化当前已经找到的解, 便可提前回溯
- 记忆化: 如果发现当前分支已被执行过, 便可跳过该分支
例 Sticks
例 P1731 [NOI1999] 生日蛋糕
例 小猫爬山
例 数独
例 数独2
迭代加深搜索: 从小到大限定dfs的深度, 如果在当前深度限制下搜不到答案, 就提前回溯并增加深度限制, 重新进行一次dfs.
说明:
- 假设答案的所在深度并不深, 但由于dfs的特性, 但在搜到答案这条分支之前, 可能出现深度很深的分支, 那么在搜到答案之前就会做许多无用功. 迭代加深搜索就可以解决这种窘境.
- 虽然当深度限制为d时, 0~d-1层又会被重新搜索一遍, 当节点分支数目较多时, 每层的节点数目会呈指数级增长, 0~d-1的搜索时间复杂度远小于整体时间复杂度, 即可忽略不计.
bool dfs(int u, int depth, ...) {
if (u > depth) return false;
if (u == depth) {
if (满足一定条件) return true;
return false;
}
// 扩展过程, 如果某个递归分支已经搜到答案, return true
if (u + 1, depth, ... ) return true;
return false;
}
int ids() {
int dep = 0;
while (!dfs(0, dep)) ++dep;
return dep;
}
例 加成序列
IDA*: 加入了估价函数的迭代加深搜索, 当当前深度加上预估距离已经超过深度限制, 就提前返回. 估价函数要求与A*差别不大.
int f(){} // 估价函数
bool dfs(int u, int depth, ...) {
if (u + f() > depth) return false;
if (!f()) return true;
// 扩展过程, 如果某个递归分支已经搜到答案, return true
if (u + 1, depth, ... ) return true;
return false;
}
int idastar() {
int dep = 0;
while (!dfs(0, dep)) ++dep;
return dep;
}
双向dfs(折半dfs)
说明: 与双向bfs的思想类似, 减少搜索空间的同时, 避免了在深层子树浪费时间.
例 送礼物
总结
通过本次整理, 我对dfs, bfs有了更加清晰的认识. 两者都是对状态树的一种遍历, 在遍历过程进行记录并寻求答案的过程. 再者通过一些优化技巧来减少搜索空间, 这一点dfs的剪枝尤为明显. bfs因其单调性可以很方便的求解最小步数问题, 且不用担心爆栈的问题. 由于期间阳了, 躺了3天, 来不及整理题解和解题心得了, 题量也刷的不是很够.
标签：24,bfs,队列,return,...,SZTUACM,BFS,int,2023.1 From： https://www.cnblogs.com/lizsen/p/17020300.html