2

如果这已在其他地方得到回答，我深表歉意，但我还没有使用我有限的算法术语找到它。;)

我的情况是这样的——我有可变数量的数据元素，每个数据元素都经过测试，以确定兼容性。兼容性存储在等效于二维数组（真值表？）中。我的目标是生成这些数据元素的所有可能组合，其中组合中的每个元素都与其他元素兼容。

例如，如果元素 1 (of 4) 与元素 2 和 4 兼容，元素 2 与 1、3 和 4 兼容，元素 3 与 2 兼容，元素 4 与 1 和 2 兼容，我的真值表将看起来像：

1) {1,1,0,1}
2) {1,1,1,1}
3) {0,1,1,0}
4) {1,1,0,1}

我想要的组合是：
1,2,4
1,2
1,4
1
2,3
2,4
2
3
4

我的方法在许多情况下都适用，但有时在元素数量超过 5000 时会陷入严重困境，具体取决于数据集。我的次要挑战是确定将执行时间从 5 秒增加到 3 小时的模式......

只看布尔数组，我就觉得肯定有一个更简单的解决方案——也许是一个以某人命名的算法。正如您可能从上面推断的那样，我不一定知道如何提出这个问题。;)

谢谢你的时间！

4

2 回答 2

4

我认为您拥有的是“邻接矩阵”而不是真值表，并且您正在寻找以邻接矩阵为代表的图形的所有“完全连接的子图”。如果没有记错的话，完全连接的子图也被称为“集团”。我不太确定您在寻找什么；正如一位较早的受访者表示的那样，您的文字和矩阵之间存在一些差异。

根据这些条款进行一些谷歌搜索；现在就在这里，我从我的脑海或图书馆中挖掘出这些东西已经太晚了。

请注意，您的图是对称的，即如果“1 与 2”兼容，则“2 与 1 兼容”必然。现在，您的数据存储需求减少了一半（使它们更加复杂，存储矩阵的上半部分或下半部分通常比它节省的空间更令人费解）。我还认为您可能应该在主对角线上使用 1，以表达“1 与 1 兼容”的想法。最终，我怀疑，你会有一些只与它们自己兼容的元素。

可悲的是，在图中查找派系是 NP，但对于只有 5000x5000 个元素的矩阵，在编译语言中，蛮力天真的算法不应该花费太长时间。

问候

标记

于 2009-08-19T22:33:17.623 回答
1

您基本上是在尝试将表达式简化为析取范式。一般来说，这个问题是NP完全的。对不起。^_^

于 2009-08-19T21:59:49.390 回答