「集合カバー問題」の版間の差分
ナビゲーションに移動
検索に移動
細 ("集合カバー問題" を保護しました。 [edit=sysop:move=sysop]) |
Sakasegawa (トーク | 投稿記録) |
||
| 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年9月3日 (月) 17:19時点における版
【しゅうごうかばーもんだい (set covering problem)】
集合の部分集合に対してコストが与えられている. このとき和集合がとなるようなの組合せの中で対応するコストの総和が最小となるものを求める問題を集合被覆問題,あるいは集合カバー問題という. さらに, 選ばれた が互いに重ならないという制約を加える場合を集合分割問題と呼ぶ. 携帯電話の受送信センターの配置問題など応用例は豊富である.
