安定結婚問題を解くアルゴリズムをJavaで作ってみた。

# 安定結婚問題って知ってます…？

男性と女性が３人ずついたとします。

- 男A
- 男B
- 男C
- 女P
- 女Q
- 女R

すると３組の夫婦が作れますよね。
でも異性の好みは人それぞれですし、なるべくみんなが満足するような結果にしたい。

そこで**個人個人がランキングを持っているとします。**

||1位|2位|3位|
|:-------------|:-----|:-----|:-----|
|男Aの好み|女P|女Q|女R|
|男Bの好み|女Q|女R|女P|
|男Cの好み|女P|女Q|女R|
|女Pの好み|男C|男B|男A|
|女Qの好み|男B|男A|男C|
|女Rの好み|男C|男A|男B|

さて、例えば下記のようなマッチングを考えたとしましょう。

- 男A ⇔ 女Q
- 男B ⇔ 女R
- 男C ⇔ 女P

男Cと女Pはお互いに1位の相手と結婚しているので幸せです。
しかし、男Aと男Bはどうでしょう。**妻をとりかえっこしたほうがもっと幸せ**ですよね。
そこでマッチングを変更し、下記のようにしたとしましょう。

- 男A ⇔ 女R
- 男B ⇔ 女Q
- 男C ⇔ 女P

これ以上とりかえっこすると、むしろ悪化しそうですね。
このように、**これ以上とりかえっこが必要ないマッチング結果のことを「安定マッチング」といいます。**

**「安定結婚問題」とは、ランキングをもとにして、安定マッチングを見つける問題のこと**です。
数学の業界では、**組合せ最適化問題**と呼ばれる問題のひとつとして知られています。

# Gale-ShapleyのアルゴリズムをJavaで試作

安定結婚問題はWikipediaにも載っているほど有名な問題です。
⇒[安定結婚問題 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C)

男女３人ずつなら簡単ですが、人数が増えるほど考えられる組合せは爆発的に増え、難しくなります。

Wikipediaを見てみると**Gale-Shapleyのアルゴリズム**というのが書いてありますね。
安定結婚問題の考案者である Gale と Shapley が提案したアルゴリズムで、
安定マッチングを確実に求められるらしい…。

ということでJavaを使ってさくっと実装してみました。

ただし、このソースコードは下記の理由によりほとんど参考にならないため注意！

- とりあえず動くものをスピード重視で作っただけで、可読性や処理速度を一切考えていない
- 入力（ランキングデータ）がハードコーディング
- 出力（マッチング結果）が標準出力されるだけ

# ソースコード
```Java
package hoge;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class randomMatching {

	public static HashMap<String, ArrayList<String>> ranking;
	public static HashMap<String, String> matching;

	public static void main(String args[]){

		// 変数初期化
		matching = new HashMap<String, String>();
		matching.put("男A", "");
		matching.put("男B", "");
		matching.put("男C", "");
		ranking = new HashMap<String, ArrayList<String>>();
		ranking.put("男A", new ArrayList<>());
		ranking.put("男B", new ArrayList<>());
		ranking.put("男C", new ArrayList<>());
		ranking.put("女P", new ArrayList<>());
		ranking.put("女Q", new ArrayList<>());
		ranking.put("女R", new ArrayList<>());
		Collections.addAll(ranking.get("男A"), "女P", "女Q", "女R");
		Collections.addAll(ranking.get("男B"), "女Q", "女R", "女P");
		Collections.addAll(ranking.get("男C"), "女P", "女Q", "女R");
		Collections.addAll(ranking.get("女P"), "男C", "男B", "男A");
		Collections.addAll(ranking.get("女Q"), "男B", "男A", "男C");
		Collections.addAll(ranking.get("女R"), "男C", "男A", "男B");

		while(true)
		{
			// 現在の状況を表示
			dump();
			
			// 独身男性を探す
			String singleManName = "";
			for (String manName : matching.keySet()) {
				if(matching.get(manName) == "")
				{
					singleManName = manName;
					break;
				}
			}

			// 独身男性がもういない場合
			if(singleManName == "")
			{
			    System.out.println("フリーの人がいなくなったため、プログラムを終了します。");
			    return;
			}

			// 独身男性の好みの女性を調べてプロポーズする
			String bestWomanName = ranking.get(singleManName).get(0);
		    System.out.println(singleManName + "が、一番好きな" + bestWomanName + "にアタックしました。");

			// この女性が独身か調べる
			String husbandName = "";
			for (String manName : matching.keySet()) {
				if(matching.get(manName) == bestWomanName)
				{
					husbandName = manName;
				    System.out.println("ところが" + bestWomanName + "は" + husbandName + "と付き合っています。");
					break;
				}
			}

			// この女性が独身だった場合は婚約
			if(husbandName == "")
			{
			    System.out.println(bestWomanName + "は現在フリーのため" + singleManName + "と付き合うことにしました。");
				matching.put(singleManName, bestWomanName);
				continue;
			}
			else
			{
				// 婚約中の hasbandName と、プロポーズしてきた singleManName 、どちらが好みか調べる
				for(String str : ranking.get(bestWomanName))
				{
					// husbandName のほうが好みの場合
					if(str == husbandName)
					{
						// singleManはこの女性に今後二度とプロポーズしない
					    System.out.println(bestWomanName + "は" + singleManName + "より" + husbandName + "が好きです。" + singleManName + "は" + bestWomanName + "を諦めました。");
					    ranking.get(singleManName).remove(bestWomanName);
						break;
					}

					// husbandName のほうが好みの場合
					if(str == singleManName)
					{
						// 婚約
					    System.out.println(bestWomanName + "は" + husbandName + "より" + singleManName + "が好きなので、乗り換えることにしました。");
						matching.put(singleManName, bestWomanName);
						matching.put(husbandName, "");
						break;
					}
				}
			}
		}

	}
	
	// 現在の状態を表示する関数
	public static void dump()
	{
		System.out.println("");
		
		System.out.println("■現在のランキング");
		for (String key : ranking.keySet()) {
		    System.out.println("・" + key + " " + ranking.get(key));
		}
		
		System.out.println("◆現在のマッチング");
		for (String manName : matching.keySet()) {
			System.out.println("・" + manName + " ⇔ " + matching.get(manName));
		}
		
		System.out.println("");
	}
}
```

