根據偏好分組

Question

我試圖帶一組20個人（標記爲1 - 20），並將它們分成五個子組，每個子組基於這些人希望與之相關的表達偏好。

20人組中的每個人可以表示0,1,2,3或4個偏好。例如，person1可以選擇0（與他們無關），或14（與person14組在一個組中），或者可以表示與14,20,6和7中的人在一個組中。理想情況下，每個具有偏好將在至少有一個選擇的組中。

關於算法的想法？

Answer 1

您遇到的問題與C＃沒有真正相關，該算法與語言無關。

這個問題的經典實現是backtracking。

更多信息：

• Constraint satisfaction problems on Wikipedia
• 推薦：Chapter 5 from Artificial Intelligence - A Modern Approach 2nd edition

另一種方法（我會去爲這個）：Genetic Algorithms。

Answer 2

這可能是一個太多的要求在SO，但認爲這個問題很有趣，所以這裏有一些想法。

由於維克多Hurdugaci說，這主要是獨立於語言的算法問題（雖然我很樂意看到下面LINQ實現我的例子！）

在你的問題不能得到所描述的問題完美的結果，即它是一個優化問題（所以你不能用約束滿足算法來解決它）。您必須找到一種算法，該算法根據指示結果有多好的某個函數（稱爲適應函數）從所有可能結果集中找到最佳結果。

天真蠻力解決方案（僞代碼）

我們先從一組人（這裏：4把事情簡單化）：

people = { a, b, c, d } 

我們可以找到的所有可能的亞組固定大小（此處：2）使用choose操作：

groups = people.choose(2) // = { {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} } 

我們可以發現USI亞組的所有可能的組合再次納克choose操作：

combi = groups.choose(4/2) // = { {ab,ac} {ab,ad} {ab,bc} {ab,bd} 
          //  {ab,cd} {ac,ad} {ac,bc} {ac,bd} 
          //  {ac,cd} {ad,bc} {ad,bd} {ad,cd} 
          //  {bc,bd} {bc,cd} {bd,cd} } 

顯然，人不能在同一時間兩個組，所以我們刪除所有無效組合：

combi2 = combi.select(g => g.bigUnion().size == 4) 
          // = { {ab,cd}, {ac,bd}, {ad,bc} } 

現在你必須要找到基於「最佳」項目在一些健身功能上，即考慮到偏好而得分最高的組合。

result = combi2.maximumBy(g => fitness(g)) 

例如，如果a有b，和b，c和d偏好沒有任何偏好，然後calculateScore應該返回一個更高的分數爲{ab,cd}比{ac,bd}和{ad,bc}。

改進方案

有一個數的算法，用這種優化問題的解決。我認爲一個Hill climbing算法很適合這裏。