我有集合S_0，...，S_N。如何找到最大子集 T，使得 T 和 S_i 的交集 I_i(对于每个 0 <= i <= N) 最多包含一个元素。
我对此有一个解决方案，但我猜测它的速度不必要地慢(本质上是几个嵌套的 for 循环尝试所有组合)。所以我的问题是:
- 有没有一个有效的算法可以解决这个问题？
- 如果没有，是否有一种有效的算法可以找到大型子集
T？
最佳答案
我认为你不太可能找到一个有效的通用算法来解决这个问题，因为我相信它是 NP 完全的。
如果您有一个有效的算法来解决这个问题，那么您可以解决 maximum independent set problem .
证明草图
假设你有一个图，那么为每条边构造一个包含 {i,j} 的集合，其中 i 和 j 是由边连接的顶点。
然后这些集合的最大子集 T 将是您的图的最大独立集合。
转换为最大独立集
更有用的是，您还可以通过找到图形的最大独立集来表达您的问题，其中当且仅当存在一个同时包含 a 和 b 的集合时，a 和 b 之间才存在边。
然后，您可以使用一些标准求解器来解决最大独立集问题，例如 one in Pythons NetworkX .
关于algorithm - 集合中互斥项的子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19166144/