最佳匹配額定配對的最佳方式是什麼？

Question

讓我說我有一個男人和女人的名單。每個男人（x）對每個女人進行評估，每個女人（y）評估每個男人的評分，評分爲0-9。

例如

X1：{Y1：0，Y2：5，Y3：9}

X2：{Y1：1，Y 2：0，Y3：9}

X3：{Y1：5，Y2 ：5，Y3：8}

Y1：{X1：3，X2：3，X3：5}

Y2：{X1：8，X2：2，X 3：2}

Y3 ：{x1：9，x2：5，x3：9}

我正在尋找一種算法，將所有x & y配對爲最大化總評分。

在這種情況下，最佳配對將是x2：y3 = 9 + 9 = 18，x1：y2 = 5 + 8 = 13，x3：y1 = 5 + 9 =至少我認爲這是由眼睛。

我認爲它是最大獨立集問題的簡化版本，這不是一個NP難的優化問題。

Answer 1

這個問題被稱爲穩定的婚姻問題，諾貝爾經濟學獎被授予解決方案。算法在一些細節描述在Wikipedia：

http://en.wikipedia.org/wiki/Stable_marriage_problem

僞代碼剪切/從維基百科粘貼：

function stableMatching { 
    Initialize all m ∈ M and w ∈ W to free 
    while ∃ free man m who still has a woman w to propose to { 
     w = m's highest ranked woman to whom he has not yet proposed 
     if w is free 
     (m, w) become engaged 
     else some pair (m', w) already exists 
     if w prefers m to m' 
      (m, w) become engaged 
      m' becomes free 
     else 
      (m', w) remain engaged 
    } 
}