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 問題を知らない)