本記事では、Colab を使用して二部マッチング問題を解く web アプリケーションを開発する方法を紹介します。ポイントは２つです。なお、サンプルコードを用意しているので直ぐに初められます。
二部マッチング問題が実際の利用シーンぶついては以下の記事が詳しいです。
本記事では以下の流れで説明します
- サンプルコードの機能概要を理解する
- Colabで実行する
- 実際に動かしてみる
目次
1. サンプルコードの機能概要を理解する
機能の目的
今回紹介するサンプルコードは下図のようなマッチング問題を解くことを目的としています。
赤チームと青チームに分かれ、それぞれ相手チームのメンバを重み付け（点数付け）し、重みが最大となるようなペア（下図の場合、太いグレーの線が該当）を見つけます。
入力情報と出力情報の定義
入力情報は以下の３つです
- 誰がどちらのチームに属しているかという情報
- 青チームの誰が赤チームの誰に何点をつけているかという情報
- 赤チームの誰が青チームの誰に何点をつけているかとう情報
出力情報は下記です
- 重みが最大となるペアがわかる情報
入力情報詳細
３種類の入力する情報について説明します。参考のためにファイルを添付しております。
名前と属性で定義します。属性は0もしくは1とします。
（例の場合、青チームを0、赤チームを1としています）
| 名前 | 属性 |
|---|---|
| A | 0 |
| B | 0 |
| C | 0 |
| D | 0 |
| W | 1 |
| F | 1 |
| G | 1 |
| H | 1 |
0属性、1属性、重みの順で定義します。
今回の例では、青チームの各メンバが赤チームから２名選出し、１位に３点、２位に１点を付与しています。
| ０属性 | 1属性 | 重み |
|---|---|---|
| A | E | 3 |
| A | F | 1 |
| B | G | 3 |
| B | H | 1 |
| C | E | 3 |
| C | G | 1 |
| D | H | 3 |
| D | E | 1 |
③赤チームの誰が青チームの誰に何点をつけているかとう情報
先程とは並びが異なり、1属性、0属性、重みの順で定義します。
先程と同様に、赤チームの各メンバが青チームから２名選出し、１位に３点、２位に１点を付与しています。
| 1属性 | 0属性 | 重み |
|---|---|---|
| E | A | 3 |
| E | B | 1 |
| F | A | 3 |
| F | B | 1 |
| G | A | 3 |
| G | B | 1 |
| H | C | 3 |
| H | D | 1 |
2. Colabで実行する ※サンプルコードへのリンクあり
最後のセルの出力に表示されるURLをクリックすることでwebアプリが実行できます。
実行イメージは下記のような簡単な web アプリになります。
3. 実際に動かしてみる
サンプルコードの操作シナリオ
下記の順番で操作します。
- 「①誰がどちらのチームに属しているかという情報」（csvファイル）をアップロードする
- 「②青チームの誰が赤チームの誰に何点をつけているかという情報」（csvファイル）をアップロードする
- 「③赤チームの誰が青チームの誰に何点をつけているかとう情報」（csvファイル）をアップロードする
- 「④マッチング開始ボタン」をクリックする
「①誰がどちらのチームに属しているかという情報」（csvファイル）をアップロードする
画面イメージの①の点線で囲まれているエリアをクリックします。
ファイルを選択するエクスプローラーが表示されるので、先程ダウンロードした「nodedef.csv」を選択します。
「②青チームの誰が赤チームの誰に何点をつけているかという情報」（csvファイル）をアップロードする
画面イメージの②の点線で囲まれているエリアをクリックします。
ファイルを選択するエクスプローラーが表示されるので、先程ダウンロードした「edge0to1.csv」を選択します。
「③赤チームの誰が青チームの誰に何点をつけているかとう情報」（csvファイル）をアップロードする
画面イメージの③の点線で囲まれているエリアをクリックします。
ファイルを選択するエクスプローラーが表示されるので、先程ダウンロードした「edge1to0.csv」を選択します。
「④マッチング開始ボタン」をクリックする
画面イメージの④の箇所にある「Matching!」をクリックします。
重み付き最大マッチングが計算され下図のようなグラフが表示されます。
（Aさん、Fさん）、（Bさん、Gさん）、（Dさん、Hさん）がペアとなることがわかります。
まとめ
本記事では、Colab を使用して二部マッチング問題を解く web アプリケーションを開発する方法を紹介しました。ご参考になりましたら twitter をフォローして SNS でシェアして頂ければ幸いです。
【付録】さらに理解を深めたいという方たちへ
理解を深めるためには、実際に動かしてみるが一番です。
下記テーマを参考に、色々と動かしてみてはいかがでしょうか？
- 青チーム、赤チームそれぞれ人員を追加（4人→8人）し、それぞれ重みを追加する
- ペアを可視化するだけでなくcsvでダウンロード可能にする
ご参考
ちなみに今回は下記 Chromebook を使用しました。
14.0型フルHD × Core i3 × メモリ8GB を満たす数少ない端末です。
軽くて持ち運びしやすく開発に耐えうるスペックなのでおすすめです。
 | 価格:70,510円 |
Chromebook でプログラミングを始める方法については下記記事をご参考下さい。
