「集合被覆問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【しゅうごうひふくもんだい (set covering problem)】''' 集合$M=\{ e_1,\: \cdots \:, \: e_m\}$の部分集合$S_j\: (j=1,\: \cdots ,\: n)$に対してコス...') |
|||
| 1行目: | 1行目: | ||
'''【しゅうごうひふくもんだい (set covering problem)】''' | '''【しゅうごうひふくもんだい (set covering problem)】''' | ||
| − | 集合 | + | 集合<math>M=\{ e_1, \cdots, e_m\}\,</math>の部分集合<math>S_j (j=1, \cdots , n)\,</math>に対してコスト<math>c_j\,</math>が与えられている. このとき和集合が<math>M\,</math>となるような<math>S_j\,</math>の組合せの中で対応するコストの総和が最小となるものを求める問題. さらに, 選ばれた <math>S_j\,</math> が互いに重ならないという制約を加える場合を集合分割問題と呼ぶ. 携帯電話の受送信センターの配置問題など応用例は豊富である. |
2007年7月12日 (木) 22:30時点における版
【しゅうごうひふくもんだい (set covering problem)】
集合の部分集合に対してコストが与えられている. このとき和集合がとなるようなの組合せの中で対応するコストの総和が最小となるものを求める問題. さらに, 選ばれた が互いに重ならないという制約を加える場合を集合分割問題と呼ぶ. 携帯電話の受送信センターの配置問題など応用例は豊富である.
