はじめに (対象読者・この記事でわかること)

この記事は、アルゴリズムに興味があるプログラミング初学者の方、Javaの基本的な知識をお持ちの方、そして安定結婚問題とそのGale-Shapleyアルゴリズムについて深く学びたい方を対象としています。

この記事を読むことで、安定結婚問題（安定マッチング問題）がどのような課題であり、なぜ解決する必要があるのかという背景を理解できます。さらに、Gale-Shapleyアルゴリズムの具体的な仕組みと、それをJava言語でどのように実装できるかを学ぶことができます。実際に動作するコードを通じて、アルゴリズムの動きを肌で感じ、複雑な問題をロジカルに解決する力を養うことができるでしょう。

前提知識

この記事を読み進める上で、以下の知識があるとスムーズです。 - Javaの基本的な文法（変数、条件分岐、ループ、クラス、メソッドなど） - 配列、リスト、マップといった基本的なデータ構造の概念 - 簡単なアルゴリズムの考え方や、問題解決へのアプローチ

安定結婚問題とは？Gale-Shapleyアルゴリズムの概要

安定結婚問題（Stable Marriage Problem）は、N人の男性とN人の女性がいて、それぞれが異性に対する選好順位（この人が一番好き、次に好き、といった優先順位）を持っているときに、ペアを組んだときに「不安定なペア」が存在しないようなマッチングを見つける問題です。

ここでいう「不安定なペア」とは、たとえば男性M1と女性W1がペアになっているが、男性M1が現在のパートナーW1よりも女性W2を好み、かつ女性W2も現在のパートナーM2よりも男性M1を好む場合、M1とW2がお互いをより好むため、現在のパートナーを捨ててM1とW2が結びついてしまう可能性がある状態を指します。安定結婚問題の目的は、このような「裏切り」が発生しないような、すべてのペアが安定している（互いに現在のパートナーが一番か、そうでないにしても他に自分をより好む人がいない）マッチングを見つけることです。

この問題を解決するのが、1962年にDavid Gale氏とLloyd Shapley氏によって考案されたGale-Shapleyアルゴリズムです。このアルゴリズムは、必ず安定したマッチングを見つけ出すことができるだけでなく、その解が男性（プロポーズする側）にとって最適な安定マッチングとなることが証明されています。アルゴリズムの核となるのは、「プロポーズ」と「受諾・拒否」のプロセスです。男性がプロポーズを繰り返し、女性は最も好ましい相手を受け入れつつ、より好ましい相手からのプロポーズがあれば乗り換える、というシンプルなルールで進行します。この仕組みにより、最終的にはすべての人が安定したペアを形成します。

Javaで実践！Gale-Shapleyアルゴリズム実装ガイド

Gale-ShapleyアルゴリズムをJavaで実装するプロセスを段階的に見ていきましょう。このアルゴリズムは、男性が順番にまだプロポーズしていない最も好きな女性にプロポーズし、女性はプロポーズしてきた男性の中で最も好きな男性を選び、それ以外の男性は拒否するというサイクルを繰り返すことで安定的なマッチングを形成します。

ステップ1: 問題設定とデータ構造の設計

まず、問題のデータをどのように表現するかを考えます。N人の男性とN人の女性がいるとし、それぞれのIDを0からN-1とします。選好順位は2次元配列で表現するのが一般的です。

  • N: 男性と女性の人数。
  • menPreferences[i][j]: 男性iがj番目に好む女性のID。
  • womenPreferences[i][j]: 女性iがj番目に好む男性のID。

女性の選好順位は、特定の男性がその女性にとって何番目に好ましいかを迅速に判断するために、少し加工した形で持っておくと便利です。 - womenRankings[i][j]: 女性iにとって、男性jが何番目に好ましいかを示す順位（0が最も好ましい）。

