我正在尝试找到任何可能对这项任务有帮助的东西：我有可变数量的位序列（它们都将具有相同的长度），并且我需要使用尽可能少的方法找到哪个序列组合将 OR 到所有 1尽可能的顺序。我正在考虑从具有最多 1 的序列开始并尝试填充空白，但由于我没有使用位比较，我真的不知道是否有一些算法或位逻辑的属性可以简化这一点。谢谢。
问问题
190 次
2 回答
4
不幸的是，这个问题在最一般的情况下是 NP 难的，因为它是从集合覆盖问题中减少的。在集合覆盖问题中，您有一组元素的集合，并且想要找到其中最小数量的集合，其并集包含所有元素。您可以通过为每个集合构造一个位向量来轻松地将集合覆盖问题简化为您的问题，如果给定集合具有该项目，则在每个位置具有 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 是多项式时间内的总元素数。您最好寻找启发式方法，或者使用贪心算法保持 O(log n) 近似值。
希望这可以帮助！
于 2012-08-02T22:47:37.697 回答
0
我想了一下这个问题，这是我想出的想法：
首先，您为每个位创建一个列表，并且在每个列表中，您会发现在该位上具有“1”的每个序列。这需要 O(n*m)，因为 n 是序列的数量，m 是特定序列的长度
然后你计算每个位序列的所有出现次数，并将所有这些 [List, Integer] 元组放入一个结构（AVL 树或堆或任何你喜欢的）中并对它们进行排序。（我的意思是：序列“a”在所有列表中出现 15 次，序列 b 出现 10 次）。这又需要 O(n*m) 因为 O(nlogn) < O(n*m)
在下一步中，您使用具有最高优先级的序列并删除包含此序列的第一步的所有列表。然后返回第 2 步，直到消除所有列表。在最坏的情况下，您将不得不这样做 m 次。
因此，我们总共有 O(n * m^2) 的时间，如果您误解了问题的一部分或我做错了，请纠正我；）这是我的意思的一个小例子：
位字符串：
a： 100101
b: 010001
c: 011100
d: 000010
所以这将创建列表：
L1：a
L2：b，c
L3：c
L4：a，c
L5：d
L6：a，b
然后我们将计数和排序：
a：3
c：3
b：2
d：1
所以我们在最终列表中取 a 并删除以下列表：
L1、L4、L6
现在我们再次数：
c:2
b:1
d:1
所以我们在列表中取 c 并删除：
L2, L3
所以我们只剩下 L5 只包含 d
所以我们找到了最终的最小集合：a, c, d
于 2012-08-03T01:52:56.253 回答