optimization - 查找使矩阵中的行唯一的列的最小子集

Question

什么是在离散值矩阵中找到列的最小子集的通用、有效的算法，使该行唯一。

例如，考虑这个矩阵(带有命名列):

A B C D
2 1 0 0
2 0 0 0
2 1 2 2
1 2 2 2
2 1 1 0

矩阵中的每一行都是唯一的。但是，如果我们删除列 a和 d我们保持相同的属性。

我可以枚举列的所有可能组合，但是，随着我的矩阵的增长，这将很快变得难以处理。是否有更快的最佳算法来执行此操作？

Answer 1

其实，我原来的配方不是很好。这是更好的设置封面。

import pulp

# Input data
A = [
    [2, 1, 0, 0],
    [2, 0, 0, 0],
    [2, 1, 2, 2],
    [1, 2, 2, 2],
    [2, 1, 1, 0]
]

# Preprocess the data a bit.
# Bikj = 1 if Aij != Akj, 0 otherwise
B = []
for i in range(len(A)):
    Bi = []
    for k in range(len(A)):
        Bik = [int(A[i][j] != A[k][j]) for j in range(len(A[i]))]
        Bi.append(Bik)
    B.append(Bi)

model = pulp.LpProblem('Tim', pulp.LpMinimize)

# Variables turn on and off columns.
x = [pulp.LpVariable('x_%d' % j, cat=pulp.LpBinary) for j in range(len(A[0]))]

# The sum of elementwise absolute difference per element and row.
for i in range(len(A)):
    for k in range(i + 1, len(A)):
        model += sum(B[i][k][j] * x[j] for j in range(len(A[i]))) >= 1

model.setObjective(pulp.lpSum(x))
assert model.solve() == pulp.LpStatusOptimal
print([xi.value() for xi in x])