次に、アルゴリズムの状態を管理するためのデータ構造が必要です。 - womanEngagedTo[i]: 女性iが現在婚約している男性のID。未婚の場合は-1。 - menNextProposalIndex[i]: 男性iが次にプロポーズする女性の、menPreferences[i]におけるインデックス。 - freeMen: まだ婚約していない男性のIDを格納するキュー。

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;

public class GaleShapley {

    private int N; // 男性の人数、女性の人数

    // 男性iがj番目に好む女性のID
    // 例: menPreferences[0] = {1, 0, 2} -> 男性0は女性1が一番、次に女性0、次に女性2を好む
    private int[][] menPreferences;

    // 女性iがj番目に好む男性のID
    // 例: womenPreferences[0] = {0, 1, 2} -> 女性0は男性0が一番、次に男性1、次に男性2を好む
    private int[][] womenPreferences;

    // 女性iにとって、男性jが何番目に好ましいかを示す順位 (0が最も好ましい)
    // womenRankings[i][j] = k -> 女性iにとって男性jはk番目に好ましい
    private int[][] womenRankings;

    // 女性iが現在婚約している男性のID (未婚の場合は-1)
    private int[] womanEngagedTo;

    // 男性iが次にプロポーズする女性の、menPreferences[i]におけるインデックス
    private int[] menNextProposalIndex;

    // まだ婚約していない男性のIDを格納するキュー
    private Queue<Integer> freeMen;

    public GaleShapley(int N, int[][] menPref, int[][] womenPref) {
        this.N = N;
        this.menPreferences = menPref;
        this.womenPreferences = womenPref;

        // womenRankingsの初期化と構築
        this.womenRankings = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 女性iにとって、womenPreferences[i][j] (j番目に好む男性) は j 番目の順位
                womenRankings[i][womenPreferences[i][j]] = j;
            }
        }

        this.womanEngagedTo = new int[N];
        Arrays.fill(womanEngagedTo, -1); // 全ての女性は未婚状態からスタート

        this.menNextProposalIndex = new int[N];
        Arrays.fill(menNextProposalIndex, 0); // 全ての男性は一番好きな女性からプロポーズを始める

        this.freeMen = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            freeMen.add(i); // 全ての男性は最初は未婚
        }
    }
    // solveメソッドは後ほど実装
    // printMatchesメソッドは後ほど実装
}

ステップ2: Gale-Shapleyアルゴリズムの核となるロジック

Gale-Shapleyアルゴリズムの主要なロジックは、未婚の男性が存在する限り、以下のプロセスを繰り返すことです。

  1. 未婚の男性がプロポーズ: freeMenキューから男性mを取り出す。男性mはまだプロポーズしていない女性の中で、最も好む女性wにプロポーズする。
  2. 女性の受諾・拒否: - 女性wが未婚の場合: 女性wは男性mを受け入れ、彼らは婚約する。 - 女性wがすでに婚約している場合: 女性wは、現在のパートナーcurrentPartnerと男性mを比較する。
    • 女性wが男性mをcurrentPartnerよりも好む場合: 女性wはcurrentPartnerとの婚約を解消し、男性mと婚約する。currentPartnerは未婚状態に戻り、freeMenキューに追加される。
    • 女性wがcurrentPartnerを男性mよりも好む場合: 女性wは男性mのプロポーズを拒否する。男性mは未婚のままであり、次に好む女性にプロポーズするためにmenNextProposalIndex[m]を更新する。

このプロセスは、すべての男性が婚約するまで、またはプロポーズできる女性がいなくなるまで繰り返されます。Gale-Shapleyアルゴリズムの特性として、すべての男性が最終的に婚約することが保証されています。

