0Pricing
Competitive Programming Academy · 课时

剪枝以应对时间限制

剪去无法改进结果的分支

剪枝以应对时间限制 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

为什么剪枝很重要

原始的回溯可能会探索过多分支，甚至超过时间限制。剪枝会尽早切断没有希望的分支，让程序保持快速。✂️

剪枝的真正含义

剪枝是指一旦能够证明某个分支无法得到有效答案或更优答案，就立即停止该分支。您可以完全跳过对它的探索。

可行性剪枝

如果当前的部分选择已经违反规则，请立即返回。这个可行性检查可以避免在错误状态的基础上继续构建。

if violates(cur):
    return

界限剪枝

请记录目前找到的最佳答案。如果某个分支所能达到的最佳结果仍然更差，就将它剪掉。这就是该分支的上界。

在代码中剪枝

这里的上界会在即使采用乐观估计也无法超过当前最佳结果时停止该分支。

if cur_cost + best_possible <= best:
    return

合理安排选择顺序

先尝试最有希望的选项，可以更早找到一个好答案，从而提高上界，并在之后剪掉更多分支。

约束传播

做出选择后，请缩小后续步骤可以执行的范围。提前移除不可能的选项就是约束传播，它可以缩小搜索树。

破除对称性

如果两个分支互为镜像，只需探索其中一个。对称性破除可以在不遗漏答案的情况下，将工作量减少一半甚至更多。

记忆化重叠状态

如果相同的部分状态再次出现，请缓存它的结果。记忆化会将重复的子树变成一次快速查找。

from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
    ...

尽早剪枝，而不是最后剪枝

请在递归之前检查剪枝条件，而不是在递归之后检查。提前剪枝可以避免扩展注定失败的分支所造成的无用工作。

运行前先估算

请始终根据约束合理检查最坏情况下的分支数量。如果数量太大，您就需要更强的剪枝或采用新方法。

快速检查

回溯中的剪枝目标是什么？

回顾：切断无效分支

您学会了使用可行性检查和上界检查、合理排序、破除对称性以及记忆化来进行剪枝，从而应对时间限制。🎯

常见问题解答

「剪枝以应对时间限制」课时是免费的吗？

是的 — 「剪枝以应对时间限制」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「剪枝以应对时间限制」这节课中我会学到什么？

剪去无法改进结果的分支 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「剪枝以应对时间限制」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 递归思考：基础情况与递归
  2. 生成所有子集
  3. 排列与 N 皇后思想
  4. 剪枝以应对时间限制
← 返回 Competitive Programming Academy