Каков наилучший способ оптимального соответствия номинальным парам?

Question

Позволяет сказать, что у меня есть список мужчин и женщин. Каждый мужчина (x) оценивает каждую женщину, и каждая женщина (y) оценивает каждого мужчину по шкале 0-9.

например.

x1: {y1: 0, у2: 5, у3: 9}

х2: {y1: 1, y 2: 0, у3: 9}

х3: {y1: 5, у2 : 5, у3: 8}

у1: {x1: 3, х2: 3, х3: 5}

у2: {x1: 8, х2: 2, х3: 2}

у3 : {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.

Answer 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 
    } 
}