搜索_解题技巧

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2.1k 阅读时长 ≈ 7 分钟

使用范围

DFS，深度优先搜索，寻找操作步骤字典序最小的解；白话文来说，就是能按序遍历所有情况

然而，DFS也是可以求最小解的：

  1. 用一个全局变量，记录最小值（打擂台）
  2. 迭代加深

BFS，广度优先搜索，找到步骤最小的解；白话文来说，就是递归/迭代次数最少的解

DFS

模板

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int k){//k代表递归层数，或者说要填第几个空
    if(所有空都填完了){
        判断最优解/记录答案;
        return;
    }
    for(枚举这个空能填的选项)
        if(这个选项是合法的){
            记录下这个空(保存现场);
            dfs(k+1);
            取消这个空(恢复现场);
        }
}

模板仅供参考，毕竟千变万化（我本人也不按照模板设计），核心编程思路有两点：

  1. 递归函数体内，每次处理的是当前的选项；下一次的情况丢给下一次递归就好

    若下一次递归的情况不符合题意怎么办呢？还往下递归吗？

    当然，函数体开头直接写相关的return语句，等下一次递归执行时，不就自动处理掉了嘛

  2. 根据题意判断是否要恢复现场。但基本上，都需要额外新建标记数组来记录解以及重复情况

    如果拿不定主意，千万不要省标记数组！！！会吃大亏！

练习题

BFS

模板

1
2
3
4
5
6
7
8
9
//Q是队列
Q.push(初始状态);//将初始状态入队
while(!Q.empty()){
    State u = Q.front();//取出队首
    Q.pop();//出队
    for(枚举所有可扩展状态)//找到u的所有可达状态v
        if(是合法的)//v需要满足某些条件，如未访问过、未在队内等
            Q.push(v);//入队(同时可能需要维护某些必要信息)
}

我基本也不按模板来...核心编程思路也有两点：

  1. 与DFS不同，BFS的函数体内每次处理的是下一次的选项！所以下一次的状态是否塞入队列，当前就要决定好！

  2. BFS为了避免死循环，也同样需要标记数组记录重复情况；比如该题

    二次强调，除非确实认定逻辑上不需要标记数组，否则一定要加上！多个数组才多少空间啊....

练习题

进阶搜索

根据边权情况分类即可：

  1. 问题只计最少步数，等价于在边权都为1的图上求最短路。

    使用普通的BFS，时间复杂度\(O\left( N \right)\)

    每个状态只访问（入队）一次，第一次入队时即为该状态的最少步数。

  2. 问题每次扩展的代价可能是0或1，等价于在边权只有0和1的图上求最短路。

    使用双端队列BFS，时间复杂度\(O\left( N \right)\)

    每个状态被更新（入队）多次，只扩展一次，第一次出队时即为该状态的最小代价。

  3. 问题每次扩展的代价是任意数值，等价于一般的最短路问题。

    1. 使用优先队列BFS，时间复杂度\(O\left( N\log N \right)\)。

      每个状态被更新（入队）多次，只扩展一次，第一次出队时即为该状态的最小代价。

    2. 使用迭代思想+普通的BFS（常用SPFA），时间复杂度\(O\left( N^2 \right)\)。

      每个状态被更新（入队）、扩展（出队）多次，最终完成搜索后，记录数组中保存了最小代价。

优先队列BFS

使用

其实就是Dijkstra和SPFA

练习题

双端队列BFS

使用

只能用在边权0或1的图上求最短路，和dijkstra完全一样的写法，只不过二叉堆换成了双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
memset(d, 0x3f, sizeof(d)), memset(vis, 0, sizeof(vis));
d[1] = 0, q.push_back(1);
while (!q.empty()) {
  int u = q.front();
  q.pop_front();
  if (vis[u]) continue;
  vis[u] = 1;
  for (int i = head[u]; ~i; i = g[i].nxt_) {
    int v = g[i].v_, w = g[i].w_ > mid;
    if (d[v] > d[u] + w) {
      d[v] = d[u] + w;
      if (w)
        q.push_back(v);
      else
        q.push_front(v);
    }
  }
}

练习题

双向BFS

使用

用以减少一半的搜索树深度，两个方向轮流做BFS，每次可以先选状态少的进行扩展；

注意！如果有无解情况，一定要先排除，否则复杂度会是普通BFS的两倍！

若要输出路径，反向BFS的方向数组千万记得取反！

正向方向数组为opa[4]={上，右，下，左}

反向方向数组应为opb[4]={下，左，上，右}

在反向BFS中，目标状态作为起点，中间状态作为终点；但客观上目标状态才是终点，中间状态是起点。

所以，在反向BFS的视角中，从目标状态朝中间状态向上移动；

客观上应该保存为从中间状态朝向目标状态向下移动！

如果双向BFS仍超时，只能考虑启发式搜索进行优化了。

练习题

迭代加深

使用

因为DFS的性质，无法像BFS一样很方便地找最少步骤解，要么就只能开一个全局变量打擂台并剪枝；

迭代加深就是模拟BFS，判断答案在第几层，异曲同工之妙。

练习题

  • poj-2248 模板题
  • poj-1167
  • poj-3700 贪心+迭代加深控制步数，非常好的题！
  • P1763 高难度剪枝，枚举分母所考虑的细节

双向DFS

使用

减少一半的搜索树深度

练习题

  • acwing-171 双向DFS模板题
  • CF525E 高难度的记忆化搜索优化
  • CF912E 优化双向DFS + 二分 + 双指针
  • P4799 和上面那题类似

Astar

使用

设当前状态为now，当前状态到目标状态的最小开销(理想值)为估价函数f(now)，初始状态到当前状态的开销为d[now]

每次取出最小的f(now) + d[now]进行扩展

与Dijkstra的大不相同！

除了目标状态之外，其余状态会重复出队入队，不能像Dijkstra那样只出队一次！

因为f(now) + d[now]是由两个变量共同组成，收敛性不一致；

且由于本身用了Dijkstra的贪心思想，所以不能用在负边权的图上！

适用于规模巨大的优先队列BFS题，一定要用估价函数来加快搜索进程否则会TLE的那种

练习题

IDAstar

使用

迭代加深+估价函数构成，

每次计算初始状态到当前状态的开销 + 当前状态到目标状态的最小开销(理想值，即估价函数)是否大于阈值，用以剪枝

练习题