【學習記錄】穩定婚姻問題

定義

題意：有 n n n 男 n n n 女，每一個人都對其他 n n n 個異性有不同程度的喜愛，用一個長為 n n n 的串列表示，串列中的異性按喜愛程度從高到低排列，問能否找出一個結婚方案，使得不存在兩對夫妻 ( m , w ′ ) , ( m ′ , w ) (m, w'), (m', w) (m,w′),(m′,w)，使得 m m m 比起 w ′ w' w′ 更喜愛 w w w， w w w 比起 m ′ m' m′ 更喜愛 m m m，

如果兩對夫妻 ( m , w ′ ) , ( m ′ , w ) (m, w'), (m', w) (m,w′),(m′,w) 沒有上述情況就稱這兩對夫妻是穩定的，否則就是不穩定的，

用圖論的語言描述，我們要找的結婚方案就是二分圖中的一個完美匹配，且要是一個穩定匹配，

Gale-Shapley 演算法

這是一個符合直覺的演算法，直接寫成偽代碼就能表述意思，

初始化：所有男女都沒有物件

WHILE 還有某個男性沒有物件，且其尚未追求過所有女性
    選擇這樣一個男性 m
    設 w 為 m 尚未追求過的，且 m 喜愛程度最高的女性

    IF w 沒有物件
        讓 (m, w) 暫時結對
    ELSE
        設當前 w 與 m' 是一對
        IF w 比起 m' 更喜歡 m
            讓 (m, w) 暫時結對，m' 變為沒有物件
        ELSE
            m 被拒絕，仍然沒有物件
END

最后所有結對的男女即成夫妻，

演算法正確性

1. 演算法是否會終止？

   會，在 n 2 n^2 n2 輪內終止，原因顯然，

2. 演算法是否找到完美匹配？

   是，否則必然有一對男女都沒有物件，而該男性由于沒有物件一定會追求該女性，使得兩者結對，

3. 演算法是否找到穩定匹配？

   是，考慮最終結果中任意兩對夫妻 ( m , w ′ ) , ( m ′ , w ) (m, w'), (m', w) (m,w′),(m′,w)，如果 m m m 追求過 w w w，那么 w w w 比起 m m m 更喜愛 m ′ m' m′；否則由于男性按照喜愛程度降序選擇女性， m m m 比起 w w w 更喜愛 w ′ w' w′，無論哪種情況，這兩對夫妻都是穩定的，

演算法其他特性

定義女性 w w w 是男性 m m m 的可行物件（valid partner），若存在某個穩定匹配，使得 ( m , w ) (m, w) (m,w) 是一對夫妻，對女性的男性可行物件定義類似，

定理：無論以何種方式實作演算法，演算法都只會回傳唯一的結果，且該結果滿足：

1. 對任意男性最優：演算法給出的其妻子，都是所有可行物件中，他的喜愛程度最高的，
2. 對任意女性最劣：演算法給出的其丈夫，都是所有可行物件中，她的喜愛程度最低的，

證明：設演算法給出的匹配是 S ? S^* S?，我們先證明第一點，

考慮反證，由于男性追求女性是按照喜愛程度降序，因此如果存在男性 m m m，使得其妻子 w w w 不是所有可行物件中， m m m 的喜愛程度最高的，那么 m m m 已經被之前的某個喜愛程度更高的可行物件 w ′ w' w′ 拒絕過了，

不妨假設 m m m 是演算法執行程序中第一個受到如此待遇的男性，按照定義，存在另一個穩定匹配 S S S，使得 ( m , w ′ ) (m, w') (m,w′) 是一對夫妻，

設 S ? S^* S? 中， w ′ w' w′ 的丈夫是 m ′ m' m′，顯然 w w w 喜愛 m ′ m' m′ 甚于 m m m，

再設 S S S 中， m ′ m' m′ 的妻子為 w ′ ′ w'' w′′，那么由于之前所設， m m m 是第一個被更喜愛的可行物件拒絕的男性，那么 m ′ m' m′ 會在 S ? S^* S? 中與 w ′ w' w′ 而不是 w ′ ′ w'' w′′ 結婚，就只能是因為 m ′ m' m′ 喜愛 w ′ w' w′ 甚于 w ′ ′ w'' w′′，否則， m ′ m' m′ 會先追求 w ′ ′ w'' w′′，被拒絕后才會追求 w ′ w' w′，而這與之前所設矛盾，

由此可得在 S S S 中， ( m , w ′ ) , ( m ′ , w ′ ′ ) (m, w'), (m', w'') (m,w′),(m′,w′′) 是不穩定的兩對夫妻，這與 S S S 是穩定匹配相矛盾，

再證明第二點，假設演算法給出的匹配 S ? S^* S? 中存在女性 w w w，使得其丈夫 m m m 不是所有可行物件中， w w w 的喜愛程度最低的，那么存在另一個穩定匹配 S S S，使得 w w w 與所有可行物件中喜愛程度最低的 m ′ m' m′ 結對，顯然， w w w 喜愛 m ′ m' m′ 甚于 m m m，

設 m m m 在 S S S 中的妻子是 w ′ w' w′，那么由于男性最優性， m m m 喜愛 w ′ w' w′ 甚于 w w w，這導致 ( m ′ , w ) , ( m , w ′ ) (m', w), (m, w') (m′,w),(m,w′) 是不穩定的兩對夫妻，這與 S S S 是穩定匹配相矛盾，

代碼實作

以 UVa 1175 為例，實作這一演算法，時間復雜度為 O ( n 2 ) O(n^2) O(n2)，

int n, pref[1005][1005], rnk[1005][1005];
// 分別為男對女的喜愛值串列，女對男的喜愛值排名（降序）
int cur[1005], wife[1005], husband[1005];
// 當前追求到哪一個
queue<int> q;
// 用佇列輔助求解
void GS(){
    memset(wife, 0, sizeof(wife));
    memset(husband, 0, sizeof(husband));
    for (int i = 1; i <= n; ++i)
        cur[i] = 1, q.push(i);
    while (!q.empty()){
        int h = q.front();
        q.pop();
        int targ = pref[h][cur[h]++];
        if (!husband[targ] || rnk[targ][h] < rnk[targ][husband[targ]]){
            wife[h] = targ;
            if (husband[targ] > 0){
                wife[husband[targ]] = 0;
                q.push(husband[targ]);
            }
            husband[targ] = h;
        } else if (cur[h] <= n){
            q.push(h);
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", wife[i]);
}

參考資料

• 《Algorithm Design》