LoginSignup
5

More than 5 years have passed since last update.

組合せ最適化 - 典型問題 - 安定マッチング問題

Last updated at Posted at 2015-07-10

典型問題と実行方法

安定マッチング問題

男性のグループと女性のグループが与えられ、男性は女性の選好順序を、女性は男性の選好順序を持っている。男女でペアを作ったときブロッキングペアが存在しないマッチングを安定マッチングという。
ブロッキングペア(m,w)とは、ペアとなっていない男女で「wはmの現在のペアよりも好ましい」「mはwの現在のペア よりも好ましい」状態のペアをいう。

安定マッチング問題は、厳密には最適化問題ではないが、マッチングに関し重要な問題なので典型問題に含めている。ゲイル・シャプレーの解法により効率的に解くことができる。

実行方法

usage
Signature: stable_matching(prefm, preff)
Docstring:
安定マッチング問題
入力
    prefm, preff: 選好
出力
    マッチング
python
from ortoolpy import stable_matching
print(stable_matching([[2,0,1],[2,1,0],[0,2,1]], [[0,1,2],[2,0,1],[2,1,0]]))
結果
{2: 2, 0: 0, 1: 1}
python
# pandas.DataFrame
from ortoolpy.optimization import StableMatching
StableMatching('data/stable.csv')
male female pref_male pref_female
0 0 0 1 0
4 1 1 1 2
8 2 2 1 0

データ

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5