Gale Sharpley
コードについての説明(個人的メモ)
$2$ 種類のグループ(男女など)の間での安定マッチングを求めるアルゴリズム. このような問題を安定結婚問題とも言う.
男女それぞれが相手のグループのメンバーに対しての優先順位を持っているとする. ここである男 $i$, 女 $j$ について $i$ が $j$ よりも優先順位の低いメンバーとマッチングしていて, $j$ も $i$ より優先順の低いメンバーとマッチングしているとき、このようなペアを blocking pair とする.
このような blocking pair の存在しないマッチングを安定マッチングと呼ぶ. このようなマッチングは常に存在することが GaleSharpley のアルゴリズムから構成的に分かる.
元論文は "College Admissions and the Stability of Marriage" [Gale Sharpley 1962]
(関数)
solve$(mpref, wpref)$ : 優先度の高い順に相手の ID を格納した行列を $2$ つ渡す(男性が申し込む場合の実装である).
時間計算量: $\O (n^2)$
コード
- class GaleSharpley
- {
- public:
- GaleSharpley(){}
- vector<int> solve(const vector<vector<int> >& mpref, const vector<vector<int> >& wpref)
- {
- int n = mpref.size();
- vector<vector<int> > worder(n, vector<int>(n));
- stack<int> single;
- for(int i = 0; i < n; ++i){
- single.push(i);
- for(int j = 0; j < n; ++j){
- worder[i][wpref[i][j]] = j;
- }
- }
- vector<int> id_pos(n, 0);
- vector<int> wtom(n, -1);
- while(!single.empty()){
- int man = single.top();
- single.pop();
- while(true){
- int woman = mpref[man][id_pos[man]++];
- if(wtom[woman] < 0){
- wtom[woman] = man;
- break;
- }else if(worder[woman][wtom[woman]] > worder[woman][man]){
- single.push(wtom[woman]);
- wtom[woman] = man;
- break;
- }
- }
- }
- vector<int> mtow(n);
- for(int i = 0; i < n; ++i)
- mtow[wtom[i]] = i;
- return mtow;
- }
- };
verify 用の問題
verify していません(verify 問題を知らない)