将真/假向量分解为其部分

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

现在,我想找到这些其他列表的'总和'(将按位OR运算符应用于每个元素...即F + F = F,F + T = T,T + T = T),这最好地解释了在列表X中看到的观察结果(我可以引入一个评分系统,给出匹配的一些分数和解决方案中不匹配的惩罚),并且由于可能存在许多可能的解决方案,我想对算法施加惩罚.它在解决方案中使用的更多列表.

Answer 1

你所描述的问题是通过从最小集合覆盖问题的减少来实现NP难度,这个问题被称为NP难度.

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

这意味着没有已知的多项式时间算法来解决这个问题,您需要接受大概的答案,或者愿意让程序在某些输入上运行很长时间.

希望这可以帮助!