algorithm - 找到最少数量的位序列 OR 来实现全 1？

Question

我正在尝试找到任何可能有助于完成此任务的方法:我有可变数量的位序列(它们各自的长度都相同)，我需要找到哪些序列组合会与所有 1 进行“或”运算，使用尽可能少的序列。我正在考虑从具有最多 1 的序列开始并尝试填充空白，但由于我没有使用位比较，我真的不知道是否有一些算法或位逻辑属性可以简化它。谢谢。

Answer 1

不幸的是，这个问题在大多数情况下是 NP-hard，通过从 set cover problem 减少 。在集合覆盖问题中，您有一个元素集合的集合，并且想要找到其中并集包含所有元素总数的最小数目。您可以通过为每个集合构造一个位向量来轻松地将集合覆盖问题简化为您的问题，如果给定集合具有该项目，则每个位置都有一个 1，否则为 0。其 OR 给出全 1 的最小数量的位向量则等于其并集包含所有元素的最小集合组。

例如，给定集合 {a, b, e}、{b, c}、{b, d, f} 和 {a, f}，您将得到这些位向量:

 {a, b, e}    110010
 {b, c}       011000
 {b, d, f}    010101
 {a, f}       100001

由于已知集合覆盖问题是 NP 难的，这意味着除非 P = NP，否则没有多项式时间算法可以解决您的问题。更糟糕的是，众所周知，您无法在多项式时间内在 O(log n) 的因数内逼近最佳解决方案，其中 n 是总元素数。您可能最好寻找启发式方法，或者使用 greedy algorithm 满足于 O(log n) 近似值。 .

希望这对您有所帮助!