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