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

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

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

这实际上是一个NP完全问题,没有简单的列举所有可能性的有效解决方案吗?还是有一个有效的解决方案?

如果它没有有效的解决方案,请尝试对其进行证明(尽管并非绝对必要)。

如果确实有有效的解决方案,请客气并张贴。

最佳答案

该问题的一个更一般的版本是为所有主题(或至少尽可能多)选择两个故事,以便从不为两个不同主题选择同一故事。

用S1 ... Sm标记故事,并用T1 ... Tn标记主题。复制每个主题,即介绍新的故事T'1 ... T'n,其中,当且仅当Ti包含Tj时,T'i包含Sj。现在可以通过以下方式解决问题:为所有主题(或尽可能多)选择一个不同的故事。一旦有了主题-故事对,就可以再次加入重复的主题,每个主题将有两个故事。

在从未两次选择任何元素的情况下找到最大对数的问题称为最大二分匹配问题。 (您可以将其视为从bipartite graph中选择最大数量的未连接边缘。)有一种简单的算法称为增强路径,可以以O((m + n)e)步(e为边缘数)求解它。 )和一些更复杂的方法(例如Hopcroft–Karp algorithm),可在O((m + n)^ 2.5)个步骤中解决。扩展路径算法包括在图中选择未选择路径的第一个边,第二个不选择第三个边的“替代”路径,等等,比对路径上的选择取反。这可能适合您的情况,而无需实际进行主题的拆分和合并。

这有点过头了,因为它将为所有主题返回两个故事,而不仅仅是五个。当您只需要查找有限主题的故事时,您可能会做得更好。 (除了某些极端情况,您可以选择故事数量最多的五个主题,丢弃其中不包含的故事,然后运行算法。)无论如何,这表明问题远非NP。 -难的。

10-07 15:39