aka*_*sky 16 php mysql algorithm combinations selection
在我的工作场所,我偶然发现了以下需要解决的问题.尽管不是绝对必要的,但优选解决方案.
有一个包含一组故事的数据库,每个故事都有一组与之相关的主题.主题存储在表单(storyid,topicid)的单独表中.
问题是如何理想地选择5个主题(或至少2个,如果5个是不可能的),使得每个主题具有2个故事(或1,如果2是不可能的话),其在任何其他所选主题中不重复.该算法还必须返回与每个主题相关的"正确"故事.
这实际上是一个NP完全问题,没有有效的解决方案,超出了所有可能性的简单枚举,还是有一个有效的解决方案？
如果它没有有效的解决方案,请尝试证明它(虽然不是绝对必要).
如果它确实有一个有效的解决方案,请善待并发布.
该问题的更一般版本是选择所有主题(或至少尽可能多的)两个故事,以便从不为两个不同主题选择相同的故事.
用S 1 ... S m标记故事,用T 1 ... T n标记主题.重复每一个主题,那就是引入新的故事T" 1 ... T" ñ,其中T" 我其S Ĵ,当且仅当T 我包含它.现在可以通过这种方式重新解决问题:为所有主题选择不同的故事(或尽可能多地选择).获得主题 - 故事对后,您可以再次加入重复的主题,每个主题将有两个故事.
在从未选择任何元素两次的情况下找到最大数量的对的问题被称为最大二分匹配问题.(您可以将其视为从二分图中选择最大数量的非连接边.)有一种称为扩充路径的简单算法,它在O((m + n)e)步骤中解决它(e为边缘)和一些更复杂的(例如Hopcroft-Karp算法)在O((m + n)^ 2.5)步骤中解决它.增广路径算法包括在图中搜索"交替"路径,其中未选择路径的第一边缘,第二边缘,第三边缘不是,依此类推,而不是反转路径上的选择.这可能可能适合您的情况而不实际分割和加入主题.
这有点过分,因为它将为所有主题返回两个故事,而不仅仅是五个; 当你只需要为有限数量的主题找到故事时,你可以做得更好.(除了一些边缘情况,你可以选择故事数量最多的五个主题,丢弃它们未包含的故事,然后运行算法.)无论如何,它表明问题远非NP -硬.