4

我想知道这是否是一个既定的计算机科学问题，是否有任何多项式时间解或近似

假设我有一些由真值和假值组成的列表 X

X = [True, False, True, False, True...True]

我还有一组与 X 长度相同的其他列表，具有真值和假值

A = [False, True, True, True, True, False .... False]
B = [False, False, True, False, True, False .... False]
...etc

现在，我想找到这些其他列表的“总和”（将按位 OR 运算符应用于每个元素。即 F + F = F 、 F + T = T 、 T + T = T ）最能解释在列表 X 中看到的观察结果（我可以引入一个评分系统，它会为匹配给出一些分数，并对解决方案中的不匹配进行惩罚），并且由于可能有许多可能的解决方案，我想对算法施加惩罚它在其解决方案中使用的更多列表。

4

1 回答 1

5

您所描述的问题是 NP-hard 通过减少最小集覆盖问题，已知是 NP-hard。

减少如下。给定一个包含 n 个元素的集合 S，创建一个包含 n 个“true”副本的列表作为您的列表 X。然后，对于集合封面中可能允许的每个集合，将其替换为在每个位置具有 true 或 false 的列表基于集合是否包含 S 的给定元素。如果将无穷大的惩罚分配给不匹配并将成本分配给每个列表，则原始集合中存在大小为 k 或更小的集合覆盖设置覆盖问题当且仅当您的问题有成本 k 或更少的解决方案。

这意味着对于这个问题没有已知的多项式时间算法，您将需要接受近似答案或愿意让您的程序在某些输入上运行很长时间。

希望这可以帮助！

于 2013-01-15T17:21:59.310 回答