知识卡片

普通读书笔记卡 · 5654.c.4.a

剪枝必须证明后续不可能合法

理解等级:中级

若当前前缀已违反最终解必须满足的约束,可以停止这一整条分支,避免继续枚举不可能成立的后续。原书禁止路径经过值3节点,因此一到3就可剪掉其全部后代路径。

剪枝不是因为目前看起来差就随意放弃;必须说明任何后续选择都无法修复违反的条件。启发式优先尝试较有希望的分支,可以改善搜索次序,但若省略其他分支,就不能自动声称仍保证最优或全解。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      避免许多无意义的尝试,从而提高了搜索效率。 第13 章 回溯 hello‑algo.com 283 图13‑3 根据约束条件剪枝 13.1.3 框架代码 接下来,我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来,提

    参考来源

    - 位置:《Hello 算法--Go版本》第13章《回溯》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[21932,22042)) - 结论依据:实际路径禁止3条件和剪枝解释,后文启发式区别保持完整性前提。 - 原始内容:避免许多无意义的尝试,从而提高了搜索效率。 第13 章 回溯 hello‑algo.com 283 图13‑3 根据约束条件剪枝 13.1.3 框架代码 接下来,我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来,提