集合被覆問題

OR事典

集合被覆問題

読み方：しゅうごうひふくもんだい
【英】：set covering problem

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

「OR事典」の他の用語

組合せ最適化：	組合せ的爆発  計算の複雑さ  貪欲アルゴリズム  連結度  集合被覆問題  離散最適化問題  非線形計画
企画・開発・プロジェクト・品質・ヒューマン：	親和図法  資源制約  連関図法  運搬経路問題  開発リスク  集合被覆問題  顧客満足

ウィキペディア

集合被覆問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/21 00:19 UTC 版)

集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。