algorithm - 计算最大对数算法

Question

我有两张人表，包含男性和女性。我知道他们的年龄、种族和兴趣(每个变量是或否)。目的是将它们配对并设置最大对数。

配对有一些标准:

• 他们的年龄应为 +- 3 岁
• 同场比赛优先，但可以接受不同比赛
• 他们应该有最大数量的共同兴趣

有没有更快的算法来加速这个过程，而不是做很多层循环和 if else 条件？

Answer 1

首先根据这些标准为每个男性和女性建立优先级集，然后申请 Stable marriage problem产生最大可能配对的算法。

对于每个男人，根据上述标准创建一个单独的排序列表(偏好列表)，反之亦然。这只是使用自定义比较器对 male 和 female 数组进行多次排序。

现在，您有了每个男性和女性的偏好列表，您可以运行稳定婚姻算法以获得尽可能多的配对。稳定婚姻问题的常见伪代码如下所示:

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 = first woman on m’s list to whom m 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' becomes free
           (m, w) become engaged 
         else
           (m', w) remain engaged
    }
} 

如果正确实现算法，时间复杂度在平均情况下为 O(nlogn)，在最坏情况下为 O(n^2)。