Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Irving

コードについての説明(個人的メモ)

GaleSharpley アルゴリズムの場合とは異なり, 戦略を取る主体が $1$ グループの場合の安定マッチングを求めるアルゴリズムである. 言い方を変えると GaleSharpley のアルゴリズムは完全二部グラフ上の安定マッチングを求めていたのに対しこのアルゴリズムは完全グラフ上の安定マッチングを求めるアルゴリズムとなっている.
安定ルームメイト問題とも呼ばれ、 $n$ 人($n$ は偶数とする) のグループがいたときに各メンバーが他の $n-1$ 人に対する優先順位のリストを持っていて誰と誰が roommate になるかをマッチングするというような状況である.
この場合の blocking pair も安定結婚問題と同様にあるペアでそれぞれのマッチング相手が今見ているペアの相手よりも優先順位より低い場合のことをいい、 そのような blocking pair の存在しないマッチングを安定マッチングと呼ぶ. この問題において, 安定マッチングは常に存在するとは限らず Irving のアルゴリズムは安定マッチングが存在する場合にのみその $1$ つを返し, そうでない場合は存在しないと判定する.
元論文は "An Efficient Algorithm for the “Stable Roommates” Problem" [Irving 1985]"

(関数)
solve$(\_ pref)$ : 優先度の高い順に相手の ID を格納した行列($n \times (n-1)$ で $n$ は偶数) を渡す(存在しない場合は要素数 $0$ の vector を返す).

時間計算量: $\O (n^2)$

コード

  1. class Irving
  2. {
  3. private:
  4.     int n;
  5.     vector<list<int> > pref;
  6.     vector<vector<list<int>::iterator> > pref_iter;
  7.     vector<vector<int> > order;
  8.     list<int> pref_index;
  9.     vector<list<int>::iterator> pref_index_iter;
  10.     bool _erase(int num1, int num2)
  11.     {
  12.         pref[num1].erase(pref_iter[num1][order[num1][num2]]);
  13.         pref[num2].erase(pref_iter[num2][order[num2][num1]]);
  14.         return pref[num1].empty() || pref[num2].empty();
  15.     }
  16.     bool __erase(int num1, int num2)
  17.     {
  18.         pref[num1].erase(pref_iter[num1][order[num1][num2]]);
  19.         pref[num2].erase(pref_iter[num2][order[num2][num1]]);
  20.         if(pref[num1].size() == 1) pref_index.erase(pref_index_iter[num1]);
  21.         if(pref[num2].size() == 1) pref_index.erase(pref_index_iter[num2]);
  22.         return pref[num1].empty() || pref[num2].empty();
  23.     }
  24.     bool reduction(const vector<int>& cand)
  25.     {
  26.         pref_index_iter.resize(n);
  27.         for(int i = 0; i < n; ++i){
  28.             if(cand[i] < 0) continue;
  29.             for(auto it = --pref[i].end(); *it != cand[i]; it = --pref[i].end()){
  30.                 if(_erase(i, *it)) return true;
  31.             }
  32.             if(pref[i].size() > 1){
  33.                 pref_index.push_back(i);
  34.                 pref_index_iter[i] = --pref_index.end();
  35.             }
  36.         }
  37.         return false;
  38.     }
  39.     bool phase1()
  40.     {
  41.         stack<int> single;
  42.         for(int i = 0; i < n; ++i){
  43.             single.push(i);
  44.         }
  45.         vector<int> cand(n, -1);
  46.         while(!single.empty()){
  47.             int u = single.top();
  48.             single.pop();
  49.             while(true){
  50.                 int v = *pref[u].begin();
  51.                 if(cand[v] < 0){
  52.                     cand[v] = u;
  53.                     break;
  54.                 }else if(order[v][cand[v]] > order[v][u]){
  55.                     single.push(cand[v]);
  56.                     if(_erase(v, cand[v])) return true;
  57.                     cand[v] = u;
  58.                     break;
  59.                 }else{
  60.                     if(_erase(v, u)) return true;
  61.                 }
  62.             }
  63.         }
  64.         return reduction(cand);
  65.     }
  66.     int eliminate(unique_ptr<bool[]>&& visit, int cur)
  67.     {
  68.         list<int> pseq;
  69.         while(!visit[cur]){
  70.             pseq.push_back(cur);
  71.             visit[cur] = true;
  72.             cur = *(--pref[*(++pref[cur].begin())].end());
  73.         }
  74.         list<int>::iterator it = pseq.begin();
  75.         for(;;++it){
  76.             visit[*it] = false;
  77.             if(*it == cur) break;
  78.         }
  79.         list<pair<int, int> > elim;
  80.         for(;it != pseq.end(); ++it){
  81.             visit[*it] = false;
  82.             elim.emplace_back(*it, *(++pref[*it].begin()));
  83.         }
  84.         for(pair<int, int>& value : elim){
  85.             int p = value.first, q = value.second;
  86.             if(*pref[p].begin() != q){
  87.                 if(__erase(p, *pref[p].begin())) return -1;
  88.             }
  89.             for(auto it = --pref[q].end(); *it != p; it = --pref[q].end()){
  90.                 if(__erase(q, *it)) return -1;
  91.             }
  92.         }
  93.         return cur;
  94.     }
  95.     bool phase2()
  96.     {
  97.         if(pref_index.empty()) return false;
  98.         unique_ptr<bool[]> visit(new bool[n]());
  99.         int start = *pref_index.begin();
  100.         do {
  101.             if(pref[start].size() == 1) start = *pref_index.begin();
  102.             if((start = eliminate(move(visit), start)) < 0) return true;
  103.         }while(!pref_index.empty());
  104.         return false;
  105.     }
  106. public:
  107.     Irving(){}
  108.     vector<int> solve(const vector<vector<int> >& _pref)
  109.     {
  110.         n = (int)_pref.size();
  111.         assert(n % 2 == 0);
  112.         pref.resize(n);
  113.         pref_iter.resize(n, vector<list<int>::iterator>(n-1));
  114.         order.resize(n, vector<int>(n));
  115.         for(int i = 0; i < n; ++i){
  116.             for(int j = 0; j < n-1; ++j){
  117.                 pref[i].push_back(_pref[i][j]);
  118.                 pref_iter[i][j] = --pref[i].end();
  119.                 order[i][_pref[i][j]] = j;
  120.             }
  121.         }
  122.         if(phase1()) return vector<int>();
  123.         if(phase2()) return vector<int>();
  124.         vector<int> ans(n);
  125.         for(int i = 0; i < n; ++i){
  126.             ans[i] = *pref[i].begin();
  127.         }
  128.         return ans;
  129.     }
  130. };

verify 用の問題

verify していません(verify 問題を知らない)