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

Question

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

например

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

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

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

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

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

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

Я ищу алгоритм, который объединяет все x & y, чтобы максимизировать общий рейтинг.

В этом случае оптимальные пары будут x2:y3 = 9+9 = 18, x1:y2 = 5+8 = 13, x3:y1 = 5+9 = 14. для общего рейтинга 45. По крайней мере, я так думаю на глаз.

Я думаю, что это упрощенная версия задачи о максимальном независимом множестве, которая не является проблемой оптимизации NP-hard.

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