解決此問題的最佳算法是什麼？我有三組人，分別是A組，B組和C組。每組的人數相同。他們每個人都有他們願意合作的其他團隊中的人員名單。我想把所有這些人分成3個小組（一個來自A，一個來自B，另一個來自C），這樣一個小組中的每個人都想與小組中的其他人一起工作。將優選夥伴匹配到三個組中的算法
如何以快速方式找到這些組？如果沒有辦法讓每個人都開心，那麼算法首先應該讓儘可能多的團隊有三個人想要相互合作，然後讓其他團隊中的許多人都快樂。
最後一點：人們同意他們想與誰一起工作（如果人員x想與人一起工作，那麼y也想與x一起工作）。如果你還可以給出算法的運行時間的大O，那會很棒！
這就像穩定的婚姻問題，但與3方而不是兩個。
看看以前的問題（雙分圖匹配）的有效解決方案，並使其適應您的需求。
http://en.wikipedia.org/wiki/Stable_marriage_problem
一個調整可能是從A，B組只有一次構建工作對。然後這些配對必須分別與來自C組的工人配對。讓雙方只選擇雙方都同意的工人（給出他們的名單）。請注意，這隻會給一個局部最優。
的最佳解決方案，以K-三方匹配是NP-很難找到：
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
參見本文的非最優解到第k三方匹配問題：
我敢肯定，你可以找到其他人在谷歌自己現在你知道搜索條款。我不知道是否有一個有效的算法給出k = 3的最優解。
這是從穩定的婚姻問題的擴展不同，因爲我瞭解了OP的問題，各組中的人物沒有的，他們希望從多到少的工作誰的有序列表;這是一種二元關係（願意/不願意）。
這可以被配製成可以很快解決的整數規劃問題。我給出了下面的問題的數學表述;您可以使用glpk或AMPL/CPLEX等包來處理數據。
定義以下矩陣：
M1 = |A| x |B|矩陣，其中
M1(a,b) = 1如果（A的給定構件）願意用b工作（給定B的成員），否則爲0
M2 = |A| x |C|矩陣，其中M2(a,c) = 1如果（A的給定構件）願意採用c工作（給定的C的部件），否則爲0
M2 = |B| x |C|矩陣，WH ERE
M3(b,c) = 1如果B（給B的成員）願意用C（C中給出的成員）的工作，否則爲0
現在定義，我們將使用我們的最大化一個新的矩陣：
X = |A| x |B| x |C|矩陣，其中
X(a,b,c) = 1如果我們使a，b和c一起工作。
現在，定義我們的目標函數：
//最大化組
數量最大化Sum[(all a, all b, all c) X(a,b,c)]
受到以下限制：
//爲了確保沒有人被安置分兩組
對於a的所有值：Sum[(all j, k) X(a, j, k)] <= 1
對於b的所有值：Sum[(all i, k) X(i, b, k)] <= 1
對c的所有值：Sum[(all i, j) X(i, j, c)] <= 1
//爲了確保所有組由兼容個人
對於所有A，B，C的： X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
首先，可以消除其中兩個當事人是誰，他們將與第三組工作脫節列出任何事實。然後開始一個蠻力，深入第一次搜索，總是從最不受歡迎的選擇到最流行的。
或者，相當於上述消除，形成所有可能的三重奏和工作從替代列表。
只是快速注意這個問題。首先，它不是穩定婚姻問題的一個例子，事實上也不是它的擴展（即3D穩定匹配問題）。無論如何，這是一個已知爲NP難度的3D匹配問題（參見Garey和Johnson）。爲了以合理的方式解決這個問題，您可能需要使用某種形式的約束，整數或線性編程（其他方法存在）。可能有用的是新的Microsoft Solver Foundation，請檢查一下。
我遇到了類似的問題，只是寫了一個腳本，蠻力...http://grouper.owoga.com/
我最初的想法是：對於一個規模太大而無法蠻力的大型組織，某種類型的遺傳算法？進行N次隨機掉期M次。通過一些「快樂」功能來評分每個新安排。採取最好的幾個，繁殖，重複。
對於小團體，我最終通過循環幾個小組獲得了更好的結果，找到了'最佳'互換（產生最高總體'快樂'獲得的互換），然後重複。
我認爲你應該重新命名你的標題來實際描述你的問題，所以在相關的搜索中會出現一些東西。 – mmcdole 2008-11-17 07:51:46