Java

    public int[] solve() {
        while (!freeMen.isEmpty()) {
            int currentMan = freeMen.poll(); // 未婚の男性をキューから取り出す

            // 男性がプロポーズする女性を探す
            int womanToProposeTo = -1;
            while (menNextProposalIndex[currentMan] < N) {
                womanToProposeTo = menPreferences[currentMan][menNextProposalIndex[currentMan]];
                menNextProposalIndex[currentMan]++; // 次回のためにインデックスを更新

                // 女性が未婚の場合
                if (womanEngagedTo[womanToProposeTo] == -1) {
                    womanEngagedTo[womanToProposeTo] = currentMan; // 婚約
                    break; // この男性は婚約したので次の男性へ
                } 
                // 女性がすでに婚約している場合
                else {
                    int currentPartner = womanEngagedTo[womanToProposeTo];
                    // 女性が新しいプロポーズ相手 (currentMan) を現在のパートナーよりも好むか？
                    // womenRankings[womanToProposeTo][currentMan] < womenRankings[womanToProposeTo][currentPartner]
                    // これは、currentManの順位がcurrentPartnerの順位よりも小さい(より好ましい)ことを意味する
                    if (womenRankings[womanToProposeTo][currentMan] < womenRankings[womanToProposeTo][currentPartner]) {
                        // 女性は新しいプロポーズ相手 (currentMan) を選ぶ
                        womanEngagedTo[womanToProposeTo] = currentMan;
                        // 古いパートナーは未婚に戻る
                        freeMen.add(currentPartner);
                        break; // この男性は婚約したので次の男性へ
                    } else {
                        // 女性は現在のパートナーを維持。プロポーズした男性は未婚のまま。
                        // この男性 (currentMan) は、次に好む女性にプロポーズするためにループを続行
                    }
                }
            }
            // プロポーズできる女性がいなくなったが、まだ婚約していない男性はキューに戻す必要はない。
            // アルゴリズムの保証により、最終的に全員が婚約する。
        }
        return womanEngagedTo; // 各女性の婚約相手の配列を返す
    }

    public void printMatches(int[] matches) {
        System.out.println("--- 安定結婚マッチング結果 ---");
        for (int i = 0; i < N; i++) {
            System.out.println("女性 " + i + " は男性 " + matches[i] + " と婚約しました。");
        }
    }

ステップ3: 完全なJavaコードの作成と実行

上記のクラスとメソッドを統合し、mainメソッドで実行例を示します。

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;

public class GaleShapley {

    private int N;
    private int[][] menPreferences;
    private int[][] womenPreferences;
    private int[][] womenRankings;
    private int[] womanEngagedTo;
    private int[] menNextProposalIndex;
    private Queue<Integer> freeMen;

