同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2087_AL0933SAT问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 47| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504314155400-Problem List-采集的数据-后羿采集器.html

Pro.ID

2087

Title

AL093 3SAT问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2087

AC

Submit

Ratio

时间&空间限制

Time Limit: 1200/400 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

SAT的一个实例是k个布尔变量 x₁ ，…， x_k 的m个布尔表达式 A₁ ，…， A_m 。若存在各布尔变量 x_i ( 1 <= i <= k )的0，1 赋值，使每个布尔表达式 A_i ( 1 <= i <= m ) 都取值1，则称布尔表达式 A₁A₂ … A_m 是可满足的。
★ 合取范式的可满足性问题CNF-SAT
如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量x或~x。例如 ( x₁ + x₂) ( x₂ + x₃ ) ( ~x₁ + ~x₂ + x₃ ) 就是一个合取范式，而 x₁ x₂ + x₃ 就不是合取范式。
★ k-SAT
如果一个布尔合取范式的每个乘积项最多是k个因子的析取式，就称之为k元合取范式，简记为k-CNF。一个k-SAT问题是判定一个k-CNF是否可满足。特别地，当k=3 时，3-SAT 问题在NP完全问题树中具有重要地位。
★ MAX-SAT
给定k个布尔变量 x₁ ，…， x_k 的m个布尔表达式 A₁ ，…， A_m ，求各布尔变量 x_i ( 1 <= i <= k ) 的0，1 赋值，使尽可能多的布尔表达式 Ai 取值1。
★ Weighted-MAX-SAT
给定k个布尔变量 x₁ ，…， x_k 的m个布尔表达式 A₁ ，…， A_m ，每个布尔表达式 A_i 都有一个权值w_i，求各布尔变量 x_i ( 1 <= i <= k )的0，1赋值，使取值1 的布尔表达式权值之和达到最大。

对于给定的带权3-CNF，设计一个蒙特卡罗算法，使其权值之和尽可能大。