將學生劃分爲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）