    public GaleShapley(int N, int[][] menPref, int[][] womenPref) {
        this.N = N;
        this.menPreferences = menPref;
        this.womenPreferences = womenPref;

        this.womenRankings = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                womenRankings[i][womenPreferences[i][j]] = j;
            }
        }

        this.womanEngagedTo = new int[N];
        Arrays.fill(womanEngagedTo, -1);

        this.menNextProposalIndex = new int[N];
        Arrays.fill(menNextProposalIndex, 0);

        this.freeMen = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            freeMen.add(i);
        }
    }

    public int[] solve() {
        while (!freeMen.isEmpty()) {
            int currentMan = freeMen.poll();

            // 男性がプロポーズする女性を探す (プロポーズできる女性がいなくなるまで繰り返す)
            int womanToProposeTo = -1;
            boolean engagedThisTurn = false; // 今回のターンで婚約したか

            while (menNextProposalIndex[currentMan] < N) {
                womanToProposeTo = menPreferences[currentMan][menNextProposalIndex[currentMan]];
                menNextProposalIndex[currentMan]++;

                // 女性が未婚の場合
                if (womanEngagedTo[womanToProposeTo] == -1) {
                    womanEngagedTo[womanToProposeTo] = currentMan;
                    engagedThisTurn = true;
                    break;
                } 
                // 女性がすでに婚約している場合
                else {
                    int currentPartner = womanEngagedTo[womanToProposeTo];
                    if (womenRankings[womanToProposeTo][currentMan] < womenRankings[womanToProposeTo][currentPartner]) {
                        // 女性は新しいプロポーズ相手 (currentMan) を選ぶ
                        womanEngagedTo[womanToProposeTo] = currentMan;
                        freeMen.add(currentPartner); // 古いパートナーは未婚に戻る
                        engagedThisTurn = true;
                        break;
                    }
                }
            }

            // もしこのターンで婚約できなかった場合 (プロポーズできる女性がいなくなった場合)
            // この男性はキューに戻す必要はない。Gale-Shapleyの保証により必ず婚約する。
            // 実際には上記のwhileループを抜ける場合、それは婚約が成立したか、またはプロポーズできる女性が
            // いなくなった（という状況は発生しない）のどちらかとなる。
        }
        return womanEngagedTo;
    }

    public void printMatches(int[] matches) {
        System.out.println("--- 安定結婚マッチング結果 ---");
        for (int i = 0; i < N; i++) {
            System.out.println("女性 " + i + " は男性 " + matches[i] + " と婚約しました。");
        }
    }

    public static void main(String[] args) {
        // 例1: N=3 のケース
        int N1 = 3;
        int[][] menPreferences1 = {
            {1, 0, 2}, // 男性0: W1, W0, W2
            {0, 1, 2}, // 男性1: W0, W1, W2
            {0, 1, 2}  // 男性2: W0, W1, W2
        };
        int[][] womenPreferences1 = {
            {0, 1, 2}, // 女性0: M0, M1, M2
            {1, 0, 2}, // 女性1: M1, M0, M2
            {0, 1, 2}  // 女性2: M0, M1, M2
        };

        System.out.println("=== 例1の実行 ===");
        GaleShapley gs1 = new GaleShapley(N1, menPreferences1, womenPreferences1);
        int[] matches1 = gs1.solve();
        gs1.printMatches(matches1);
        System.out.println("\n");

        // 例2: N=4 のケース (より複雑な選好)
        int N2 = 4;
        int[][] menPreferences2 = {
            {0, 1, 2, 3}, // 男性0: W0, W1, W2, W3
            {1, 0, 3, 2}, // 男性1: W1, W0, W3, W2
            {0, 1, 2, 3}, // 男性2: W0, W1, W2, W3
            {1, 0, 3, 2}  // 男性3: W1, W0, W3, W2
        };
        int[][] womenPreferences2 = {
            {0, 1, 2, 3}, // 女性0: M0, M1, M2, M3
            {1, 0, 3, 2}, // 女性1: M1, M0, M3, M2
            {0, 1, 2, 3}, // 女性2: M0, M1, M2, M3
            {1, 0, 3, 2}  // 女性3: M1, M0, M3, M2
        };

        System.out.println("=== 例2の実行 ===");
        GaleShapley gs2 = new GaleShapley(N2, menPreferences2, womenPreferences2);
        int[] matches2 = gs2.solve();
        gs2.printMatches(matches2);
    }
}

ハマった点やエラー解決

Gale-Shapleyアルゴリズムを実装する際に、特に注意が必要な点と、それによって発生しやすい問題について説明します。

  1. 選好順位のインデックスとIDの混同:

    • 問題: menPreferences[i][j]が「男性iがj番目に好む女性のID」を意味するのに対し、womenPreferences[i][j]も「女性iがj番目に好む男性のID」を意味します。ここで、womenRankingsの計算を怠ったり、womenPreferencesをそのまま使って比較しようとすると、期待する順位（その人が何番目に好ましいか）ではなく、単なるインデックスとして扱ってしまい、誤った比較をしてしまいます。
    • 例: womenPreferences[0] = {2, 1, 0}という場合、女性0は男性2が一番好き、次に男性1、次に男性0が好き、という意味です。もし女性0に男性2と男性0がプロポーズした場合、どちらを好むか比較するには、男性2は1番目、男性0は3番目という「順位」で比較する必要があります。

  2. 無限ループまたは婚約されない男性の発生:

    • 問題: freeMenキューから男性を取り出し、彼がプロポーズし続ける処理のロジックに誤りがあると、無限ループに陥るか、すべての男性が婚約しないままアルゴリズムが終了してしまう可能性があります。
    • 例: 男性がプロポーズを拒否されたときに、menNextProposalIndexを正しく更新しないと、同じ女性に何度もプロポーズしてしまう可能性があります。また、女性が既存の婚約者を解放する際に、その婚約者をfreeMenキューに戻し忘れると、その男性は永遠に未婚のままになります。

