Gale-shapleyアルゴリズムはマッチングに関するアルゴリズムです。
合コンでの男女のマッチング、研修医と病院のマッチングなどのグループAとグループB、そして全ての参加者がそのマッチング対象のグループの参加者に対して順位がある場合、Gale-shapleyアルゴリズムが役立ちます。
これらのマッチングでは、安定マッチングと呼ばれる一対一になっている状態を目指します。
言葉だけの説明は難しいと思うので、実際の問題を使って解説します。
男女の合コンのマッチングを考えます。
男
A ... 1,2,3
B ... 2,1,3
C ... 2,3,1
女
1 ... B, A, C
2 ... A, B, C
3 ... C, B, A
男性最良マッチング
男性の希望順位ができる限り反映されるマッチング(最良)を考えます。ちなみに、英語ではoptimalと言います。
男性の最良マッチングは男性の希望順位が反映されやすいように男性から告白します。
そうすると、女性１、女性２、女性３は以下のように男性がアプローチしてきます。
女性１...A
女性２...B,C
女性３...
でも女性２は二人の人が来ているので、自分の順位から高い方を選びます。女性２はA->B->Cの順番で希望しているので、Bを選択。
女性２とBがマッチしたので、Cは他の女性にアプローチします。Cの順番は2,3,1なので、女性３にアプローチします。
これでカップルは{(1,A)(2,B)(3,C)}とマッチングによって誕生しました。
ここで全員が安定マッチングしたことが分かります。
女性最良マッチング
女性の希望順位ができる限り反映されるマッチング(最良)を考えます。ちなみに、英語ではoptimalと言います。
上の男性マッチングの女性と男性を逆にするイメージです。
そうすると、男性A、男性B、男性Cは以下のように女性がアプローチしてきます
男性A ... 2
男性B ... 1
男性C ... 3
これにより{(A,2)(B,1)(C,3)}のカップルが生まれました。
一対一になっていることから安定マッチングになっていることも理解できます。
