set covering problemとは何？わかりやすく解説 Weblio辞書

すべての辞書から再検索する

OR事典

索引トップ用語の索引ランキングカテゴリー

集合カバー問題

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

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

「OR事典」の他の用語

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