安定結婚問題って知ってます…？
男性と女性が３人ずついたとします。
- 男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
男女３人ずつなら簡単ですが、人数が増えるほど考えられる組合せは爆発的に増え、難しくなります。
Wikipediaを見てみるとGale-Shapleyのアルゴリズムというのが書いてありますね。
安定結婚問題の考案者である Gale と Shapley が提案したアルゴリズムで、
安定マッチングを確実に求められるらしい…。
ということで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のアルゴリズムを実装することができました。
実装してみたいアルゴリズム、解決してみたい組合せ最適化問題があれば、また何か挑戦してみたいと思います。