Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

安定結婚問題

アルゴリズムC〈第3巻〉グラフ・数理・トピックス』の34章に安定結婚問題という面白そうな問題がありました。男性N人,女性N人がいて,男性も女性もそれぞれ異性に対して高感度をランキングし,その中で結婚相手を探しN組のカップルを決定するという問題です。そのとき,全員の高感度を反映していなければなりません。
本書の例を実際に試してみたいと思います。

男性の選好順位表

A君 => 2, 5, 1, 3, 4
B君 => 1, 2, 3, 4, 5
C君 => 2, 3, 5, 4, 1
D君 => 1, 3, 2, 4, 5
E君 => 5, 3, 2, 1, 4

この表は,A君は,2さん,5さん,1さん…の順で好意を持っていることを表しています。

女性の選好順位表

1さん => E, A, D, B, C
2さん => D, B, E, A, C
3さん => A, D, B, C, E
4さん => C, B, D, A, E
5さん => D, B, C, E, A

安定結婚の安定とは,また不安定とは

不安定とは,

その集団の中に,互いに自分の配偶者よりも相手を好ましいとする夫婦以外の男女の対が存在することをいう

とあります。ちょっと難しいですが,{A1, B3, C2, D4, E5}の結婚は不安定となります。Aは1より2を好み,2はCよりAを好むからです。安定とは不安定でないということなります。

marriage.c

男性をアルファベットで表現してきましたが,簡単のため男性も数字で表します。
2次元配列preferは,男性の選好順位表です。A君がインデックス1に相当します。prefer[1][2]は,A君が2番目に順位付けした女性5さんという意味になります。
2次元配列rankは,女性の選好順位表です。表現の方法がpreferと違って,例えば,rank[1][2]は,1さんがB君(インデックス2)を何に順位付けしているかを表しています。1次元配列fianceeは,女性の婚約中の男性を表しています。

#include <stdio.h>
#define N 5                     /* 人数 */

int main(void)
{
  int prefer[][N+1] = {{0, 0, 0, 0, 0, 0},
                       {0, 2, 5, 1, 3, 4},
                       {0, 1, 2, 3, 4, 5},
                       {0, 2, 3, 5, 4, 1},
                       {0, 1, 3, 2, 4, 5},
                       {0, 5, 3, 2, 1, 4}};
  int rank[][N+1] = {{N+1, 0, 0, 0, 0, 0},
                     {N+1, 2, 4, 5, 3, 1},
                     {N+1, 4, 3, 5, 1, 2},
                     {N+1, 4, 2, 1, 3, 5},
                     {N+1, 5, 2, 3, 1, 4}};
  int next[N+1] = {0};
  int fiancee[N+1] = {0};
  int m, s, w, t, f;
  
  for (m = 1; m <= N; m++) {
    for (s = m; s != 0; ) {
      next[s]++;
      w = prefer[s][next[s]];
      if (rank[w][s] < rank[w][fiancee[w]]) {
        t = fiancee[w];
        fiancee[w] = s;
        s = t;
      }
    }
  }
  
  printf("f -- m\n======\n");
  for (f = 1; f <= N; f++) {
    printf("%d -- %d\n", f, fiancee[f]);
  }
  return 0;
}

実行結果

f -- m
======
1 -- 1(A)
2 -- 4(D)
3 -- 3(C)
4 -- 2(B)
5 -- 5(E)

見辛いですが,左の列が女性,右の列が男性を表します。実行結果の(A)などは,付け加えました。安定結婚問題というネーミングが面白かったので取り組んでみましたが,本文に

データ構造の適切な選択がアルゴリズムの性能に大きく影響する

とあるように,2次元配列rankの使い方や,番兵の使い方は非常に勉強になりました。

さいごに

この題材ですが,他の例として,医学部の卒業生を病院に配属するためにはどうするかといったちゃんとした(??)例の紹介もありました。優秀な学生は多くの病院から指名され,良い病院は多くの学生が希望するというのが,男女の間柄にも似ていて面白いですね。