# 実行結果

夫婦がまったく成立していない状態から、
進行状況を段階的に`System.out.println()`するように作ってあります。

```
■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女P, 女Q, 女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 
・男A ⇔ 
・男B ⇔ 

男Cが、一番好きな女Pにアタックしました。
女Pは現在フリーのため男Cと付き合うことにしました。

■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女P, 女Q, 女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 女P
・男A ⇔ 
・男B ⇔ 

男Aが、一番好きな女Pにアタックしました。
ところが女Pは男Cと付き合っています。
女Pは男Aより男Cが好きです。男Aは女Pを諦めました。

■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女Q, 女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 女P
・男A ⇔ 
・男B ⇔ 

男Aが、一番好きな女Qにアタックしました。
女Qは現在フリーのため男Aと付き合うことにしました。

■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女Q, 女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 女P
・男A ⇔ 女Q
・男B ⇔ 

男Bが、一番好きな女Qにアタックしました。
ところが女Qは男Aと付き合っています。
女Qは男Aより男Bが好きなので、乗り換えることにしました。

■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女Q, 女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 女P
・男A ⇔ 
・男B ⇔ 女Q

男Aが、一番好きな女Qにアタックしました。
ところが女Qは男Bと付き合っています。
女Qは男Aより男Bが好きです。男Aは女Qを諦めました。

■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 女P
・男A ⇔ 
・男B ⇔ 女Q

男Aが、一番好きな女Rにアタックしました。
女Rは現在フリーのため男Aと付き合うことにしました。

■現在のランキング
・男C [女P, 女Q, 女R]
・男A [女R]
・女Q [男B, 男A, 男C]
・男B [女Q, 女R, 女P]
・女R [男C, 男A, 男B]
・女P [男C, 男B, 男A]
◆現在のマッチング
・男C ⇔ 女P
・男A ⇔ 女R
・男B ⇔ 女Q

フリーの人がいなくなったため、プログラムを終了します。
```

以上が実行結果となります。
安定マッチングが無事に求まりました。
# このアルゴリズムのすごいところ
### (1) 必ず安定マッチングが求まる

実行結果の途中で

```
女Pは男Aより男Cが好きです。男Aは女Pを諦めました。
```
と出力されているところがあります。
このように男のアタックを女が断ったとき、
男は「諦める」、つまり**その男のランキングから該当の女を除外**します。
この除外操作により、男が同じ女に繰り返しアタックすることは絶対に発生しません。
**無限ループに陥ることなく、アルゴリズムが必ず終了する**のはこのためです。

### (2) 結婚だけでなく応用がきく
今回は「どの男とどの女を夫婦にする？」という題材で試してみましたが、
ほかにも例えば学校で「どのゼミにどの学生を入れる？」という題材でもできそうですよね。
ゼミの教授は好きな学生のランキングを作れるでしょうし、
学生も入りたいゼミのランキングを作れるでしょう。

お互いのランキングさえあれば、あらゆる題材にこのアルゴリズムは実行可能なのです。
そして求まるのは「安定マッチング」。
求まったマッチング結果に文句を言う人はいないはず！

# まとめ
突貫工事ではありますが、JavaでGale-Shapleyのアルゴリズムを実装することができました。
実装してみたいアルゴリズム、解決してみたい組合せ最適化問題があれば、また何か挑戦してみたいと思います。