ハミルトングラフ･研修医マッチング

プロジェクト発表会
野村プロジェクト
グラフ理論班 ハミルトングラフ
１．発表に至る経緯
私たちグラフ理論班は前期中にオイラーグラフ、ハミルトングラフ、最大流問題、マッチ
ング問題について各個人がまとめたことを他のメンバーの前で発表をする輪読形式で勉強
をしてきた。その中で今回はハミルトングラフとそれに通ずるバックトラック法、分枝限
定法について簡単ではあるが紹介する。
グラフというと多くの人がよくテレビニュースで見る棒グラフや折れ線グラフを思い浮か
べるであろう。しかし点と線で結ばれた図もグラフであり、これを用いて現象を解析する
のがグラフ理論である。
２．ハミルトングラフとは
グラフのすべての頂点を含む閉路をハミルトン閉路という。すべてのノード(頂点)を含む
道をハミルトン道という。そして、ハミルトン閉路を含むグラフをハミルトングラフとい
う。
・閉路…始点と終点が同じ場所であること(バスが同じ地点を一周するようなイメージ)
・道…頂点と辺の集まりを持つグラフのこと。始点と終点が違ってもよい。
ハミルトン閉路を用いたものとして巡回セールスマン問題が良く知られている。巡回セ
ールスマン問題とは「重みのついたグラフにおいて、すべての頂点をちょうど１回通る閉
路の中で最も重みの小さいものを求める」ということ。例えば宅配業者が複数の配達先に
向かう際に複数の道があるとする。ハミルトン閉路を用いれば最短のルートを知ることが
でき、仕事の効率も向上する。
ハミルトン閉路を求めるアルゴリズムは以下の通り
入力：辺に重みのついた完全グラフ Kn と始点 s
出力：ハミルトン閉路 C
1.
i=1,v1=s,W1=v1 とする。
2.
i=n ならば、C=Wi+1 として終了。
3.
V(G)の中でまだ選んでいない頂点 u の中で w({vi,u})が最小のものを vi+1 と
して選び、Wi の最後に Vi+1 を加え、Wi+1 とする。
4.
i=i+1 とする。
5.
i=n ならば、Wi の最後に vi を加え、Wi+1 とし、2 へ戻る。i≠n ならば、
3 へ戻る。
右図のグラフに上記のアルゴリズムを適用すると、閉路 s-a-b-c-s、重み 10 となる。
だが閉路 s-b-a-c-s とした方が、重みは 9 となり、効率はいい。
この方法にはある問題点が存在する。それはこのアルゴリズムが単純に「最短経路」を取
っていることである。
最短経路を通っているので、結果的に長い道を通ることにつながってしまう。だが、すべ
ての道をそのまま調べるのはよくない。では効率よく調べる方法はないのだろうか。
３．バックトラック法の適用
バックトラック法…これ以上の探索が無駄だと感じたら引き返すこと
先ほどのハミルトングラフを例にして考える
このハミルトン閉路を木構造で表す。辺についている数字は重み。
完全グラフ Kn のハミルトン閉路は(n-1)!個存在する。
これをどうバックトラックする方法
→最も長い重みを持つ辺を通る場合は探索をやめて 1 つ前に戻る。
この図を見ると重み５の部分は通らないほうが良いと分かる。例えば Sac と続いた次に b
を通れるが重みは５なので通らずにひとつ前に戻る。
この考えを用いれば、重み 9 のハミルトン閉路を求めることができる(SbacS か ScabS)。
とはいっても、どのような重みをもつ完全グラフ Kn についても最短の重みであるハミルト
ン閉路を出力する方法であるかは証明できていない。
４．分子限定法の適用
分枝限定法は「重みが現時点での最短距離を超えてしまう場合は戻る」という考えのも
とで行われるアルゴリズムである。分枝限定法には以下の２つの手続きが必要である。
・分枝：ある集合 S に対してこれをS = S! ∪ S! ∪ …となるように分割する。
・限定：S の１つの部分集合𝑆! のf 𝑥 の最小値の上限と下限を計算する手続き。
ある集合 A の下限が B の上限より大きければ A は探索する必要がないという考え方。
例：A の下限が 10、B の上限が 7 だとしたら A は調べる必要がなくなる。
・実際に考えてみる
通常は制約条件を満たす実数最適解から得た近似解を、目的関数に代入して求めた値を暫
定値とするが、ここでは「ハミルトン閉路を求めるアルゴリズム」から得た重みを暫定値
とする。図において、ハミルトン閉路を求めるアルゴリズムを適用すると SabcS という解
が得られる。これより、暫定値は 10 となる。
S からスタート。
まずは S-a と進む。（この時点での重み：１）
S-a-c と進む。（重み：４）
S-a-c-b と進む。（重み：９）
S-a-c-b-S と進みたいが、重み≥暫定値(10 ≥ 10)となるので S-a まで戻る。
S-a-b と進む。（重み：２）
S-a-b-c と進む。（重み：７）
S-a-c-b-S と進みたいが、重み≥暫定値(10 ≥ 10)となるので S-a まで戻る。
S-a において、これ以上経路は見つからない。よって、S にもどる。
次に、S-b と進む。（この時点での重み：２）
S-b-a と進む。（重み：３）
S-b-a-c と進む。（重み：６）
S-a-c-b-S と進んでも、重み≤暫定値(9 ≤ 10)となるので暫定値を更新。
暫定値＝９とし S-b まで戻る。
S-b-c と進む。（重み：７）
S-b-c-a と進みたいが。重み≥暫定値(10≥ 10)となるので S-b まで戻る。
S-b において、これ以上経路は見つからない。よって、S にもどる。
次に、S-c と進む。（この時点での重み：３）
S-c-a と進む。（重み：６）
S-c-a-b と進む。（重み：７）
S-c-a-b-S と進みたいが、重み≥暫定値(9 ≥ 9)となるので S-c まで戻る。
S-c-b と進む。（重み：９）
S-c-b-a と進みたいが、重み≥暫定値(9 ≥ 9)となるので S-c まで戻る。
S-c において、これ以上経路は見つからない。よって、S にもどる。
探索終了。解は S-a-c-b-S、重みは 9 となる。
結果として、アルゴリズムで求めた解より良い解が求められた。
・他のアルゴリズムと比較する
アルゴリズムとの比較
ここでは比較回数と、出力する結果を元にして比較を行う。また、比較を最大何回行うか
を考える。対象とするグラフは完全グラフ Kn(n>3)。
（A）ハミルトン閉路を求めるアルゴリズム
n 個のデータの最小値を求めるアルゴリズム（というか処理）の比較回数は n-1 回
下記は最小値を求める処理である。
完全グラフ Kn においては、最初は n-1 個の辺、次に n-2 個の辺の選択肢がある。よって、
まず n-1 個の辺の内から重みが最小の辺を探し、次に n-2 個の辺の内から重みが最小の辺
を探す。
よって計算式は…(n-1)-1+(n-2)-1+…+(1)-1。これをΣで表すと
!!!
!!! 𝑛
!
!
!
!
− 1 = 𝑛! − 𝑛 + 1と
なる。
!
!
!
!
比較回数は 𝑛! − 𝑛 + 1となる。最後に S に戻る際に重みを足すことになるがこれは比較を
していないのでカウントしないこととする。頂点の個数が n のグラフについて、そのグラ
フが完全グラフでない限りは、比較回数はこれより小さくなるはずである。
また、出力結果について、重みが最短の閉路を出すことはできない。
（B）分枝限定法
!
!
!
!
まず、暫定値を求める際に（A）のアルゴリズムを使っているので、比較回数は 𝑛! − 𝑛 + 1回
以上となる。先ほどの木構造のグラフにおいて、比較を最大何回行うか考えてみる。各々
の辺に対して、「重み≥暫定値となるかどうか」を比較する。よって、分枝限定法で用いら
れるグラフの辺の本数が比較回数となる。漸化式を用いて表すとa! = 6, 𝑎! = 𝑛 − 1 𝑎!!! +
!
!
!
!
(𝑛 − 1)となる。各 n について比較回数が 𝑛! − 𝑛 + 1回分（暫定値を求めるための比較回
数）だけプラスされることになる。
また、出力結果について、重みが最短の閉路を出すことができる（極論、総当たり法なの
で、確実に最短閉路を出すことができる）。
以下に(A)と(B)でのノードの数の違いによる比較回数の違いを表にして表した。
(A )アルゴリズム
ノード数 比較回数
3
1
4
3
5
6
6
10
7
15
8
21
9
28
10
36
11
45
12
55
13
66
14
78
15
91
16
105
17
120
18
136
19
153
20
171
(B )分枝限定法
ノード数 比較回数
3
7
4
24
5
94
6
455
7
2,691
8
18,760
9
149,948
10
1,349,325
11
13,492,945
12
148,421,966
13
1,781,063,010
14
23,153,818,363
15
324,153,456,095
16
4,862,301,840,180
17
77,796,829,441,336
18
1,322,546,100,500,820
19
23,805,829,809,012,600
20
452,310,766,371,236,000
分枝限定法はほぼ確実に最短経路を出すことができるのは先ほど説明したが、表からも分
かるようにアルゴリズムを用いた時と比べて計算量の数が爆発的に増えてしまうという問
題を抱えている。
研修医マッチング
１．はじめに
臨床研修制度とは医学部を卒業した医師たちが病院で実地研修を行う仕組みである。こ
の制度の導入に合わせ、どの研修医がどの病院で研修をするかの組み合わせ（マッチング）
を明確なルールに従って決める「研修医マッチング」という制度が実施された。研修医マ
ッチングとは、病院側、医師側双方にどの相手とマッチした以下の希望順位表を提出させ、
それを元に誰をどこにマッチさせるかを決定する手続きである。
マッチングの仕方はいくつも考えることができ、今回は Deferred Acceptance（DA）ア
ルゴリズム、Japan Residency Matching Program（JRMP）アルゴリズム、繰り返し DA
アルゴリズム、Flexible Deferred Acceptance（FDA）アルゴリズムの４つについてそれが
どのような特徴をもっているのかを述べていく。また、それぞれのどのような特徴が重要
視されるのかを議論するために、よいアルゴリズムとはどのようなものなのかを定義する。
２．マッチングのモデル
①n 個の病院 h1,h2,h3…hn、m 人の医師 d1,d2,d3…dm がいる。
②各病院はどの医師を雇用したいかについて希望順位表を持っている。
EX)h1 の希望表が「d1,d3,d5」⇒第 1 候補：d1、第 2 候補：d3、第 3 候補：d5
③各医師はどの病院に勤務したいかについて希望順位表を持っている。
EX) d1 の希望表が「h1,h3」⇒第 1 候補：h1、第 2 候補：h3
④各病院には「定員」があり、その定員以上雇うことはできない。
⑤マッチングμは「どの医師がどこで働くか」
「どの病院でどの医師が働くか」を記述する。
EX)μ(d1)=h1：d1 は h1 で働く。 μ(h1)={d2,d3}：h1 は d2,d3 を雇う。
μ(h3)=φ：h3 は誰も雇わない。
ここでは現実に即し、各医師は 1 つの病院にしかマッチできず、各病院は定員までなら何
人でもマッチできるとする。
３．よいマッチングの定義
定義１：マッチングの安定性⇒メカニズムの安定性
マッチングμが安定であるとは、以下の 2 つの条件が成り立つことを言う。
a.どの病院もどの医師も、μにおいて希望順位表に乗っていない相手とはマッチしていな
い。
b.もし病院 h が医師 d の希望順位表でμ(d)よりも上位にあり、d が h の希望順位表に乗
っているならば、μにおいて h とマッチしている医師はみんな h にとって d よりもよ
く、かつ h の定員は満たされている。
メカニズムが安定であるとは、どんな希望順位表が与えられたとしても、安定なマッチ
ングを生成することを意味する。
定義２：メカニズムの対戦略性
メカニズムが対戦略性を持つとは、他の医師及び病院がどのような希望順位表を提出す
るかに関わらず、医師は嘘をついても得をしないことを意味する。
・定義 1b の具体例を交えて書き換えてみると…
μ(d1)=h2、μ(h1)=d2 とし、d1 の希望表が「h1,h2」、h1 の希望表が「d2,d1」、h1 の定員は１
とする。
「もし病院 h が医師 d の希望順位表でμ(d)よりも上位にあり、d が h の希望順位表に乗っ
ている」
⇒h1 は d1 の希望順位表でμ(d1)=h2 よりも上位にある。また、h1 の希望表に d1 は存在する。
「μにおいて h とマッチしている医師はみんな h にとって d よりもよく、かつ h の定員は
満たされている。」
⇒h1 とマッチしている医師 d2 は、h1 の希望順位表より、d1 より雇いたい人物。かつ h1 の
定員は満たされている。
よって…
h1 は d1 の希望順位表でμ(d1)=h2 よりも上位にある。また、h1 の希望表に d1 は存在するの
で、d1 は h1 に雇われたいが、h1 にとっては d1 より d2 の方が雇いたい人物なので、d1 を雇
う意味はない。
・定義 1b が成り立たない状況とは？
μ(d1)=h2、μ(h1)=d2 とし、d1 の希望表が「h1,h2」、h1 の希望表が「d1,d2」、h1 の定員は１
とする。
○医師 d1 は d1 の希望順位表より、μ(d1)=h2 より h1 とマッチしたい。
○病院 h1 はμ(h1)=d2 であるが、h1 の希望順位表より d2 を解雇して d1 を雇いたい。
⇒メカニズムにより決まったマッチングよりも、μ(d1)=h1、μ(h1)=d1 とした方がお互い得。
d1 と h1 のような関係を逸脱ペアと呼ぶ。
・逸脱ペアが存在すると…
逸脱ペア同士で相談して、勝手にマッチをすればお互い得。せっかくメカニズムでマッチ
ングを指定したのに、最終的に雇用先はそのマッチングとはかけ離れたものとなる。
⇒医師と病院はメカニズムに参加する意味がなくなる。
４．１．DA アルゴリズム
このアルゴリズムは安定性（医師も病院も希望順位に乗っていない相手とはマッチング
していない。かつ、逸脱ペアが存在してないこと）と対戦略性（医師も病院も嘘の希望を
だす必要がないこと）の両方を満たしている。
４．２．具体的なアルゴリズム
ステップ１：各医師が自分の第一希望の病院を指名する。各病院は自分を指名した医師
の中から、希望順位表の上から順に定員以下できるだけ多くの医師を「仮
マッチ」して、その他の指名してきた医師はアンマッチとする。どの病院
も希望順位表に載せていない医師はアンマッチ確定。
ステップ２：ステップ１で仮マッチした医師は同じ病院を指名する。ステップ１でアン
マッチになっているがアンマッチ確定にはなっていない医師は、次に希望
する病院（第二希望）を指名する。各病院は自分を指名した医師の中から、
希望順位表の上から順に定員以下できるだけ多くの医師を仮マッチして、
その他の指名してきた医師はアンマッチとする。ただし、第二希望のない
医師、つまり希望順位表に第一希望しか書いておらず、ステップ１で希望
病院を指名し尽くしてもアンマッチであった医師はアンマッチ確定。
・・・・・
ステップｋ：前ステップ k−1 で仮マッチした医師は同じ病院を指名する。前ステップで
アンマッチになっているがアンマッチ確定にはなっていない医師は、前ス
テップで指名した病院の次の希望病院（今まで j 回仮マッチしていたら第
k−j 希望 ）を指名する。各病院は自分を指名した医師の中から、希望順位
表の上から順に定員以下できるだけ多くの医師を仮マッチして、その他の
指名してきた医師はアンマッチとする。ただし、前ステップで希望病院を
指名し尽くしてもアンマッチであった医師はアンマッチ確定。
‥‥‥
仮マッチしていない医師が全員アンマッチ確定となった時点で、仮マッチ
を正式マッチとし、アルゴリズムを終了する。
⇒ところが DA アルゴリズムを活用すると、研修医が以前より自由に研修先を選べるよう
になったので、研修プログラムや生活環境の良い大都市の病院に応募が集中。結果地方の
大学病院は研修医を集められなくなった。
５．JRMP アルゴリズム
このアルゴリズムは、Deferred Acceptance アルゴリズムの、地域によって医師が偏る
という問題を解決すべく、それを解消するアルゴリズムである。ある地域の病院にマッチ
したい医師がどんなに多くいても、地域定員があれば一定数の医師があぶれ、これらの医
師が他の地域にマッチされるという考えのもとに作られた。しかし、このアルゴリズムに
は安定性がないというデメリットがある。JRMP アルゴリズムでは、地域定員という新し
い概念が導入され、地域定員とは厚生労働省により各都道府県に設定された、都道府県内
の病院にマッチできる研修医の総数の上限のことである。
JRMP アルゴリズムは DA メカニズムを以下のように変更する。
まず地域内の定員の総和が地域定員を超過する都道府県では各病院の定員を（和が地域
定員と一致するようにできるだけ）比例的に減らした数（これを目標定員とする）を計算
し、この目標定員をあたかも本当の定員（これを設置定員とする）であるかのように仮想
的にみなし、DA アルゴリズムを用いてマッチングを生成する。
６．繰り返し DA アルゴリズム
繰り返し DA アルゴリズムでは、耐戦略性がないというデメリットがある。
アルゴリズムとしては、提出された希望順位表をもとに、 目標定員をあたかも設置定員
であるかのようにみなして Deferred Acceptance アルゴリズムを実行してマッチングを生
成する。もしこのマッチングで目標定員を下回る医師しかマッチしなかった病院が存在し
なければアルゴリズムは終了、さもなければ次の「ラウンド」に進む。
次のラウンドでは、前ラウンドで生成されたマッチングで目標定員を下回る医師しかマ
ッチしなかった病院の空いている席数を同地域の残りの病院に予め決められたルールに従
い分配し、これを新しい目標定員とする。そして、この新しい目標定員のもとで Deferred Acceptance アルゴリズムを実行し、以前と同じようにさらに次のラウンドに進むかどうか
を決定する。席の移動がなくなった時点でアルゴリズムを終了し、そのときに生成されて
いるマッチングでのマッチを正式マッチとする。JRMP メカニズムは繰り返し Deferred Acceptance アルゴリズムの第１ラウンドのみを使う単純なメカニズムである。
７．Flexible Deferred Acceptance アルゴリズム
Flexible Deferred Acceptance アルゴリズムは安定性、耐戦略性があり、地域の偏りも抑
えることができるアルゴリズムである。
アルゴリズムは deferred acceptance アルゴリズムのようにいくつかのステップで成り立
っている。一般にステップ k は以下のように記述できる。
ステップ k：前ステップ k−1 で仮マッチした医師は同じ病院を指名する。前ステップで
アンマッチになっているがアンマッチ確定にはなっていない医師は前ステップで指名した
病院の次の希望病院（今まで j 回仮マッチしていたら第 k−j 希望の病院）を指名する。ただ
し、前ステップで希望病院を指名し尽くしてもアンマッチであった医師はアンマッチ確定
とする。また、各病院は指名してきた医師の中で希望順位表に載っていない医師をアンマ
ッチとする。各地域はその地域内の病院を指名した医師数の中でアンマッチとされていな
い医師の数を病院ごとに数え上げ、各病院が数え上げられた医師数以下を配分されるよう
な医師数の配分の中でもっとも希望する配分を選択する。各病院は指名してきた医師を地
域に配分された数まで仮マッチして、他の指名してきた医師はアンマッチとする。仮マッ
チしていない医師が全員アンマッチ確定となった時点で、仮マッチを正式マッチとしてア
ルゴリズムを終了する。
８．それぞれのアルゴリズムの比較
同じ問題設定に対して、実際にそれぞれのアルゴリズムでマッチングを行い、結果の比
較を行う。
８．１．問題設定
A 地区には３つの病院 N 村病院 Y 下病院 K 林病院があり、B 地区には M 永病院があり、
B 地区は A 地区に比べるとあまり栄えていない地域。それぞれの病院の定員は 5 人とする。
また、医師は A 君～J 君まで 10 人いるとする。病院の希望表は A~J 君まで全員が順番に
はいっており、医師の希望表下図のようである。
N 村病院
A
B
C
D
E
F
G
H
I
J
Y下病院
4
2
2
1
2
1
3
1
1
3
K林病院
3
1
1
2
1
3
1
3
4
1
M 永病院
1
3
4
4
3
4
4
2
2
4
2
4
3
3
2
2
2
4
3
2
８．２．DA アルゴリズム
STEP1
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→仮マッチ、H→仮マッチ、I→仮マッチ、J→仮マッチ
STEP2
全ての医師が仮マッチになったためアルゴリズム終了。結果としては
N 村病院｛D,H,I,F｝
Y 下病院｛B,C,E,J,G｝
K 林病院｛A｝
M 永病院｛｝
という結果になった。確かに B 地区の M 永病院には誰もマッチングしていないので、地
区の偏りを許してしまうアルゴリズムであることがわかる。
８．３．JRMP アルゴリズム
STEP1
JRMP アルゴリズムでは予め地域の定員を決めてから DA アルゴリズムを開始する。地
域定員は病院の数を考慮して、A 地区が 8 人、B 地区が 2 人とする。また、A 地区では
３つの病院があるので最終的には N 村病院 3 人、Y 下病院 3 人、K 林病院 2 人、M 永
病院 2 人とすると
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→アンマッチ、H→仮マッチ、I→アンマッチ、J→アンマッチ
STEP2
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→仮マッチ、H→仮マッチ、I→仮マッチ、J→仮マッチ
他に候補のないアンマッチと仮マッチのみになったため、アルゴリズム終了。
結果としては
N 村病院｛D,F,H｝
Y 下病院｛B,C,E｝
K 林病院｛A,I｝
M 永病院｛G,J｝
という結果になった。一見成功したようにみえるが、I と N 村病院は逸脱ペアであり、
かつ病院と地域の定員に余裕があるため、安定性のないアルゴリズムであるといえる。
８．４．繰り返し D A アルゴリズム
STEP1
繰り返し D A アルゴリズムは JRMP アルゴリズムを繰り返し行うものである。なので、
まずは JRMP アルゴリズムを行う。結果は同じように
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→アンマッチ、H→仮マッチ、I→アンマッチ、J→アンマッチ
STEP2
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→仮マッチ、H→仮マッチ、I→仮マッチ、J→仮マッチ
STEP3
JRMP アルゴリズムではここでアルゴリズムが終了であったが、繰り返し D A アルゴリ
ズムではここから病院の目標定員の調整が行われる。今回の場合では全てが仮マッチの
ため、調整は行われないが、もし、I が私は N 村病院以外には行きたくないと嘘をついた
場合には結果は
N 村病院｛D,F,H,I｝
Y 下病院｛B,C,E｝
K 林病院｛A｝
M 永病院｛G,J｝
というように変動してしまい、I にとって嘘の希望表を提出する意味がでてきてしまうの
である。つまり、繰り返し D A アルゴリズムには耐戦略性がないとわかる。
８．５．FDA アルゴリズム
STEP1
病院は自分のところに志望してきて仮マッチできる状況の医師の数を地域に伝える。
N 村病院｛4 人の志望者｝
Y 下病院｛5 人の志望者｝
K 林病院｛1 人の志望者｝
M 永病院｛0 人の志望者｝
A 地区は、8 人の定員を与えられているため、この結果をみて病院ごとの仮マッチの定員
を定める N 村→3 人、Y 下→4 人、K 林→1 人。B 地区は１つの病院しかもっていないた
め M 永→2 人。
それをみて病院は上から順番に仮マッチしていく。すると結果は
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→仮マッチ、H→仮マッチ、I→アンマッチ、J→アンマッチ
STEP2
仮マッチを受けた医師はそのまま同じ希望を提出し、アンマッチを受けた医師は次の希
望の病院を指定する。その結果
N 村病院｛3 人の志望者｝
Y 下病院｛4 人の志望者｝
K 林病院｛2 人の志望者｝
M 永病院｛1 人の志望者｝
A 地区は、8 人の定員を与えられているため、この結果をみて病院ごとの仮マッチの定員
を定める N 村→3 人、Y 下→3 人、K 林→2 人。B 地区は１つの病院しかもっていないた
め M 永→2 人。それをみて病院は上から順番に仮マッチしていく。すると結果は
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→アンマッチ、H→仮マッチ、I→仮マッチ、J→仮マッチ。
STEP3
仮マッチを受けた医師はそのまま同じ希望を提出し、アンマッチを受けた医師は次の希
望の病院を指定する。その結果
N 村病院｛3 人の志望者｝
Y 下病院｛3 人の志望者｝
K 林病院｛2 人の志望者｝
M 永病院｛2 人の志望者｝
A 地区は、8 人の定員を与えられているため、この結果をみて病院ごとの仮マッチの定員
を定める N 村→3 人、Y 下→3 人、K 林→2 人。B 地区は１つの病院しかもっていないた
め M 永→2 人。それをみて病院は上から順番に仮マッチしていく。すると結果は
A→仮マッチ、B→仮マッチ、C→仮マッチ、D→仮マッチ、E→仮マッチ、F→仮マッチ、
G→アンマッチ、H→仮マッチ、I→仮マッチ、J→仮マッチ。
最終的な結果は
N 村病院｛D,F,H｝
Y 下病院｛B,C,E,｝
K 林病院｛A,I｝
M 永病院｛G,J｝
とマッチングされる。FDA アルゴリズムでは嘘の希望表をだして、N 村病院にしかいき
たくないということにしても、もし、N 村病院に行けない場合、自分がアンマッチ確定に
なってしまい、どこにも研修しにいくことができないというデメリットしかなくなってし
まうため、嘘の希望表をだす意味がない。つまり、耐戦略性を持っている。
また、FDA アルゴリズムでは地域定員を固定しながらマッチングを行っているため、逸
脱ペアが存在していたとしても、地域の定員を守りつつ逸脱ペアを解消することが不可能
ということである。これはつまり、地域定員の問題と、安定性の問題を同時に解消できて
いるということである。
９．まとめ
４つのアルゴリズムの特徴のまとめとしては
地域定員
安定性
耐戦略性
DA
×
○
○
JRMP
○
×
○
繰り返し DA
○
○
×
FDA
○
○
○
このようになる。様々なマッチングのアルゴリズムが考えられるが、以上の理由により、
我々の考えでは FDA アルゴリズムを利用するのが最も有効であると結論付ける。