algorithm - 集合中互斥项的子集

Question

我有套S_0, ..., S_N。如何找到最大的子集T，使得和（对于每个 0 <= <= N）I_i的交集最多包含一个元素。TS_ii

我对此有一个解决方案，但我猜测它不必要地慢（基本上是几个嵌套的 for 循环尝试所有组合）。所以我的问题是：

• 有没有解决这个问题的有效算法？
• 如果没有，是否有找到大子集的有效算法T？

Answer 1

我认为你不太可能找到一个有效的通用算法来解决这个问题，因为我相信它是 NP 完备的。

如果你有一个有效的算法来解决这个问题，那么你可以解决最大独立集问题。

证明草图

假设你有一个图，然后为每条边构造一个包含 {i,j} 的集合，其中 i 和 j 是由边连接的顶点。

那么这些集合的最大子集 T 将是您的图形的最大独立集。

转换为最大独立集

更有用的是，您还可以通过为图找到最大独立集来表达您的问题，其中 a 和 b 之间存在边，当且仅当存在一个同时包含 a 和 b 的集合时。

然后，您可以使用一些标准求解器来解决最大独立集问题，例如Pythons NetworkX 中的求解器。

Answer 2

S_a您可以通过缓存集合的交集和S_b是否为空来加速您的程序。而不是构建T我认为是中一些集合并集的集合S。您保留T集合索引的列表，并检查一个集合是否S_n与您相交，T检查表中的集合T是否S_n与其中一个相交。

我在我的一个 Python 程序中这样做了，因为设置交集测试是慢点。