1

男性と女性のリストがあるとしましょう。各男性 (x) は各女性を評価し、各女性 (y) は各男性を 0 ～ 9 のスケールで評価します。

例えば

x1: {y1: 0、y2: 5、y3: 9}

x2: {y1: 1, y2: 0, y3: 9}

x3: {y1: 5, y2: 5, y3: 8}

y1: {x1: 3, x2: 3, x3: 5}

y2: {x1: 8, x2: 2, x3: 2}

y3: {x1: 9, x2: 5, x3: 9}

合計評価を最大化するために、すべての x と y をペアにするアルゴリズムを探しています。

この場合、最適なペアリングは x2:y3 = 9+9 = 18、x1:y2 = 5+8 = 13、x3:y1 = 5+9 = 14 です。合計評価は 45 です。少なくとも私はそう思います。目によるものです。

これは最大独立集合問題の単純化されたバージョンであり、NP 困難な最適化問題ではないと思います。

4

1 に答える 1

1

この問題は、安定した結婚の問題として知られており、ノーベル経済学賞がその解決策に対して授与されました。アルゴリズムは、ウィキペディアで詳細に説明されています。

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
    }
}
于 2014-12-07T16:42:02.893 に答える