最適化勉強会　～最大マッチング問題とその応用 後編～

こんにちは。NRIデジタルの泉です。
NRIデジタルでは、社内で最適化問題を業務で扱っているメンバーを中心に、知識向上のために「最適化勉強会」が開催されています。本記事では社内の最適化勉強会にて発表した「最大マッチング問題とその応用」についての後編の記事になります。

前編をまだ読まれていない方はぜひそちらも見ていただければと思います。

問題③：二部グラフにおける最大１対２マッチング問題

個別指導塾に関する問題を考えます。この時、1対1での指導と1対2の指導では教える価格が異なるため、1対2で指導を希望している生徒に対して先生とのペアの最大化を考えます。つまり、「1対2で教えるペア」の最大化であり、1対1のペアに価値がない状態であるとします。担当教科と教えてもらいたい教科や都合の良い時間が一致している場合に、先生と生徒間に辺が結ばれているとして、下図のような問題を考えます。

この問題についても、変換することで最大マッチング問題に帰着することができます。

先生をそれぞれ2つに分割して、元の先生と同じ辺を結び、さらに、分割した元々同一の先生を3つの辺を用いて下図のように結びます。

この時、初期のマッチングを下図の赤い辺のように設定するものとします。¹⁾The maximum 1-2 matching problem and two kinds of its variants

この状態で増加道を探すと下図(中央)のような増加道を見つけることができます。マッチングの辺をマッチングでない辺に、マッチングでない辺をマッチングの辺に置き換えると下図(右)の状態に更新することができます。

さらに増加道を探して更新していくと下図(左)のような最大マッチングを見つけることができます。分割した頂点を元に戻して、辺を統合する際にマッチングの辺があればマッチングとします。これで得られた下図(右)が最大１対２マッチングとなります。

問題④：二部グラフにおける最大異種１対２マッチング問題

下図の社交ダンス教室の個人レッスンを考えます。先生1人に対して男性1人と女性1人を選ぶペアの最大化が最大異種１対２マッチング問題です。

この問題に関しても、変換することで最大マッチング問題に帰着することができます。

各先生を２つに分割し、一方は元々男性生徒と結んでいた辺を結び、もう一方は元々女性生徒と結んでいた辺を結びます。この時、初期のマッチングを下図の赤い辺のように設定するものとします。

この状態で、増加道を探して更新していくと下図(左)のような最大マッチングを見つけることができます。分割した頂点を元に戻して、辺を統合する際にマッチングの辺があればマッチングとします。これで得られた下図(右)が最大異種１対２マッチングとなります。

問題⑤：二部グラフにおける最大同種１対２マッチング問題

個別指導塾に関する問題を考えます。この時、1対1での指導と1対2の指導では教える価格が異なるため、1対2で指導を希望している生徒に対して先生とのペアの最大化を考えます。つまり、「1対2で教えるペア」の最大化であり、1対1のペアに価値がない状態であるとします。今回はさらに同時に教えるときは理系同士もしくは文系同士の生徒にして効率よく教えることを考えます。

実は、最大同種１対２マッチング問題については最大マッチング問題に変換することができません。増加道を拡張した増加部分グラフを探索することで最大同種１対２マッチングを求めることができると知られています。

おわりに

今回は社内の最適化勉強会にて発表した「最大マッチング問題とその応用」について紹介させていただきました。この記事を読んで、最適化問題の魅力を少しでも伝えることができたら幸いです。