Python
最適化

組合せ最適化 - 典型問題 - 集合被覆問題

More than 1 year has passed since last update.

典型問題と実行方法


集合被覆問題

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


実行方法


usage

Signature: set_covering(n, cand, is_partition=False)

Docstring:
集合被覆問題
入力
n: 要素数
cand: (重み, 部分集合)の候補リスト
出力
選択された候補リストの番号リスト


python

# CSVデータ

import pandas as pd
from ortoolpy import set_covering
ss = pd.read_csv('data/subset.csv')
g = ss.groupby('id')
set_covering(len(g), [(r.weight.iloc[0], r.element.tolist()) for _, r in g])


結果

[0, 1, 2]


set.gif


python

# pandas.DataFrame

from ortoolpy.optimization import SetCovering
SetCovering('data/subset.csv')




id
weight
element




0
0
1.0
a


1
0
NaN
b


2
1
1.0
a


3
1
NaN
c


4
2
1.0
a


5
2
NaN
d


python

# サンプルデータ

from ortoolpy import set_covering
set_covering(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])


結果

[0, 1, 2]



データ