5

问题

我正在研究 SAT 优化问题的一个特殊子集。对于那些不熟悉 SAT 和相关主题的人，这里是相关的 Wikipedia 文章。

TRUE=(a OR b OR c OR d) AND (a OR f) AND ...

没有非，它是合取范式。这很容易解决。但是，我试图最小化真实分配的数量，以使整个陈述成为真实。我找不到解决这个问题的方法。

可能的解决方案

我想出了以下方法来解决它：

  1. 转换为有向图并搜索最小生成树，仅跨越顶点的子集。有 Edmond 的算法，但它给出了完整图的 MST，而不是顶点的子集。
    • 也许有一个版本的 Edmond 算法可以解决顶点子集的问题？
    • 也许有一种方法可以从可以用其他算法解决的原始问题构建图形？
  2. 使用 SAT 求解器、LIP 求解器或穷举搜索。我对这些解决方案不感兴趣，因为我正试图将这个问题用作讲座材料。

问题

你有什么想法/意见吗？你能想出其他可行的方法吗？

4

1 回答 1

9

这个问题也是NP-Hard。

可以显示从Hitting Set向东减少：

命中集合问题：给定集合S1,S2,...,Sn和一个数字k：选择S大小的集合k，使得对于每个Si存在的元素都s在S其中。[替代定义：每个和之间的交集不为空]。sSiSiS

归约：
对于(S1,...,Sn,k)命中集合的实例，构造您的问题的实例：(S'1 AND S'2 And ... S'n,k)中S'i的所有元素在哪里Si，使用 OR。S'i 中的这些元素是公式中的变量。

证明：
Hitting Set -> 这个问题：如果有一个 hittins 集合的实例，S那么通过将所有S的元素赋值为 true，公式满足k元素，因为对于每个元素S'i都有一些变量v，因此S也Si在S'i.
This question -> Hitting set :S使用所有赋值为 true 的元素构建 [与 Hitting Set->This question 相同的想法]。

由于您正在为此寻找优化问题，因此它也是 NP-Hard，如果您正在寻找精确的解决方案 - 您应该尝试指数算法

于 2012-01-17T14:21:51.817 回答