浅记搜索
Silent_E
·
·
个人记录
\text{蒟蒻的搜索总结}
\text{搜索，必不可少的骗分技巧}
什么是搜索？
$\ \ \ \ \ \ \ $表面上，搜索是一种暴力，但如果它能与‘回溯’，‘剪枝’，甚至‘乐观估价函数(IDA*)’一起运用，搜索的效率将会很高。
搜索一般有固定的模板，分类主要分为：深度优先搜索，广度优先搜索，迭代深搜，记忆化搜索，IDA*。其中后三种主要建立在深搜的基础上。
- ### 深度优先搜索（DFS）
**思想：一直往深处走，直到找到解或者走不下去为止。**
实现：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
常用模版：
```cpp
void dfs(int k,其他参数)
{
if(到目的地)输出解;
else for(i=1;i<=算符种数;i++)
if(满足条件) {
保存结果;
//do something
dfs(k+1);
恢复：保存结果之前的状态（回溯）
//一般的DFS都需回溯到上一个状态
}
}
```
**注意：**
1. 尽量保证框架完整。
2. 时刻提醒自己是否可以剪枝。（最优化剪枝||可行性剪枝）
3. 打标记已经出现过的状态。
4. 需要回溯的地方不要忘了回溯。
- ### 广搜，宽搜（BFS）
**思想：总是先搜索距离初始状态近的状态。**
实现：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。
```cpp
void bfs(){
初始化，初始状态存入队列；
队列首指针head=0; 尾指针tail=1；
while(head<tail){ 队列为空
指针head后移一位，指向待扩展结点；
for (int i=1;i<=max;++i) //max为产生子结点的规则数
{
if (子结点符合条件)
{
tail指针增1，把新结点存入列尾；
if (新结点与原已产生结点重复) 删去该结点（取消入队，tail减1）;
else
if (新结点是目标结点) 输出并退出；
}
}
}
}
```
**注意：**
1. 每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪（递归），找到从根结点到目标结点的一条路径。当然如果不要求输出路径，就没必要记父亲。
2. 生成的结点要与前面所有已经产生结点比较（俗称打标记），以免出现重复结点，浪费时间和空间，还有可能陷入死循环。
3. 如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用广度优先搜索；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。
4. 广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。
- ### 迭代深搜
**类似于广搜的思想，但在一般情况下，迭代深搜快于广搜（貌似？）。用深搜框架，限制每次搜索层数。**
```cpp
void dfs(答案,搜索层数,其他参数){
if(层数==maxdeep){
更新答案;
return;
}
(剪枝)
for(枚举下一层可能的状态){
更新全局变量表示状态的变量;
dfs(答案+新状态增加的价值,层数+1,其他参数);
还原全局变量表示状态的变量;
}
}
```
- ### 记忆化搜索
~~知道有这东西就行了QAQ~~。大体思路是存储每一步的结果，确保后面的调用，速度起飞。（DP的递归版）
- ### IDA*
一个神奇的算法。
# 编辑中。。。例题扩充中。。。