Gale-Shapley algorithm

二部グラフの点を、プロポーズする側のグループとプロポーズされる側のグループに分ける
プロポーズする側は自分がプロポーズしていない最高順位の相手にプロポーズする
相手が独身ならば婚約
独身でなければプロポーズされる側の順位にしたがって婚約あるいは婚約破棄をする
プロポーズする側に独身がいなくなるまでプロポーズを繰り返す

計算量
平均O(N)O(N)
最悪O(N2)O(N^2)
順位表をすべて走査する
プロポーズする側のグループの最良安定マッチングが得られる
👉安定マッチングのうち、プロポーズする側の意向をもっともよく反映したマッチングになる

引用
>（男性がプロポーズする）G-S アルゴリズムは、(1) 1 人の男性が同じ女性に 2 度以上プロポーズしない、(2) 女性は婚約すると独身に戻らない、(3) 女性はプロポーズされる際その相手が悪くなることはない、ということからこのアルゴリズムが任意の例に対し、有限回の操作で安定マッチングを必ず導いて終了することがいえる。

表記ゆれ

Related