我问的最小成本最大流量several weeks ago。克拉斯凯维奇的回答很聪明,解决了我的问题我已经implemented it了,它工作得很好(抱歉,只能用法语)此外,该算法还可以为每个学生分配i(i>1)个项目。
现在我在尝试更困难的事情。我想增加选择的限制如果有人想影响每个学生的i(i>1)项目,我希望能够指定哪些项目是兼容的(彼此)。
在某些项目不兼容的情况下,我希望算法返回全局最优,即将I项目影响到每个学生,最大化全局幸福和评估兼容性约束。
将i乘以原始方法(并在每个步骤检查约束)将没有帮助,因为它只会返回局部最优值。
对正确的图表有什么想法吗?

最佳答案

不幸的是,它在多项式时间内是不可解的(除非P = NP或有附加约束)。
这里是从最大独立集问题(已知为NP完全)的多项式时间减少到这一点:
给定图形G和数字k,请执行以下操作:
为图中的每个顶点创建一个项目G,并说如果G中的相应顶点之间有一条边,则两个项目不兼容。
创建一个同样喜欢每个项目的学生(我们可以假设每个项目给他的快乐等于1)。
使用一个算法来解决最大的幸福,解决你的问题中所陈述的问题。我们称之为h
如果一组项目都是相容的,则可以选择它们,这意味着G的所选顶点形成一个独立的集(由于我们构造图的方式)。
因此,h等于最大独立集的大小。
返回h >= k
这在实践中意味着什么这意味着寻找这个问题的多项式时间解是不合理的。有几件事可以做:
如果输入很小,可以使用穷举搜索。
如果不是,你可以使用启发式和/或近似来找到一个相对好的解决方案(虽然不是必要的最佳方案)。

关于algorithm - 影响m个学生到n个组,但有限制?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/29099158/

10-08 22:00
查看更多