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

Question

假设我有一个 n 集合的列表，是否有一种有效的方法来计算 r 集合的组合，其交集大于 的任何其他组合r 集合在列表中？

特别是，我有一个包含大约 6000 组字符串的列表，我想从此列表中选择大约 9 组，以便它们在 9 组的所有组合中共享最多的字符串。问题是，如果我要对其进行蛮力计算并计算所有组合并寻找最大交集，它将需要(6000 选择 9)〜 3e28 计算，所以我需要更有效的算法或一些可靠的启发式。

此外，如果可能的话，我想将这个问题扩展到选择一个变量 r 使得任何组合的总元素大小小于某个任意阈值，而不是选择一个恒定 r。也就是说，算法不是仅从 6000 个列表中选择 9 个集合来进行组合，而是添加字符串集合，直到组合中的字符串总数超过某个阈值，比如 40 个字符串。
这更接近我最初想要做的事情，但我意识到采用 9 组的恒定大小组合对于我正在处理的列表来说有点体面，并且可能更容易实现，尽管一个算法可以实现这一点将是可取的。据我所知，这个问题类似于背包问题，尽管我知道解决这个问题的唯一有效方法是使用动态规划，而且我不确定在这种情况下我将如何实现动态规划，因为我必须计算运行交叉路口来获取权重，而不是像常规背包那样具有预先计算的权重列表。

Answer 1

这是给你的一个想法:

从 6000 组中随机选择 9 组。对于剩余的 5991 组，确定要替换这 9 组中的哪一组以最大化交集(或者如果新组没有提供改进，则不要使用它)。这大约是 6000 * 9 次操作。

这样做 K 次，跟踪答案。然后找到出现在大多数答案中的集合(获胜集合)。重复整个过程，但现在随机选择的起始组必须包含获胜组，并且获胜组不能被替换。

重复直到 9 组中有 8 组获胜。然后第 9 组是使交集最大化的任何一组。如果所有答案都相同，您也可以提前终止。

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