php - 算法问题 : select two stories per topic so that the same story is never selected for two different topics

Question

在我的工作场所，我偶然发现了以下需要我解决的问题。尽管不是绝对需要，但首选解决方案。

有一个包含一组故事的数据库，每个故事都有一组与之关联的主题。主题存储在单独的表中，格式为 (storyid, topicid)。

问题是如何理想地选择 5 个主题(或至少 2 个，如果 5 个是不可能的)，以便每个主题有 2 个故事(或 1 个，如果 2 个是不可能的)，这些故事不会在任何其他选定主题中重复.该算法还必须返回与每个主题相关的确切“正确”故事。

这实际上是一个 NP 完全问题，没有超越所有可能性的简单枚举的有效解决方案，还是它有一个有效的解决方案？

如果没有高效解，请尝试证明(虽然不是绝对必要)。

如果确实有有效的解决方案，请善待并发布。

Answer 1

该问题的一个更一般的版本是为所有主题(或至少尽可能多的)选择两个故事，这样就不会为两个不同的主题选择相同的故事。

用S₁...S_m标记故事，用T₁...T_{n标记主题 。复制每个主题，即引入新故事T'1...T'n，其中T'i包含Sj 当且仅当 Ti 包含它。这个问题现在可以这样改写:为所有主题(或尽可能多的)选择一个不同的故事。获得主题故事对后，您可以再次加入重复的主题，每个主题将有两个故事。}

在不选择任何元素两次的情况下找到尽可能多的对的问题称为最大二分匹配问题。 (您可以将其视为从 bipartite graph 中选择最大数量的非连接边。)有一个称为增广路径的简单算法可以在 O((m+n)e) 步中解决它(e 是数字边缘)和一些更复杂的(例如 Hopcroft–Karp algorithm )，它们在大约 O((m+n)^2.5) 步内解决它。增广路径算法包括在图中搜索“交替”路径，其中路径的第一条边未被选中，第二条被选中，第三条未被选中，依此类推，而不是反转路径上的选择。这可能会适应您的情况，而无需实际进行主题的拆分和连接。

这有点矫枉过正，因为它将为所有主题返回两个故事，而不仅仅是五个；当您只需要查找有限主题的故事时，您可能会做得更好。 (除了一些边缘情况，你可以只选择故事数量最多的五个主题，丢弃它们不包含的故事，然后运行算法。)无论如何它表明问题远不是NP -很难。