【Colab】Csv をアップロードして二部マッチング問題を解く【Webアプリ開発入門】

3 min

本記事では、Colab を使用して二部マッチング問題を解く web アプリケーションを開発する方法を紹介します。ポイントは2つです。なお、サンプルコードを用意しているので直ぐに初められます。

ポイント①:JupyterDash を使用した web アプリです。

ポイント②: networkx と dash_cytoscape を使用して二部マッチング問題を解く機能を組み込んでいます

二部マッチング問題が実際の利用シーンぶついては以下の記事が詳しいです。

GitHubにソースを用意しているので Colab からすぐに実行できます

本記事では以下の流れで説明します

  • サンプルコードの機能概要を理解する
  • Colabで実行する
  • 実際に動かしてみる
広告_零号機

1. サンプルコードの機能概要を理解する

機能の目的

今回紹介するサンプルコードは下図のようなマッチング問題を解くことを目的としています。

赤チームと青チームに分かれ、それぞれ相手チームのメンバを重み付け(点数付け)し、重みが最大となるようなペア(下図の場合、太いグレーの線が該当)を見つけます。

入力情報と出力情報の定義

入力情報は以下の3つです

  1. 誰がどちらのチームに属しているかという情報
  2. 青チームの誰が赤チームの誰に何点をつけているかという情報
  3. 赤チームの誰が青チームの誰に何点をつけているかとう情報

出力情報は下記です

  • 重みが最大となるペアがわかる情報

今回は、入力をcsvファイル、出力を先述の図とします。

入力情報詳細

3種類の入力する情報について説明します。参考のためにファイルを添付しております。

①誰がどちらのチームに属しているかという情報

名前と属性で定義します。属性は0もしくは1とします。

(例の場合、青チームを0、赤チームを1としています)

名前属性
A0
B0
C0
D0
W1
F1
G1
H1
誰がどちらのチームに属しているかの情報

②青チームの誰が赤チームの誰に何点をつけているかという情報

0属性、1属性、重みの順で定義します。

今回の例では、青チームの各メンバが赤チームから2名選出し、1位に3点、2位に1点を付与しています。

0属性1属性重み
AE3
AF1
BG3
BH1
CE3
CG1
DH3
DE1

③赤チームの誰が青チームの誰に何点をつけているかとう情報

先程とは並びが異なり、1属性、0属性、重みの順で定義します。

先程と同様に、赤チームの各メンバが青チームから2名選出し、1位に3点、2位に1点を付与しています。

1属性0属性重み
EA3
EB1
FA3
FB1
GA3
GB1
HC3
HD1

2. Colabで実行する ※サンプルコードへのリンクあり

下記リンクをクリックして Colab で起動し、
ランタイムより「すべてのセルを実行する」をクリックします。

Open In Colab

最後のセルの出力に表示されるURLをクリックすることでwebアプリが実行できます。

実行イメージは下記のような簡単な web アプリになります。

実行イメージ

3. 実際に動かしてみる

サンプルコードの操作シナリオ

下記の順番で操作します。

  1. 「①誰がどちらのチームに属しているかという情報」(csvファイル)をアップロードする
  2. 「②青チームの誰が赤チームの誰に何点をつけているかという情報」(csvファイル)をアップロードする
  3. 「③赤チームの誰が青チームの誰に何点をつけているかとう情報」(csvファイル)をアップロードする
  4. 「④マッチング開始ボタン」をクリックする
画面イメージ

「①誰がどちらのチームに属しているかという情報」(csvファイル)をアップロードする

画面イメージの①の点線で囲まれているエリアをクリックします。

ファイルを選択するエクスプローラーが表示されるので、先程ダウンロードした「nodedef.csv」を選択します。

「②青チームの誰が赤チームの誰に何点をつけているかという情報」(csvファイル)をアップロードする

画面イメージの②の点線で囲まれているエリアをクリックします。

ファイルを選択するエクスプローラーが表示されるので、先程ダウンロードした「edge0to1.csv」を選択します。

「③赤チームの誰が青チームの誰に何点をつけているかとう情報」(csvファイル)をアップロードする

画面イメージの③の点線で囲まれているエリアをクリックします。

ファイルを選択するエクスプローラーが表示されるので、先程ダウンロードした「edge1to0.csv」を選択します。

「④マッチング開始ボタン」をクリックする

画面イメージの④の箇所にある「Matching!」をクリックします。

重み付き最大マッチングが計算され下図のようなグラフが表示されます。

(Aさん、Fさん)、(Bさん、Gさん)、(Dさん、Hさん)がペアとなることがわかります。

まとめ

本記事では、Colab を使用して二部マッチング問題を解く web アプリケーションを開発する方法を紹介しました。ご参考になりましたら twitter をフォローして SNS でシェアして頂ければ幸いです。

【付録】さらに理解を深めたいという方たちへ

理解を深めるためには、実際に動かしてみるが一番です。

下記テーマを参考に、色々と動かしてみてはいかがでしょうか?

  1. 青チーム、赤チームそれぞれ人員を追加(4人→8人)し、それぞれ重みを追加する
  2. ペアを可視化するだけでなくcsvでダウンロード可能にする

ご参考

ちなみに今回は下記 Chromebook を使用しました。
14.0型フルHD × Core i3 × メモリ8GB を満たす数少ない端末です。
軽くて持ち運びしやすく開発に耐えうるスペックなのでおすすめです。

富士通|FUJITSU ノートパソコン FMV Chromebook 14F(タッチパネル) ダーククロム FCB143FB [14.0型 /Chrome OS /intel Core i3 /メモリ:8GB /SSD:128GB /タッチパネル対応 /2021年12月モデル]【point_rb】

価格:70,510円
(2022/2/23 18:35時点)
感想(1件)

Chromebook でプログラミングを始める方法については下記記事をご参考下さい。

広告_零号機-エリア2
kewton

kewton

大学院卒業後、某大手SIerで10年以上SEとして従事。
社会人3年目までに基本情報・応用情報技術者、データベーススペシャリスト、簿記3級・2級を取得。
基幹系システム・IoTシステム開発のプロジェクト経験多数。AI活用システムの企画・プロト開発経験あり。
強みは、プロマネだけでなく自身で開発も実施してきたこと。
【扱える言語】
C#、java、python、javascript、Excel VBA
【扱えるDB】
oracle、sql server、postgreSQL、mongoDB

FOLLOW

関連記事

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA