知识卡片
最大三合取满足数
MAX-3-CNF-SAT沿用三合取范式公式作为输入,但目标是找到使尽量多子句为真的变量赋值。
即使公式整体不可满足,也有可比较的最优满足子句数;它与问能否让所有子句为真的判定问题不同。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 最大三合取满足数
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
We call the resulting maximization problem MAX-3-CNF satisfiability. The input to MAX-3-CNF satisfiability is the same as for 3-CNF satisfiability, and the goal is to return an assignment of the variables that maximizes the number of clauses evaluating to 1. You might be surprised that randomly setting each variable to 1 with probability 1/2 and
参考来源
- 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[30000,35000))。
- 结论依据:第35章无三角约束旅行商、集合覆盖与随机近似、线性松弛的原文论证;图35.3已核对。
- 原始内容:We call the resulting maximization problem MAX-3-CNF satisfiability . The input to MAX-3-CNF satisfiability is the same as for 3-CNF satisfiability, and the goal is to return an assignment of the variables that maximizes the number of clauses evaluating to 1. You might be surprised that randomly setting each variable to 1 with probability 1/2 and