optimization - 最佳匹配评级对的最佳方式是什么？

Question

让我们说我有一个男人和女人的名单。每个男人 (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-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
    }
}