集合被覆問題

提供:ORWiki
移動: 案内, 検索

【しゅうごうひふくもんだい (set covering problem)】

集合M=\{ e_1, \cdots,  e_m\}\,の部分集合S_j (j=1, \cdots , n)\,に対してコストc_j\,が与えられている. このとき和集合がM\,となるようなS_j\,の組合せの中で対応するコストの総和が最小となるものを求める問題. さらに, 選ばれた S_j\, が互いに重ならないという制約を加える場合を集合分割問題と呼ぶ. 携帯電話の受送信センターの配置問題など応用例は豊富である.

個人用ツール