LoginSignup
8

More than 3 years have passed since last update.

組合せ最適化 - 典型問題 - 集合分割問題

Last updated at Posted at 2015-07-10

典型問題と実行方法

集合分割問題

集合$M=\{1,\dots,m\}$の$n$個の部分集合$S_j(\subseteq M), j \in N=\{1,\dots,n\}$に対してコスト$c_j$が与えられているとする。コストの総和が最小となる$M$の分割$X(\subseteq N)$を求めよ。分割は、部分集合の中に同じ要素があってはいけない。

実行方法

usage
Signature: set_partition(n, cand)
Docstring:
集合分割問題
入力
    n: 要素数
    cand: (重み, 部分集合)の候補リスト
出力
    選択された候補リストの番号リスト
python
# CSVデータ
import pandas as pd
from ortoolpy import set_partition
ss = pd.read_csv('data/subset.csv')
g = ss.groupby('id')
set_partition(len(g), [(r.weight.iloc[0], r.element.tolist()) for _, r in g])
結果
[2, 3]

set.gif

python
# pandas.DataFrame
from ortoolpy.optimization import SetPartition
SetPartition('data/subset.csv')
id weight element
4 2 1.0 a
5 2 NaN d
6 3 3.0 b
7 3 NaN c
python
# サンプルデータ
from ortoolpy import set_partition
set_partition(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])
結果
[2, 3]

データ

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
8