algorithm - 找到方法测试矩阵(数学问题)解释的有效方法

Question

设置:

我有一个 bool 矩阵，例如

1  0
1  1
0  1

where rows are named m1, m2, m3 (as methods) and columns t1 and t2 (as tests).

Definition:

An explanation is a set of rows (methods) which in union have at least one "1" in any column (every test hast to be matched by at least one method).

in our example, the set of explanations would be:

{
  {m2}, 
  {m1,m2},{m1,m3},{m2,m3},
  {m1,m2,m3}
}

问题:

我现在想计算所有的解释。

现在，我已经有两种实现可以解决这个问题，一种是自上而下搜索解释，另一种是自下而上，但两者都在计算时间上呈指数增长(通过将行数增加一倍)。

这是一个已知的(可能有效解决的)数学问题吗？

让事情变得更简单的是，最后，我只需要每种方法在解释中出现的次数。在我们的示例中，这将是 m1 出现三次，m2 出现四次，m3 出现三次。

我当前的算法可以正常工作，直到假设 26 行。但进一步，它变得非常缓慢。

感谢您的帮助!

Answer 1

如果您可以满足于近似概率并想要可扩展的东西，吉布斯抽样可能会奏效。基本思想非常简单:从所有行的解释开始，然后重复以下内容以对一堆解释进行抽样。

1. 随机选择一行。
2. 掷硬币。
3. 如果硬币正面朝上，将这一行添加到解释中(如果已经存在，则什么也不做)。
4. 如果硬币反面朝上，尝试从解释中删除该行。如果结果不能解释，则将该行放回原处。

在极限情况下，包含给定行的样本分数会收敛到其真实值。在关键字“使用吉布斯采样的贝叶斯推理”下有一些实际的实现(你有一个统一的先验并观察到对于每一列，与它相关的行的析取是真实的)。不过，由于我不是这方面的专家，所以我无法就自己滚动的危险向您提出建议。