知识卡片
奖惩权重编码约束
归约可用费用把合法选择与非法选择区分:从哈密顿环到旅行商时,原图边费用0、补边费用1,预算0使任何补边都无法出现在合格环中。
构造权重时,必须证明预算阈值恰好区分原问题的是非实例。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 奖惩权重编码约束
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Make big rewards and big penalties The strategy for reducing the hamiltonian-cycle problem with a graph G to the traveling-salesperson problem encouraged using edges present in G when choosing edges for the traveling-salesperson tour. The reduction did so by giving these edges a low weight: 0. In other words, we gave a big reward for using these edges.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[120000,125000))。
- 结论依据:原文归约策略、习题定义与脚注限定;图34.20–34.21已核对,习题未给出的证明不作既成结论。
- 原始内容:Make big rewards and big penalties The strategy for reducing the hamiltonian-cycle problem with a graph G to the traveling-salesperson problem encouraged using edges present in G when choosing edges for the traveling-salesperson tour. The reduction did so by giving these edges a low weight: 0. In other words, we gave a big reward for using these edges.