algorithm - 将 m 个学生影响到 n 个组，但有限制？

Question

我问的是最小成本最大流量several weeks ago . Kraskevich 的回答非常出色，解决了我的问题。我有 implemented it而且效果很好(抱歉，仅提供法语版本)。此外，该算法可以处理分配给每个学生的 i(i> 1)个项目。

现在我正在尝试更困难的事情。我想添加对选择的限制。如果有人想要影响每个学生的 i(i> 1)个项目，我希望能够指定哪些项目(彼此)兼容。

在某些项目不兼容的情况下，我希望算法返回全局最优值，即影响i 项目给每个学生最大化全局幸福和 repecting兼容性约束。

将原始方法链接 i 次(并在每一步检查约束条件)无济于事，因为它只会返回局部最优值。

关于要使用的正确图表有什么想法吗？

Answer 1

不幸的是，它在多项式时间内不可解(除非 P = NP 或有额外的约束)。

这是从最大独立集问题(已知是 NP 完全问题)到这个问题的多项式时间缩减:

给定一个图 G 和一个数字 k，执行以下操作:

1. 为图 G 中的每个顶点创建一个项目，并说两个项目不兼容，当且仅当 G 中对应的顶点之间有一条边。

2. 创建一个对每个项目都同样喜欢的学生(我们可以假设每个项目给他的快乐等于1)。

3. 使用解决问题中所述问题的算法找到最大的幸福感。我们称它为h。

4. 一组项目可以被挑选，当且仅当它们都是兼容的，这意味着 G 的挑选顶点形成一个独立的集合(由于我们构建图的方式)。

5. 因此，h等于最大独立集的大小。

6. 返回h >= k。

这在实践中意味着什么？这意味着寻找这个问题的多项式时间解是不合理的。有几件事可以做:

1. 如果输入较小，可以使用穷举搜索。

2. 如果不是，您可以使用试探法和/或近似法来找到相对较好的解决方案(但不一定是最佳解决方案)。