計算最大配對數算法

我有兩個人的表，包含男性和女性。我知道他們的年齡，種族和興趣（每個變量是或否）。目的是將它們配對並設置最大數量的配對。計算最大配對數算法

沒有爲配對的一些標準：

他們的年齡應該是+ - - 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

計算最大配對數算法

回答

相關問題