用戶之間非二部非加權最大匹配

Question

情況：用戶選擇多個其他用戶作爲項目的可能合作伙伴。用戶沒有偏好他選擇的另一個用戶（即，他的列表中的任何用戶對於夥伴而言足夠好）。例如：

| user_id | preferred_partners | 
| 1  | 2 4    | 
| 2  | 3 1    | 
| 3  | 4 2 1    | 
| 4  | 1     | 

真實名單會大得多。

我的問題：給定一組用戶及其首選合作伙伴（如上面的列表），我想生成一個最終合作伙伴數組。最終合作伙伴的數量必須最大化（我希望儘可能多的人配對）。

這是算法我認爲我需要：Edmonds's matching algorithm，但因爲我不是從數學背景，我無法解釋和實施它。

任何幫助，將不勝感激。提前致謝。

Answer 1

Edmonds的匹配算法的確是你想要的。這是一個good link，它提供了一個詳細的解釋

Answer 2

埃德蒙茲的算法可能是你想要的，但它可能不是。你會去找三倍嗎？你是否會想要喜好的力量？你是否想過要對你的機制提供一些保證，如果有人放下更多的偏好，他們不能從被匹配到不匹配？合作伙伴必須是相互優先的嗎？如果不是，相互優先的合作伙伴有更多的權重嗎？

其中一些變體可以通過Edmonds算法或其加權表親來解決，它使用Edmonds's來解決「受限制的原始」，就像匈牙利算法使用雙向匹配算法一樣，但是一些3D匹配特別是，很難和可愛的組合算法。您可能會發現，通過從Ruby調用整數規劃求解器即可解決多時間情況。