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