algorithm - 将真/假向量分解成它的部分

Question

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

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

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

我还有一组其他列表，它们的长度与 X 相同，具有 true 和 false 值

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

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

Answer 1

您所描述的问题是 NP-hard 问题，通过减少 minimum set cover problem ，这是众所周知的 NP-hard。

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

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

希望这对您有所帮助!