知识卡片

普通读书笔记卡 · 3714.b.8.b

奖惩权重编码约束

理解等级:中级

归约可用费用把合法选择与非法选择区分:从哈密顿环到旅行商时,原图边费用0、补边费用1,预算0使任何补边都无法出现在合格环中。

构造权重时,必须证明预算阈值恰好区分原问题的是非实例。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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.