在二进制矩阵中准确找到 k 列的快速算法，这些列的总和是 1 向量

Question

假设我有一个 (M x N) 二进制矩阵，其中 M 和 N 都可以很大。我想精确地找到 k 列（k 相对较小，比如说小于 10），使得这些 k 列的总和是 1-向量（所有元素都是 1）。一种解决方案就足够了。有快速算法吗？

例如，在矩阵上工作的算法

k=2 应 return 列 0 和 2，但如果 k=1 或 k=3 则应报告无解。

我试过两种方法：

我尝试所有（N 选择 k）个组合并找到总和为 1 向量的组合的慢速组合方法。这在 O(N^k) 时间内运行，这显然是可怕的。
一种递归方法，速度更快但仍能在 O(N^k) 最坏情况下运行。 Python代码如下：

import numpy as np

def recursiveFn(mat, col_used_bool, col_sum_to_date, cols_to_go):
    N = len(mat)
    if cols_to_go == 1:
        col_unused = 1 - col_sum_to_date
        if list(col_unused) in [list(i) for i in mat]:
            return (True, [col_unused])
        else:
            return (False, None)
    for col_id in range(N):
        if col_used_bool[col_id]:
            continue
        if 2 not in mat[col_id]+col_sum_to_date:
            col_used_bool[col_id] = True
            x = recursiveFn(mat, col_used_bool, mat[col_id]+col_sum_to_date, cols_to_go-1)
            col_used_bool[col_id] = False
            if x[0]:
                return (True, x[1] + [mat[col_id]])
    return (False, None)

exMat = [[1,1,1,0],[0,0,1,1],[0,0,0,1]] #input by colums
exMat = [np.asarray(i) for i in exMat]
k = 2
output = recursiveFn(mat = exMat, col_used_bool = [False for i in exMat], 
    col_sum_to_date = np.asarray([0 for i in exMat[0]]), cols_to_go = k)
print(output[1])
### prints this : [array([0, 0, 0, 1]), array([1, 1, 1, 0])]

我对这两种方法都不满意，我觉得存在更智能、更快速的算法。非常感谢您的帮助。这是我在 Whosebug 上的第一个 post，所以如果我在某个地方失礼了，请对我温和一点！

（如果有兴趣，我也asked the same question on Math Stack Exchange，但我不太关心算法效率，更关心数学技巧。）

Answer 1

我的第一次尝试是 integer-programming using one of the available high-performance solvers (e.g. Cbc)。

假设在您的关联矩阵中 一些稀疏性 ，这些将非常有效并且非常普遍（边约束/适应）。它们也很完整，也许能够证明不可行性。

一个简单的公式如下：

Instance

c0 c1 c2
1  0  0  r0
1  0  0  r1
1  1  0  r2
0  1  1  r3

IP:

minimize(0)        # constant objective | pure feasibility problem

sum(c_i) = k       # target of columns chosen

r0 = 1 = c0        # r0 just showing the origin of the constraint; no real variable!
r1 = 1 = c0
r2 = 1 = c0 + c1
r3 = 1 = c1 + c2

c_i in {0, 1}      # all variables are binary

可能可以通过额外的不等式（例如 clique-inequalities（冲突图 -> maximal-cliques））来加强这个公式，但不确定这是否有帮助。好的求解器会动态地做一些类似的事情来生成削减。

有很多理论可用。一个关键字是 exact cover 或所有那些非常相似的 packing/covering 问题。

简单的代码示例：

import cvxpy as cp
import numpy as np

data = np.array([[1, 0, 0],
                 [1, 0, 0],
                 [1, 1, 0],
                 [0, 1, 1]])

def solve(k, data):
  c = cp.Variable(data.shape[1], boolean=True)

  con = [data * c == 1,
         cp.sum(c) == k,
         c >= 0,
         c <= 1]

  obj = cp.Minimize(0)
  
  problem = cp.Problem(obj, con)
  problem.solve(verbose=True, solver=cp.GLPK_MI)

  if(problem.status == 'optimal'):
    return np.where(np.isclose(c.value, 1.0) == True)[0]
  else:
    assert problem.status == 'infeasible'
    return None

print(solve(2, data))
print(solve(1, data))
print(solve(3, data))

# [0 2]
# None
# None

备注：

代码使用了非常强大的cvxpy，但缺少一些高级整数规划支持
- 唯一好用的非商业求解器是GLPK，非常好，但通常无法与Cbc竞争
- cvxpy 的非常代数用法以及一些接口决策导致不寻常的变量边界作为约束 公式

Answer 2

如第一个回答中所说，是一个Exact cover问题，属于NP-hard。解决 NP-hard 问题的经典方法是回溯。

在考虑回溯时，通常问题在于细节。不同的实现可以提供完全不同的结果。

历史上，Knuth 提出了 Algorithm X，这是一种递归的、非确定性的、深度优先的、回溯算法。

这个算法值得在这里测试

但是，由于只有少数 k 列要 selected，我会尝试另一种方法，即使用布尔值 [=12] 的经典回溯算法=] 指示列 j 是否 selected，还有两个额外的技巧。

将j列加到当前列总和时，只要遇到“2”就可以停止，不需要等到最后要计算的总和
我们可以将每一列的p个元素（对应p行）分组为一个整数，而不是一个一个地添加列元素，以加快列求和的过程。为此，我们需要 select 基础。小基数可以避免太大的数字（这对于限制 ``isValid[]` 数组的大小很重要，见下文）。

基数 2 是不可能的：例如将 (1 0) 和 (1 0) 相加将得到 (0 1)，这仍然是一个有效数字。

因此，我建议使用 base 3，它允许在求和期间检测是否存在错误的“2”。例如，

V(0 1 1 0) = 0*3**0 + 1*3**1 +1*3**2 + 0*3**3

在实践中，为了分析“p”个元素组，我们需要一个大小为“3**p”、isValid[] 的布尔值 table，这将允许立即检测是否给定得到的整数有效。这 table 必须在初始化阶段进行预处理。

我们知道当所有整数都等于特定值时我们已经获得了 1-vector (3**p - 1)/2，请注意最后一组可能具有不同的大小 p' < p.

由于n值较大，可以测试最后一个技巧：

为多行 n1 < n 寻找有效的解决方案，然后，对于获得的每个候选解决方案，检查它是否真的是所有 n 行的解决方案。

在二进制矩阵中准确找到 k 列的快速算法，这些列的总和是 1 向量

Fast algorithm to find exactly k columns in binary matrix such that the sum of those columns is the 1-vector

python

algorithm

performance

matrix

linear-algebra