更有效的算法来查找两组的OR

Question

给定's和's 的n行和m列矩阵,需要找出可以选择的行对的数量,以便它们是.10OR11111....m times

例:

1 0 1 0 1
0 1 0 0 1
1 1 1 1 0

回答:

2 ---> OR of row number [1,3] and [2,3]

鉴于n并且m可能是一个订单<= 3000,这个问题的解决效率如何？

PS:我已经尝试过一种天真的O(n*n*m)方法.我在考虑一个更好的解决方案.

Answer 1

1. 简单的解决方案 简单的算法（您已经发现但没有发布）是采用所有（n选择 2）n行的组合，或它们，然后看看它是否有效。这是O(n^2 * m)。编码如下：

for (i = 0; i < n; ++i)
  for (j=i+1; j < n; ++ j) {
    try OR of row[i] with row[j] to see if it works, if so record (i,j)
  }

2. 恒定加速 通过将位打包到字中，可以将运行时间缩短一个字大小的倍数。这仍然给出相同的渐近，但实际上在 64 位机器上有 64 位加速倍数。这已经在上面的评论中指出了。

3.启发式加速 我们可以在实践中做启发式来进一步提高时间，但没有渐近保证。考虑按汉明权重对行进行排序，最小的汉明权重在前面，最大的汉明权重在最后（运行时间O(m * n * log m )）。然后，您只需比较低权重行和高权重行：具体来说，权重需要为>= m。然后搜索看起来像这样：

for (i = 0; i < n; ++i)
  for (j=n-1; j > i; --j) /* go backwards to take advantage of hmwt */
  {
    if ( (hmwt(row[i]) + hmwt(row[j])) < m)
      break;
    try OR of row[i] with row[j] to see if it works, if so record (i,j)
  }

4. 寻求更好的方法 另一种可能提供更好回报的方法是选择低汉明权重的列。然后将这些行合并为两组：该列中包含 1 的行（A 组）与该列中包含 0 的行（B 组）。然后，您只需要考虑行的组合，其中一个来自 A 组，另一个来自 B 组，或者两者都来自 A 组（感谢 @ruakh 发现我的疏忽）。沿着这些思路的一些东西应该会有很大帮助。但这仍然是渐近相同的最坏情况，但在实践中应该更快（假设我们不是所有组合都是答案的情况）。

5. 可以做的事情的限制 构造例子很容易，其中有效的向量对的数量是O(n^2)，因此感觉很难击败O(m*n^2) 最坏的情况。我们应该寻求的是一个与有效配对数量在某种程度上相关的解决方案。上面的启发法就是朝着这个方向发展的。如果有一列汉明权重较小h，则上述第 4 点会将运行时间缩短为O(h*n*m + h^2*m)。如果h显着小于n，那么您将获得很大的改进。