ゲール-シャプレイ (Gale-Shapley) アルゴリズム

詳しいことは言えないのですが、Gale-Shapleyアルゴリズムを使う日が来てしまったらしいので、それについて簡単に解説。

Gale-Shapleyアルゴリズム(以下、G-Sアルゴリズム)は、安定マッチングとして有名らしい。僕ははじめて知りました。

ペアを安定してマッチングさせるアルゴリズムで、男女のペアを例にして説明されているみたい。

• 男性優位のマッチングと女性優位のマッチングがある。(今回は男性優位)

• 参加者全員が、選好順序のリストを用意する必要がある。

手順はこう。

1. 男性は、最も好きな女性に求婚する。
2. 女性が独身なら、ペアが成立する。
3. 女性が既婚の場合、今の相手(男性’)の方が準位が高い場合、その男性を振る。
4. 女性が既婚の場合、男性の方が男性'より順位が高い場合、男性'を振り、男性と結婚する。
5. これをすべての男性が既婚になるまで、繰り返す。

非常に発振しそうなアルゴリズムなんだけどO(n^2)で実行可能というからすごい。

作ってみた。正直くっそがばがばであるが、安定にマッチングできているので良いとする。
どう見ても計算量はO(n^2)である。
github.com

確かに安定にマッチしていると思う。
Windowsユーザーしか試せないので、スクショを何枚か貼っておく。

ちかれた。クズ記事でブログ更新AC