知识卡片
剪枝必须证明后续不可能合法
若当前前缀已违反最终解必须满足的约束,可以停止这一整条分支,避免继续枚举不可能成立的后续。原书禁止路径经过值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 框架代码 接下来,我们尝试将回溯的“尝试、回退、剪枝”的主体框架提炼出来,提