研究に関する実装がしてみたいと思いプログラミングを始めたはいいものの、気づいたらWeb系言語を触るようになり、結局そっちのエンジニアになることになってしまった。
やれるときにやっておかないと当初の目標が達成できなさそうなので、ここでやる。
扱うのはPythonによる安定マッチング問題の実装である。
安定マッチング問題とは
他の記事で簡潔に説明しているものがあったので引用。
男性のグループと女性のグループが与えられ、男性は女性の選好順序を、女性は男性の選好順序を持っている。男女でペアを作ったときブロッキングペアが存在しないマッチングを安定マッチングという。
ブロッキングペア(m,w)とは、ペアとなっていない男女で「wはmの現在のペアよりも好ましい」「mはwの現在のペア よりも好ましい」状態のペアをいう。
安定マッチング問題は、厳密には最適化問題ではないが、マッチングに関し重要な問題なので典型問題に含めている。ゲイル・シャプレーの解法により効率的に解くことができる。
記事で触れているように、この問題の一般的な解き方として ゲール-シャプレイ アルゴリズム(受け入れ保留アルゴリズムともいう) があり、調べると結構実装してる人がいる。
しかし、この問題には不動点定理というものを用いた解法もある。
多分興味がある人はあまりいないだろうから、かなりざっくり説明すると、プレイヤーの仮のマッチングを用意し、ある関数でそれを更新する。そして更新しても値が変化しなくなればそれが安定マッチングであるという感じだ。
そして嬉しいことに「安定マッチング 不動点」で調べた感じ、プログラミングで実装した記事は出てこなかったのでやってみた。
実装の流れ
- プレイヤーと選好を定義する
- プレマッチングを用意する
- 片側は最も好ましい相手と仮マッチさせる
- 反対側は誰ともマッチしていない状態にする
- 各プレイヤーについて以下の操作を行う
- 現在のプレマッチング相手よりも自分を好ましく思うプレイヤーの中から、最も好ましい相手とプレマッチングする
- これを繰り返し、プレマッチングが変化しなくなったら終了
これに従い実装する。
プレイヤーと選好を定義する
M = [[],
[1, 2, 3, 0], #男性1の選好順序
[1, 3, 2, 0], #男性2の選好順序
[2, 1, 0], #男性3の選好順序
[2, 1, 1, 0]] #男性4の選好順序
W = [[],
[3, 1, 2, 0], #女性1の選好順序
[2, 1, 3, 0], #女性2の選好順序
[2, 3, 1, 0], #女性3の選好順序
]
男性4人、女性3人の問題を考える。
各配列は選好順序を意味しており、左側がより好ましい相手。
この図の場合は男性1は女性1,2,3の順に好ましく思う。
一番上の空配列は配列番号を合わせるためのダミーである。またマッチング相手が0であるとは誰ともマッチングしていないことを意味する。
プレマッチングを用意する
import copy
Pre_M = [0] * len(M)
Pre_W = [len(w) - 1 for w in W]
# 更新前と更新後を比較するための変数を用意する
Renew_M = copy.deepcopy(Pre_M)
Renew_W = copy.deepcopy(Pre_W)
プレマッチングの数字は各選好の配列番号を意味する。例えばここでは、全男性は選好配列の配列番号0の相手と、すなわち最も好ましい相手と仮マッチしている。女性はその逆である。
アルゴリズム開始
while True:
for m in range(1, len(M)):
for w in M[m][Pre_M[m]:]:
if m in W[w][:Pre_W[w] + 1]:
Renew_M[m] = M[m].index(w)
break
else:
Renew_M[m] = len(M[m]) - 1
for w in range(1, len(W)):
for m in W[w][:Pre_W[w] + 1]:
if w in M[m][:Pre_M[m] + 1]:
Renew_W[w] = W[w].index(m)
break
if Pre_M == Renew_M and Pre_W == Renew_W:
for m in range(1, len(M)):
print(f'm{m} - w{M[m][Pre_M[m]]}')
break
else:
Pre_M = Renew_M
Pre_W = Renew_W
先程の初期設定に対しこれを実行すると、出力は
m1 - w1
m2 - w3
m3 - w2
m4 - w0
となる。これはG-Sアルゴリズムの男性側からの実行結果と一致する。
少し細かく分けてみていく。
for m in range(1, len(M)):
for w in M[m][Pre_M[m]:]:
if m in W[w][:Pre_W[w] + 1]:
Renew_M[m] = M[m].index(w)
break
else:
Renew_M[m] = len(M[m]) - 1
for w in M[m][Pre_M[m]:]:
この問題ではプレマッチングは単調に変化するためこのように書くことができる。更新するたびに男性は現在のプレマッチング相手以下の選好順序の相手とマッチする。
m in W[w][:Pre_W[w] + 1]
指定した相手が、現在のプレマッチング相手よりも自分を好ましく思うなら、更新が行われる。そして誰とも更新できなければ、
Renew_M[m] = len(M[m]) - 1
で0とマッチング、すなわち誰ともマッチングしないということになる。
これと似たような流れを女性側でも実行したら、
if Pre_M == Renew_M and Pre_W == Renew_W: # 不動点に到達
for m in range(1, len(M)):
print(f'm{m} - w{M[m][Pre_M[m]]}')
break
else: #プレマッチング更新
Pre_M = Renew_M
Pre_W = Renew_W
こんな感じである。以上まとめると
import copy
M = [[],
[1, 2, 3, 0],
[1, 3, 2, 0],
[2, 1, 0],
[2, 1, 1, 0]]
W = [[],
[3, 1, 2, 0],
[2, 1, 3, 0],
[2, 3, 1, 0],
]
Pre_M = [0] * len(M)
Pre_W = [len(w) - 1 for w in W]
Renew_M = copy.deepcopy(Pre_M)
Renew_W = copy.deepcopy(Pre_W)
while True:
for m in range(1, len(M)):
for w in M[m][Pre_M[m]:]:
if m in W[w][:Pre_W[w] + 1]:
Renew_M[m] = M[m].index(w)
break
else:
Renew_M[m] = len(M[m]) - 1
for w in range(1, len(W)):
for m in W[w][:Pre_W[w] + 1]:
if w in M[m][:Pre_M[m] + 1]:
Renew_W[w] = W[w].index(m)
break
if Pre_M == Renew_M and Pre_W == Renew_W:
for m in range(1, len(M)):
print("m{0} - w{1}".format(m, M[m][Pre_M[m]]))
break
else:
Pre_M = Renew_M
Pre_W = Renew_W
最後に
いつか自分の研究している分野に関する実装をしてみたいと思っていたので、この機会に達成できてよかった。Pythonはあまりたくさん書くわけではないので、改善の余地はあると思うがまあよし！