解決策

  1. womenRankings配列の活用:

    • 女性がプロポーズしてきた男性を比較する際に、womenPreferencesを直接参照するのではなく、事前に計算しておいたwomenRankings配列を使用します。womenRankings[女性ID][男性ID]で、その女性にとってその男性が何番目に好ましいか（数字が小さいほど好ましい）がすぐに分かるようにすることで、比較ロジックを簡潔かつ正確に実装できます。
    • 例: womenRankings[womanToProposeTo][currentMan] < womenRankings[womanToProposeTo][currentPartner]のように比較することで、「女性womanToProposeToにとって、currentManはcurrentPartnerよりも好ましいか？」を正しく判断できます。

  2. freeMenキューとmenNextProposalIndexの厳密な管理:

    • freeMenキュー: 男性がプロポーズを拒否され、未婚のままでいる場合（女性が既存の婚約者を維持した場合）、その男性はすぐに次の女性にプロポーズする必要があります。しかし、キューから一度取り出した男性が婚約できなかった場合、その男性を再びキューに戻す必要はありません。彼は現在のターンで次のプロポーズ先を探し続けるか、または次の機会に再びキューから取り出されることで、最終的に婚約します。最も重要なのは、女性が既存の婚約者を解放した場合、その解放された男性は必ずfreeMenキューに戻すことです。
    • menNextProposalIndex: 男性がプロポーズを拒否された場合、必ずmenNextProposalIndex[currentMan]をインクリメントし、次にプロポーズする女性が異なるようにします。このインデックスがNに達した場合、その男性はすべての女性にプロポーズし終えたことになります（ただし、Gale-Shapleyの性質上、そのような事態が起きる前に全ての男性は婚約する）。

これらの点を踏まえ、データ構造の初期化と更新ロジックを慎重に設計することで、Gale-Shapleyアルゴリズムを正しく、かつ効率的に実装することができます。

まとめ

本記事では、安定結婚問題とそれを解決するGale-Shapleyアルゴリズムについて、Javaを用いた実装を通じて深く掘り下げました。

  • 安定結婚問題: N人の男性とN人の女性がそれぞれ選好順位を持つ中で、すべてのペアが「安定」する（誰も現在のパートナーよりお互いを好む組み合わせが存在しない）マッチングを見つける課題であることを学びました。
  • Gale-Shapleyアルゴリズムの仕組み: 男性がプロポーズし、女性が最も好む相手を受け入れるというシンプルながら強力なプロセスにより、必ず安定マッチングが得られることを理解しました。このアルゴリズムは、プロポーズする側（男性）にとって最適な安定マッチングを保証します。
  • Javaによる実装: 選好順位の表現方法、freeMenキューやwomanEngagedTo、menNextProposalIndexなどの状態管理用データ構造、そしてプロポーズと受諾・拒否のロジックを、具体的なJavaコードとして実装する手順を追いました。

この記事を通して、Gale-Shapleyアルゴリズムの理論的な理解を深めるとともに、実際にJavaでアルゴリズムを実装する実践的なスキルを習得できたことでしょう。 データ構造の選定やインデックスの管理といったプログラミングにおける注意点も学ぶことができました。

今後は、このアルゴリズムを大規模なデータセットに適用した場合のパフォーマンス最適化や、異なる種類のマッチング問題（例: レジデンシーマッチングなど）への応用、さらには女性に有利な安定マッチングを求める場合のアルゴリズムの変形などについても記事にする予定です。

参考資料