Search on the blog

2014年7月19日土曜日

Gale-Shapleyアルゴリズム

 最近、安定結婚問題に基づいてパートナーを決める出会い系アプリに関する記事を読みました。安定結婚問題を解くGale-Shapleyアルゴリズムが面白そうだったので勉強してみました。

安定結婚問題とは?
N人の男とN人の女がいる。N組のカップルを作りたい。
ただし、駆け落ちする人が現れないようにカップルを作りたい。

「駆け落ち」が起こりえる条件は、
  1. 自分のパートナーよりも、好きな人(A)が別にいる
  2. Aさんも、Aさん自身のパートナーより自分のことを好きでいてくれる
である。

Gale-Shapleyアルゴリズムとは?
安定結婚問題を解くためのアルゴリズムで、以下のような手続きをパートナーのいない男がいなくなるまで繰り返します。
  1. パートナーがいない男(X)は、まだプロポーズをしたことのない相手の中で一番好きな人にプロポーズをする。
    1. プロポーズされた女は、
      1. フリーの場合、そのプロポーズを受け入れる。
      2. すでに婚約中の場合、
        1. 今の婚約相手よりもXの方が魅力的であれば、今の婚約相手を振って、Xのプロポーズを受け入れる。
        2. Xよりも今の婚約相手の方が魅力的であれば、Xのプロポーズを断る。

    このアルゴリズムが本当に正しく動作するのか考えてみました。

    ーまず、このアルゴリズムは停止するのか?

    アルゴリズムは、パートナーがいない男が存在する間は停止しない。パートナーという関係は男集合から女集合へのbijectiveな写像なので、「パートナーがいない男が存在する」と「パートナーがいない女が存在する」は同値。

    女は、一度でもプロポーズされると、それ以降はうまく男をキープすることで常にパートナーのいる状態を継続できる。よって、すべての女が一度でもプロポーズをされたことがある状態になるとこのアルゴリズムは停止する。

    男はN人いて、それぞれの男には1位からN位まで女をランク付けしたリストがあり、それにしたがってプロポーズしていくので、プロポーズという行為が全体でN * N回行われた時点でアルゴリズムは停止する。

    よって計算量はO(N2)。

    ーアルゴリズムが停止したときのマッチングには、ブロッキングペア(駆け落ちが発生するようなペア)が存在しないか?

    m1はf1よりf2の方が好き、かつ、f2はm2よりm1の方が好きであるにも関わらず、アルゴリズムが停止したとき、(m1, f1)、(m2, f2)というペアがえられたと仮定する。

    しかしこの場合、m1はf1にプロポーズする前にf2にプロポーズしているはずで、f2はそのプロポーズを受け入れているはずである。よってそのようなペアは存在しない。

    ソースコード
    C++で書いたソースコードを貼りつけておきます。Gale-Shapleyアルゴリズムの処理は関数process()で行なっています。
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <cassert>
    
    using namespace std;
    
    const int N = 100;
    
    int male[N][N];    // j-th favorite of i-th male is male[i][j]
    int female[N][N];  // j-th favorite of i-th female is female[i][j]
    
    int rmale[N][N];   // for i-th male, j-th female is rmale[i][j]-th place
    int rfemale[N][N]; // for i-th female, j-th male is rfemale[i][j]-th place
    
    int match[N];      // i-th female is engaged to match[i]-th male
    
    void read() {
    
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> male[i][j];
                rmale[i][male[i][j]] = j;
            }
        }
    
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> female[i][j];
                rfemale[i][female[i][j]] = j;
            }
        }
    
    }
    
    void process() {
    
        fill(match, match + N, -1);
    
        queue<pair<int, int> > q;
        
        for (int i = 0; i < N; i++) {
            // i-th male is trying to propose his first favorite
            q.push(make_pair(i, 0));
        }
        
        while (!q.empty()) {
            int m = q.front().first;
            int order = q.front().second;
            q.pop();
    
            int f = male[m][order];
    
            // The proposed female is free.
            if (match[f] == -1) {
                match[f] = m;
            } 
            // The proposed female is engaged but switches over to him.
            else if (rfemale[f][m] < rfemale[f][match[f]]) {
                int dumped = match[f];
                match[f] = m;
                q.push(make_pair(dumped, rmale[dumped][f] + 1));
            } 
            // The proposed female is engaged and rejects him.
            else {
                q.push(make_pair(m, order + 1));
            }
        }
    
    }
    
    void write() {
    
        for (int i = 0; i < N; i++) {
            cout << i << " th female is engaged to " << match[i] << " th male." << endl;
        }
    
    }
    
    void check() {
    
        for (int f1 = 0; f1 < N; f1++) {
    
            int m1 = match[f1];
    
            for (int f2 = 0; f2 < N; f2++) {
    
                if (f1 == f2)
                    continue;
    
                int m2 = match[f2];
    
                // m1 won't elope with another female.
                assert(rmale[m1][f1] < rmale[m1][f2] || rfemale[f2][m2] < rfemale[f2][m1]);
    
                // f1 won't elope with another male.
                assert(rfemale[f1][m1] < rfemale[f1][m2] || rmale[m2][f2] < rmale[m2][f1]);
                
            }
        }
    
    }
    
    int main(int argc, char **argv) {
    
        read();
    
        process();
    
        write();
        
        check();
        
        return 0;
    }
    

    0 件のコメント:

    コメントを投稿