希望考慮し全ペアいい組合せを見つける

二つのグループから一人残らずペアを作るときに、各個人の希望も考慮して全体としてそこそこ満足のいく組合せを求める方法について紹介します. この問題は、安定結婚問題と言われる問題と同じです.安定結婚問題では、男女のグループでお互いに異性のよいと思われる順序を決めてそのなかで安定した組合せになるように求めます.このときの安定とは、今の相手以外のどの異性のペアを考えても二人とも希望がさらに満たされることはないことを言います.(駆け落ちがない) 例えば 1とA, 2とBがペアになった時に「1とB」のペアを考えても1もB二人とも今よりよくなることはなく(片方はよくなったとしても)、「2とA」のペアを考えても二人とも今よりよくなることはない状態を安定といいます. 実際の現場でも使用されることのアルゴリズムです.某サイトによれば、病院とナースの組合せ、webサーバとユーザの組合せ等.

上記のような安定結婚問題では、必ず一つは安定な解があることがわかっています. 安定結婚問題の安定な解はGale-Shapleyのアルゴリズムで求められることが知られています. 手順 1. どちらかのグループに注目する(ここでは男性グループとする) 2. 男性グループのメンバから最も希望の高い順に女性グループにプロポーズをしていく 3. プロポーズされた女性はプロポーズした男性が初めてであれば暫定OKとして、もし過去にプロポーズされ暫定OKをしている場合は、新しい男性がより希望度が高いかどうかで新しい男性に暫定OKを出すかどうか決定します. 4. もし新しい暫定OKによって前の男性がはじき出された場合は、男性が次の希望の女性にプロポーズします. 5. もしプロポーズをして断れた男性がいた場合も、4.同様に次の女性にプロポーズします. 上記をペアのいない男性がいなくなるまで行います. 上記で男性でなく女性にする場合はすべてを逆にしてやってください.

安定結婚問題の特徴についてまとめておきます. ・この問題で安定な解は基本的に複数ありえます. ・そのため女性グループに注目してアルゴリズムを回すか男性グループに注目してアルゴリズムを回すかで、結果が異なってきます. ・女性からプロポーズした場合は、女性グループの希望がよく反映された組合せ、男性からプロポーズした場合は、男性グループの希望がよく反映された組合せが見つかります. ・このアルゴリズムはO(N^2)で解を見つける.