%reload_ext autoreload
%autoreload 2
%matplotlib inline
%load_ext lab_black
import random
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
m, n = 3, 4
G = nx.grid_2d_graph(m, n)
pos = {(i, j): (i, j) for (i, j) in G.nodes()}
plt.figure()
nx.draw(G, pos=pos, node_size=100)
plt.show()
edges = nx.maximal_matching(G)
nx.draw(G, pos=pos, width=5, node_size=10, edgelist=edges, edge_color="orange")
plt.show()
edges = nx.max_weight_matching(G)
nx.draw(G, pos=pos, width=5, node_size=10, edgelist=edges, edge_color="orange")
plt.show()
最小費用の完全マッチングも求めたい場合には，枝の重みを負に設定すれば良い． この場合には，引数のmaxcardinalityをTrueに設定して，枝の本数を最大にする必要がある．
lb, ub = 1, 20
for (i, j) in G.edges():
G[i][j]["weight"] = -random.randint(lb, ub)
edges = nx.max_weight_matching(G, maxcardinality=True)
plt.figure()
nx.draw(G, pos=pos, node_size=100)
edge_labels = {}
for (i, j) in G.edges():
edge_labels[i, j] = f"{ G[i][j]['weight'] }"
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
nx.draw(G, pos=pos, width=5, edgelist=edges, edge_color="orange")
plt.show()
安定マッチング問題
最も基本的な安定マッチング問題は，安定結婚問題(stable marriage problem)とよばれ，以下のように定義される．
２つの異なる集合 $S, R$ が与えられており， 2つの集合で構成される2部グラフの完全マッチング $M$ を求めたい． 各集合（古典的には男女の集団と仮定されるが，ここではsuitorとreviewerとする）には， $S$ と $R$ の各要素 $s,r$ は， 別の集合の要素に対する選好(preference) を全順序 $\prec_s, \prec_r$ として持っている．
以下の条件を満たすような組 $(s,r)$ がないマッチング $M$ を安定マッチングとよぶ．
- $（s，r）$ は $M$ に含まれない．
- $(s,r') \in M$ となる $r'$ に対して $r \prec_s r'$ となる（すなわち $s$ さんは，マッチングされていない $r$ さんの方が好きである）．
- $(s',r) \in M$ となる $s'$ に対して $s \prec_r s'$ となる（すなわち $r$ さんも，マッチングされていない $s$ さんの方が好きである）．
具体的な例で説明しよう．
$n$ 箇所の病院の集合 $H$ と $n$ 人の学生のマッチングを求めたい． 各病院 $h$ は学生の選好順 $student[h]$ をもち，各学生 $s$ は病院の選好順 $hospital[s]$ をもつ． 病院 $h$ が割り当てられている学生 $s'$ より $s$ を選好し，学生 $s$ が割り当てられている病院 $h'$ より $h$ を選好しているとき，$(h,s)$ を不安定ペア (unstable pair) とよぶ， 病院と学生の完全マッチングで，不安定ペアが存在しないものを安定マッチング (stable matching)とよぶ．
1つの（病院最適な）安定マッチングを算出するGale-Shapleyのアルゴリズム（以下の論文に基づく）を示す．
David Gale and Lloyd Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962
- 空の集合からなるマッチング $M$ を準備する．
- 学生が割り当てられていない病院 $h$ がなくなるまで，以下を実行する．
- $h$ の選好リストの先頭の学生 $s$ を選択し，プロポーズする．
- $s$ が未割り当てなら，マッチング $M$ に $(h,s)$ を追加する．
- $s$ にすでに割り当てられている病院 $h'$ より $h$ を選好するなら，$M$ から $(h',s)$ を除き $(h,s)$ を追加する．
- そうでないなら，$h$ は拒否される．
安定マッチング問題の解説と実装方法については，以下のビデオを参照されたい．
簡単な $O(n^2)$ 時間の実装を以下に示す．
student_pref = np.array([[0, 1, 2], [1, 0, 2], [0, 1, 2]])
hospital_pref = np.array([[1, 0, 2], [0, 1, 2], [0, 1, 2]])
top_student = [0, 0, 0]
n = len(student_pref)
hospital_rank = np.zeros((n, n), dtype=int)
for s in range(n):
for i in range(n):
hospital_rank[s, hospital_pref[s, i]] = i
hospital_list = list(range(n))
student = [-1 for i in range(n)]
hospital = [-1 for i in range(n)]
while hospital_list:
print("Unassigned Hospital=", hospital_list)
h = hospital_list.pop(0)
print(h)
s = student_pref[h, top_student[h]]
top_student[h] += 1
print(h, "proposes to", s)
if hospital[s] == -1: # 未割り当て
student[h] = s
hospital[s] = h
elif hospital_rank[s, h] < hospital_rank[s, hospital[s]]:
print("Student", s, " is assigned to Hospital", h)
hospital_list.append(hospital[s])
student[h] = s
hospital[s] = h
else:
print(h, "is rejected")
hospital_list.append(h)
print("Student=", student)
print("Hospital=", hospital)
なお， 以下のパッケージで，安定マッチング問題を含む様々な問題を解くことができる．
安定ルームメイト問題
類似の問題として安定ルームメイト問題(stable roommates problem)がある． 以下のように定義される．
集合 $P$ (player) が与えられており， その要素数は偶数であると仮定する． $P$に対する完全マッチング $M$ （部屋割を表す）を求めたい． $P$ の各要素 $p$ は， 自分以外の人に対する選好を全順序 $\prec_p$ として持っている．
以下の条件を満たすような組 $(s,r)$ がないマッチング $M$ を安定マッチングとよぶ．
- $（s，r）$ は $M$ に含まれない．
- $(s,r') \in M$ となる $r'$ に対して $r \prec_s r'$ となる（すなわち $s$ さんは，マッチングされていない $r$ さんの方が好きである）．
- $(s',r) \in M$ となる $s'$ に対して $s \prec_r s'$ となる（すなわち $r$ さんも，マッチングされていない $s$ さんの方が好きである）．
安定ルームメイト問題に対する安定マッチングも，安定マッチングで紹介したパッケージで解くことができる．