C++で解く安定結婚問題（マッチング問題）｜特定のケースの実装例

本記事では、安定結婚問題（Stable Marriage Problem）と呼ばれるマッチング問題を、特定のケースについて解決するC++プログラムを紹介します。ここでは、N人の男性とN人の女性が与えられ、それぞれが異性全員を好みの順にランク付けしているものとします。その上で、「お互いが現在のパートナーよりも相手の方を望む」というような男女の組み合わせが一切存在しない形で結婚を実現します。この条件を満たすとき、すべての結婚は「安定（stable）」していると言えます。

アルゴリズムの流れ

このプログラムで採用しているのは、ゲールとシャプレーが1962年に提案したGale–Shapleyの安定結婚アルゴリズムです。自由な男性が順にプロポーズを行い、女性側の選択によって婚約の組み替えを繰り返すことで、最終的に必ず安定なマッチングが得られます。計算量はO(N²)です。

Begin
    関数 WomenPrefersMenOverMen1():
    A) 女性が現在の婚約者m1よりも男性mを好むかどうかを判定する
    B) 女性のリストでm1がmより先に現れる場合、女性は現在の婚約を維持する
    C) 女性のリストでmがm1より先に現れる場合、現在の婚約を破棄してmと婚約させる
End

Begin
    関数 stablewedding():
    1) 男性には0〜N-1の番号を割り当てる
    2) 女性にはN〜2N-1の番号を割り当てる
    3) 自由な男性が存在する間、以下を繰り返す
       A) 最初の自由な男性を選ぶ
       B) その男性の好みの順序に従って、女性を一人ずつ順に見ていく
       C) 希望する女性が自由であれば、その女性と男性はカップルになる
       D) 女性がすでに婚約している場合は、その現在の婚約者を特定する
       E) 女性が現在の婚約者m1よりも男性mを好む場合、女性とm1の婚約を破棄し、mと女性を婚約させる
End

サンプルコード

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 4

// 女性wが現在の婚約者m1よりも男性mを好むかどうかを判定する関数
// （m1が先に現れればtrue＝現在の婚約を維持、mが先に現れればfalse＝乗り換え）
bool WomenPrefersMenOverMen1(int prefer[2*N][N], int w, int m, int m1) {
    for (int i = 0; i < N; i++) {
        if (prefer[w][i] == m1)
            return true;
        if (prefer[w][i] == m)
            return false;
    }
}

void stablewedding(int prefer[2*N][N]) {
    int wPartner[N];  // 女性のパートナーを格納する配列
    bool mFree[N];    // 男性が自由かどうかを格納する配列
    // すべての男性と女性を「自由」の状態で初期化
    memset(wPartner, -1, sizeof(wPartner));
    memset(mFree, false, sizeof(mFree));
    int freeCnt = N;
    while (freeCnt > 0) {  // 自由な男性が存在する間繰り返す
        int m;  // 最初の自由な男性を選ぶ
        for (m = 0; m < N; m++)
            if (mFree[m] == false)
                break;
        // 自由になった男性の好みに従い、女性を一人ずつ順に見ていく
        for (int i = 0; i < N && mFree[m] == false; i++) {
            int w = prefer[m][i];
            // 希望する女性が自由なら、そのままカップルになる
            if (wPartner[w-N] == -1) {
                wPartner[w-N] = m;
                mFree[m] = true;
                freeCnt--;
            } else {  // 女性wがすでに婚約している場合
                // 女性の現在の婚約者を調べる
                int m1 = wPartner[w-N];
                // 女性が現在の婚約者m1よりもmを好むなら、
                // m1との婚約を破棄し、mと婚約させる
                if (WomenPrefersMenOverMen1(prefer, w, m, m1) == false) {
                    wPartner[w-N] = m;
                    mFree[m] = true;
                    mFree[m1] = false;
                }
            }
        }
    }
    cout << "Woman Man" << endl;
    for (int i = 0; i < N; i++)
        cout << " " << i+N << "\t" << wPartner[i] << endl;
}

int main() {
    int p[2*N][N] = {
        {7, 5, 6, 4},   // 男性0の好み
        {5, 4, 7, 6},   // 男性1の好み
        {4, 5, 7, 6},   // 男性2の好み
        {4, 5, 7, 6},   // 男性3の好み
        {0, 1, 3, 2},   // 女性4の好み
        {0, 1, 3, 2},   // 女性5の好み
        {0, 1, 3, 2},   // 女性6の好み
        {0, 1, 3, 2},   // 女性7の好み
    };
    stablewedding(p);
    return 0;
}

実行結果

Woman Man
 4      3
 5      1
 6      2
 7      0

出力の見方

出力の左側は女性の番号（N〜2N-1）、右側はその女性と結ばれた男性の番号（0〜N-1）を表しています。この例では、女性4は男性3と、女性5は男性1と、女性6は男性2と、女性7は男性0とマッチングされています。どの男女のペアを取り上げても「両者が現在のパートナーよりも互いを望む」という状況は発生しないため、この結婚の組み合わせが安定していることが確認できます。