寻找具有最大交集的子集组合

Question

假设我有一个包含n个集合的列表，有没有一种有效的方法来计算r个集合的组合，使得这些集合的交集大于列表中其他r个集合组合的交集？

特别是，我有一个由大约6000个字符串集合组成的列表，并且我想从该列表中选择大约9个集合，以便它们共享所有9个集合组合中最多的字符串。问题在于，如果我强制计算所有组合并查找最大交集，那么将需要（6000个选9个）约3e28次计算，因此我需要更有效的算法或一些可靠的启发式算法。

此外，如果可能的话，我还想扩展这个问题，选择一个变量r，使得任何组合的总元素大小都小于某个任意阈值，而不是选择一个常数r。也就是说，除了从6000个列表中选择9个集合以组成组合之外，该算法将添加字符串集合，直到组合中的字符串总数超过某个阈值，比如40个字符串。
这样做更接近我最初想要做的事情，但我意识到选择9个集合的固定大小会在我使用的列表上有相当不错的效果，并且可能会更容易实现，尽管最好能够实现这种算法。据我所知，这个问题类似于背包问题，尽管我知道解决它的唯一有效方法是使用动态规划，但我不确定在这种情况下如何实现动态规划，因为必须计算运行交集以获取权重，而不能像常规背包一样预先计算权重列表。

- Diego Tejada

Answer 1

这里有一个想法：

从6000个集合中随机选择9个集合。对于剩下的5991个集合，确定要替换哪个9个集合以最大化交集（如果新集合没有提供改进，则不使用新集合）。大约需要进行6000 * 9次操作。

重复上述步骤K次，并跟踪答案。然后找到出现最多次数的集合（获胜集合）。重复整个过程，但现在随机选择的起始集合必须包括获胜集合，且不能替换获胜集合。

重复直到8个9个集合都是获胜者。然后第9个集合就是最大化交集的任意集合。如果所有答案都相同，也可以提前终止。

运行时间大约为6000 * 9 * K * 8次操作，其中一次操作计算9个集合的交集。

- user3386109