|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 集 ： [しゅう] 【名詞】 1. collection ・ 集合 ： [しゅうごう] 1. (n,vs) (1) gathering 2. assembly 3. meeting 4. (2) (gen) (math) set ・ 合 ： [ごう] 【名詞】 1. go (approx. 0.18l or 0.33m) ・ 被覆 ： [ひふく] (n,vs) insulation ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。 各部分集合 Si に対し重み wi が与えられ、選択した部分集合の重みの和を最小化する問題のことを指す場合もある。このような場合、重み付き集合被覆問題 と区別して呼ぶことも多い。全ての i について wi が等しいとき、重み無し集合被覆問題と等価なので、重み無し集合被覆問題は、重み付き集合被覆問題の特殊な場合とも言える。 重み無し・重み付きを問わず、この問題はNP困難であることが知られている。そのため、集合に制約を加えた問題や近似アルゴリズムの研究がさかんである。 ==重み無し集合被覆問題== 貪欲法によって、近似度 ln|U|+1 の解を得ることができることが知られている。特に、各部分集合の要素の数が k 以内であることがわかっているとき (k-set cover problem)、調和級数 Hk (= 1+1/2+…+1/k) を用いると、近似度 Hk + 1 (≦ ln k + 1) になることが知られている。逆に、NP⊆QP が成り立たないとき、任意のε>0について、近似度 (1-ε) ln |U| の多項式時間アルゴリズムが存在しないことも示されている。 k-set cover problem については、k=2 のとき、最大マッチング問題の解法を応用することで容易に最適解が求められることが知られているが、k>2 の場合については、MAX SNP-hardであることが知られている。k>2 の場合について、Duh と Fürer は、1997年、k-set cover problem に対して、Hk - 1/2 近似アルゴリズムを与えた。 また、最も高頻度に現れる集合の要素の頻度を f とおくとき、近似度 f の近似アルゴリズムも存在することが知られている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「集合被覆問題」の詳細全文を読む スポンサード リンク
|