- @ThothChildren
- 2018.6.16
- PV 128
希望考慮し全ペアいい組合せを見つける
ー 概要 ー
お互いに希望の順序があり双方の希望を考慮しながら全体的に見てそこそこよい組合せを検出する技術についてまとめます.男性と女性の結婚の希望リストに沿って最も安定な組み合わせる安定結婚問題(stable marriage problem)という有名な問題です.この問題は少なくとも一つは必ず解を持つことが知られています. 安定結婚問題はGale–Shapley アルゴリズムによって求めます.
この章を学ぶ前に必要な知識
条件
- 二つのグループから一人ずつ出してペアを作る
- 二つのグループとも同数
- 全員が相手グループ全員の希望ランキングを持つ
効果
- 個々人の希望に沿って、二つのグループから一人づつ出して作るペアの組合せを求める
- 今とは違うペアで希望リストが双方上がるペアはない状態の結果(駆け落ちがありえない)
ポイント
- 同一の順位がある場合も解くことが可能
- 安定結婚問題といい、これには安定した解が幾らかある
- どちらかのグループにアルゴリズムが注目するかで希望の通り方が変わる
- 解は一般的に複数存在する
- Gale–Shapleyアルゴリズムによって最良安定ペアを算出
解 説
二つのグループから一人残らずペアを作るときに、各個人の希望も考慮して全体としてそこそこ満足のいく組合せを求める方法について紹介します.
この問題は、安定結婚問題と言われる問題と同じです.安定結婚問題では、男女のグループでお互いに異性のよいと思われる順序を決めてそのなかで安定した組合せになるように求めます.このときの安定とは、今の相手以外のどの異性のペアを考えても二人とも希望がさらに満たされることはないことを言います.(駆け落ちがない)
例えば 1とA, 2とBがペアになった時に「1とB」のペアを考えても1もB二人とも今よりよくなることはなく(片方はよくなったとしても)、「2とA」のペアを考えても二人とも今よりよくなることはない状態を安定といいます.
実際の現場でも使用されることのアルゴリズムです.某サイトによれば、病院とナースの組合せ、webサーバとユーザの組合せ等. | 希望順序考慮しいい組合せを見つける |
安定結婚問題の問題設定と
左の組合せの場合の安定解の例
安定であるため、左の場合ペアを変えた場合に新しいペアが今より二人とも喜ぶことはありません. | |
上記のような安定結婚問題では、必ず一つは安定な解があることがわかっています.
安定結婚問題の安定な解はGale-Shapleyのアルゴリズムで求められることが知られています.
手順
1. どちらかのグループに注目する(ここでは男性グループとする)
2. 男性グループのメンバから最も希望の高い順に女性グループにプロポーズをしていく
3. プロポーズされた女性はプロポーズした男性が初めてであれば暫定OKとして、もし過去にプロポーズされ暫定OKをしている場合は、新しい男性がより希望度が高いかどうかで新しい男性に暫定OKを出すかどうか決定します.
4. もし新しい暫定OKによって前の男性がはじき出された場合は、男性が次の希望の女性にプロポーズします.
5. もしプロポーズをして断れた男性がいた場合も、4.同様に次の女性にプロポーズします.
上記をペアのいない男性がいなくなるまで行います.
上記で男性でなく女性にする場合はすべてを逆にしてやってください. | 安定結婚問題の安定な解を見つけられるアルゴリズム(Gale-Shapley) |
安定結婚問題の特徴についてまとめておきます.
・この問題で安定な解は基本的に複数ありえます.
・そのため女性グループに注目してアルゴリズムを回すか男性グループに注目してアルゴリズムを回すかで、結果が異なってきます.
・女性からプロポーズした場合は、女性グループの希望がよく反映された組合せ、男性からプロポーズした場合は、男性グループの希望がよく反映された組合せが見つかります.
・このアルゴリズムはO(N^2)で解を見つける. | 安定結婚問題の特徴 |
Stable Matchingの解説動画
Youtubeにてご覧ください. |
この章を学んで新たに学べる
Comments