进阶搜索算法 学习笔记
进阶搜索算法
前情提要～
- 双向广搜、双向深搜
- 堆优化的 Dijkstra
- 一颗小小的 A-STAR
- 不大聪明的 IDDFS（IDS）
- 可爱的 IDA-STAR
广搜、深搜
这是进阶搜索算法，不说了直接上例题
以“P1514 引水问题”为例：https://www.luogu.com.cn/paste/zo5e6pal
双向广搜、双向深搜
算法思想
- 在搜索的时候，搜索出来的树太大了
- 从起始状态和目标状态同时开始搜索一定层数
- 把搜索出来的所有状态扔到 hash 表里面，看看有没有重复的
- 能够提升一倍答案的效率，比如原来复杂度是 $O(2^n)$，现在可以变成 $O(2^{n / 2})$，相当于复杂度开根号
代码
以“U319719 八城堡问题”为例：https://www.luogu.com.cn/paste/uicfza9m
堆优化的 Dijkstra
算法思想
考虑当前走过的距离，不考虑剩下的距离，当前走的少的优先考虑
优先队列里不允许出现相同的元素，但是同一个元素可以入队和出队多次，当第二及更多次入队是，必然是遇到了更加优化的路径（到起点的距离更近）
代码
以“P3371 P4779 单源最短路径”为例：https://www.luogu.com.cn/paste/vzupxcqq
一颗小小的 A-STAR
基础知识
- 估价函数 $f(i) = g(i) + h(i)$，每次要选取 $f(i)$ 最小的更新
- $g(i)$：从起始状态到当前状态 $i$ 的代价
- $h(i)$：从当前状态 $i$ 到目标状态的估计代价
基础思想
好东西：https://zhuanlan.zhihu.com/p/54510444
重点在设计估价函数，估价函数 $h(i)$ 若选取不当，则可能找不到解，或找到的解也不是最优解。
- 定义 $h^*(i)$ 为从当前状态 $n$ 到目标状态的实际代价
- 必须满足 $h(i) \le h^*(i)$，否则嘿嘿嘿
- 估计总是过于乐观的
常见的估价函数
对于网格形式的图，有以下这些启发函数可以使用：
- 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * (dx + dy)
- 如果图形中允许朝八个方向移动，则可以使用对角距离
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
// 这里的D2指的是两个斜着相邻节点之间的移动代价
- 如果图形中允许朝任何方向移动，则可以使用欧几里得距离
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * sqrt(dx * dx + dy * dy)
- 对于类似八数码问题的，可以使用各数码使用距离目标位置的曼哈顿距离之和
int f(string state)
{
int res = 0;
for (int i = 0; i < 9; ++i)
{
if (state[i] != '0')
{
int t = tar[state[i] - '1'];
res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
}
}
return res;
}
- 对于数列（二维也可以）问题的，可以使用有多少个元素位置不正确，或其前驱、后继不正确
int f(string state)
{
int res = 0;
for (int i = 0; i < 9; ++i)
res += state[i] != gend[i];
return res;
}
int f()
{
int res = 0;
for (int i = 0; i + 1 < n; ++i)
if (q[i + 1] != q[i] + 1)
++res;
return (res + 2) / 3;
}
设计要求
- 不要太过分就好，一般来说没问题的
- 脑洞要大
代码
以“P1379 八数码问题”为例：https://www.luogu.com.cn/paste/9olegdye
不大聪明的 IDDFS（IDS）
算法思想
迭代加深是一种每次限制搜索深度的深度优先搜索，目的是寻找最优解。
- 给出一个限制 limit，规定：当 搜索层数 > limit 时直接剪枝
- 在最外层 循环枚举 limit，如果无解就继续
特点
缺点：重复计算
与BFS的区别：BFS 的基础是队列，空间复杂度大，当状态比较多或者单个状态比较大时，迭代加深就类似于用 DFS 方式实现的 BFS，空间复杂度相对较小。
在大多数的题目中，广度优先搜索还是比较方便的，而且容易判重。当发现广度优先搜索在空间上不够优秀，而且要找最优解的问题时，就应该考虑迭代加深。
代码
以“LOJ10021 Addition Chains（加成序列问题）”为例：https://www.luogu.com.cn/paste/y81dwnc5
可爱的 IDA-STAR
算法思想
IDA-STAR 为采用了迭代加深（IDDFS）算法的 A-STAR 算法。
所以，在一般的问题中是这样使用 IDA-star 算法的：
- （类似 IDDFS）循环枚举 limit，当$h(i) + g(i) >$ limit 时, 就停止继续往下搜索
- 写成代码就是：
if depth + h() > limit then return; - 没了
估价函数
往上门口（见 A-STAR）
特点
- 省空间：各种游戏求最少步数，普通搜索会爆炸
- 省时间：不需要判重，不需要排序，利于深度剪枝
- 费时间（？）：每次深度变大都要再次从头搜索，有时可能双向广搜会更快
代码
以“P2324 骑士精神”为例：https://www.luogu.com.cn/paste/71rlu8wf
题单推荐
- https://www.luogu.com.cn/training/348219（来自我老师 QwQ）
部分资料来源
- https://github.com/huzecong/oi-slides
- https://zhuanlan.zhihu.com/p/54510444
- https://oi-wiki.org/
- https://www.acwing.com/