将学生划分为N组的算法

Question

我想将M个学生分成N组。这并不难，但有一些限制。

1.约束：（A，B）一对学生必须在一组中。这意味着学生A想与学生B在同一个小组中。

2.约束：（A，B）一对学生（studentA和studentB）不得在一个组中。

我有M个学生，并希望通过这个约束创建N个组。如果不可能将它们分开，找到最少的违反约束条件的解决方案。

任何想法如何解决它的算法？

Answer 1

你可能会觉得这是一个有用的想法graph colouring problem。该链接包含各种建议的算法。

顶点代表学生，颜色代表不同的组。

顶点之间的边表示那些学生想要在不同的组中。如果学生想要在同一组中，只需合并顶点。

不幸的是，把学生逼到3组，即使这证明了你的问题是NP难（因为你可以用它来寻找一个三色图 - 而这个问题是NP-complete）