根據偏好列表分配組（以3爲例）

-1

這是從純粹的算法角度開始的問題的第三次迭代，現在已經變成絕望的任務來尋找我可以理解的代碼示例。根據偏好列表分配組（以3爲例）

我想要做的是創建g人羣列表，試圖滿足儘可能多的偏好。每個人給出了排名前列的n列表中他們想要分配的其他人。它（我的程序）需要將相互請求視爲單向的更有影響力，並且應該（希望）找到接近最佳解決方案的東西。

我想要某種代碼示例（實際上是任何基於C的語言或詳細的僞代碼），以便我可以理解所需的算法並編寫我的程序。在我的第一個問題之後，我已經確定這可能需要某種關於穩定婚姻問題的變體，但我一直無法找到僞代碼或我能理解的實際語言的完整示例。

我已經詢問了算法HERE和HERE前面的問題，但沒有拿出任何東西（我認爲這是由於這些SE論壇極低的用戶數）。現在我在這裏問一個問題，希望更高的觀看率和一個面向程序設計的問題能夠爲我提供一個答案。

是的，我意識到這樣的問題之前已經被問到過，但沒有一個可以應用和回答。

有誰知道我該怎麼做？

要添加更多的細節（迴應意見）：我有一個人的名單。對於每個人，我都有一份他們最喜歡的其他人的列表，其中只包括主列表中的其他人。沒有列表以任何方式排序。優先列表中的名稱表示請求者希望與請求的人在一起。我正在尋找一種方法來創建指定數量的組，每個組只包含我在主列表中的人員。我希望分組能夠包含首選項列表。如果他們都在他們的名單中要求彼此，它應該嘗試將人們放在同一個小組中。它也應該包含一個人（在這個例子中是人A）請求其他人（人B）但B沒有請求A的請求。在這種情況下，雖然它仍然應該計算請求，但它應該被計算爲較低優先納入而不是相互請求。

編輯：此外，按照要求，這裏是一個JS函數，將（希望）有助於解釋我的目標：

/* 
Scores a possible grouping 
group would be an object, where the keys are names and the values are arrays of preferences. Ex: 

    { 
     "Person 1": ["Person 2"], 
     "Person 2": ["Person 1"], 
     "Person 3": ["Person 4"], 
     "Person 4": ["Person 2"] 
    } 

*/ 
function getGroupScore(group) { 
    var totalPoints = 0; 

    //Add a point for each request 
    for (var person in group) { 
     for (var request in group[person]) { 
      if(request != undefined && request.length > 0) 
       totalPoints++; 
     } 
    } 

    //Add two points for each two-way request 
    for (var person in group) { 
     for (var request in group[person]) { 
      if (group[person][request] != undefined //String validation 
       && group[person][request].length > 0 //More string validation 
       && group[group[person][request]] != undefined //Array validation 
       && group[group[person][request]].indexOf(person) != -1) //Check mutual request 
        totalPoints += 2; 
     } 
    } 

    return totalPoints; 
} 

/* 
Compares two possble groupings 
*/ 
function compareGroups(groupA, groupB) { 
    var scoreA = getGroupScore(groupA), 
     scoreB = getGroupScore(groupB); 

    if (scoreA > scoreB) 
     return 1; 
    else if (scoreA == ScoreB) 
     return 0; 
    else 
     return -1; 
}

來源

2013-09-23 Wasabi Fan

你有*不知道*你會怎麼做？是什麼讓你覺得我們會爲你做你的功課？ –

可疑類似於http://stackoverflow.com/q/18965363/56778 –

不，這不是家庭作業，它是個人項目的一部分。我試圖自己想出一個答案，但我的所有解決方案都會涉及到最初爲每個組選擇一個種子的人，而我發現這些人通常會將許多請求分開。我已經看到你在搜索後的日子裏連接的問題，但它沒有答案，所以它不能幫助我。 –

好，我一直在想你的問題，我想我可以給你一些方向，雖然我不能解決它。

首先我要試着重新修改一下你的問題，如果我錯了，請糾正我的錯誤。

要有一個集合P人的，以及諸如偏好的一個表：

 
Preferences of 4 people named A B C D: 
    A B C D 
+---------+ 
A| X X | 
B|  X | 
C|  X X | 
D| X  | 
+---------+

在該示例中， 'A' 偏好 'C'， 'B' 喜歡 'd' 等對角線是否喜歡自己將變得無足輕重。

現在你的問題是將P人分成G個不同的大小爲N的集合，假設P = G * N。對於N = 2的例子：

 
    A C B D 
+-------| 
A|x x| | 
C| x| x| 
+---+---- 
B| | x| 
D| |x | 
+---+---+ 
Here the partition is {A, C} and {B, D}

到其上的分區被滿足的程度是X的對角塊的數量，這在上面的例子中是3 + 2 = 5的總和。 AFAIK，與你想要解決的問題最相似的問題是構造一個塊對角矩陣，或者儘可能地接近一個。在你的情況下，對角塊外的值不會違反你。

如果你蠻橫的問題，那麼你有P！/ N！要檢查的分區。對於較小的P值和較大的N值，這可能值得直接實施，儘管在JS中這樣做會受到傷害。如果您的解決方案必須是最佳結果，那麼您可能不得不採取這樣的措施。

如果您可以允許「非常好」的解決方案，那麼隨機方法可能會接近。只要進行貪婪的重新排列，直到不再有重新排列，再重複這個過程幾次。

我在其他論壇上也發現this thread可能對您有幫助。與此相關的大多數問題都假設存在一個滿足每個偏好的解決方案，這歸結爲廣度優先搜索。很明顯，如果那是真的，那麼結果將是您的最佳解決方案，但由於通常情況並非如此，您可能需要進行一些重大研究來修改已知算法。

最好的祝願〜

來源

2013-09-26 03:12:08 DanielV

所以，你基本上建議我隨機測試組，直到沒有太大的改善？這絕對是我可以弄清楚如何實現的東西。 –

這是你想解決的問題嗎？是的，如果「足夠好」足夠好，那麼隨機生成的多個貪婪測試可能是最簡單的。 – DanielV

看完你的文章並思考了一段時間後，我想出了一個算法，似乎工作。感謝你的幫助！ –

根據偏好列表分配組（以3爲例）

回答

相關問題