c++的搜索剪枝

常规
1

今天，咱来讲一下搜索剪枝喵！
用一句话来说剪枝就是：“感觉不对，立马撤退；发现最优，剩下丢掉！”

1. 把它想象成“侦探破案”的故事

这次，我们的主角是一位经验丰富的“名侦探”。他在一棵巨大的“线索树”上推理，寻找那个唯一的真凶（或最优解）。 但这棵树的树枝太多了（有成千上万种可能性），如果一根根往死里查，案子没破，侦探就先老死了。

这时候，侦探掏出了他的武器——“大剪刀（剪枝条件）”。他是这样破案的：

  • 第一招：可行性剪枝： 侦探顺着一根线索往下查，走到一半，发现前面的桥断了（不符合题目边界/需要的道具不够了）。正常人会走到桥边再回头，但精明的侦探会想：“既然前面定是死路，我往下干嘛啊！”于是掏出剪刀，把这根树枝后面的所有延伸直接剪掉，立刻回头！
  • 第二招：最优性剪枝： 侦探的目标是花最少的时间找到真凶。在第一轮推理中，他找到了一种用一天的方案（当前最优解）。在第二轮推理时，他才走到一半，过去的时间就已经达到了一天半。侦探冷笑一声：“后面就算分文不花，总数也已经超过一天了，后面的路不看了！”掏出剪刀，又省下了大把时间。

这就是剪枝：在搜索（DFS/BFS）的过程中，只要发现当前方向绝对不可能诞生正确答案/最优解，就立刻强行中止。 这种把无用搜索砍掉的操作，就叫剪枝。

2. 剪枝的优缺点喵

  • 优点（速度起飞，逆天改命）： 它是让普通程序从超时走向满分的外挂！有时一个精妙的剪枝，能把计算量从几亿次瞬间变成几千次，直接降维打击。
  • 缺点（脑细胞杀手）： 非常考验你的观察力。如果剪枝条件写错了，就会导致程序漏掉正确答案喜提WA。

3. C++ 代码长什么样？

剪枝在代码里，通常体现为写在函数最开头的那几句冷酷的 if 语句。 看一个极简的代码骨架：

`C++// 侦探从当前状态（当前时间time，当前位置pos）开始推理

void dfs(int pos, int time) {
 // 【可行性剪枝】
 if (不合法(pos) || 能量耗尽(pos)) {
   return; // 桥断了，或者走不出去了，果断放弃！
 }
 // 【最优性剪枝】
 if (time >= best_ans) {
   return; // 已经比之前找到的最好方案还要差，后面不用看了，剪掉！
 }
 // 成功抓到真凶/到达终点
 if (pos == target) {
   best_ans = min(best_ans, time); // 刷新我们的最好纪录
   return;
 }
 // 继续向下一层推理
 for (int i = 0; i < 各种选择; i++) {
   dfs(下一个位置, time + 消耗);
 }
}

最后小结：

  • 不剪枝的搜索： 愚公移山，明知山有虎，偏向虎山行（容易 TLE 喵）。
  • 带剪枝的搜索： 步步为营，发现苗头不对迅速止损，只走最聪明的路。
1 个赞