计算最大配对数算法

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

没有为配对的一些标准：

他们的年龄应该是+ - - 3年
同一场比赛中第一次，但差的比赛是可以接受的
他们应该有共同的利益

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

2016-11-04 Felix Chan

此问题未指定。年龄是一个硬限制，这很好。你给出了另外两个标准（种族和共同利益），但没有说明两者的相对权重，也没有给出匹配的最小值是可接受的。如果你需要匹配稳定，稳定的婚姻可能适用于这里。如果不是，您有一个版本的分配问题，但您没有指定权重函数。 – tjhighley

是的，只有年龄才是严格的限制。对于其他因素，它们具有相同的权重，这意味着更常见的因素更适合配对。如果他们有不同的种族并且没有共同的兴趣，那还是可以的，但它必须是配对中的最后一个选项。 –

首先根据这些标准为每个男性和女性建立优先级集，然后应用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 = 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)在最坏的情况下。

来源

2016-11-04 10:15:44

计算最大配对数算法

回答

相关问题