セットの簡素化

Question

は、私が二組、set1 = {a,b,c,d,e,f}とset2 = {a,b,c,d,e,g}を持っていると言います。むしろ明示的にこれらを表現するよりも、私たちは{a,b,c,h}を表現したい場合は、我々はcommon - d - e + hとしてそれを表すことができ

common = {a,b,c,d,e} 
set1 = common + f 
set2 = common + g 

のようなものを作りたいです。

私の目標は、使用する最適な共通部分を生成できるように基本的です。一般的なセクションは1つしかありませんが、これは難しいことではありませんが、複数を許可する必要があります（無制限ではありません。最適によって

、Iは「発現エレメントの最小数」を意味します。したがって、上記の例では、common変数を作成するためには5（要素数）のコストがかかります。次に、1と2の両方をコスト2（1つは共通参照、もう1つは余分な要素を追加）に設定し、合計7になります。同様に、参照先の要素を減算の「コスト」1

別の例として、 {a,b,c,d}, {a,c,d,e}, {e,f,g,h} and {e,f}

は、これは多くの挑戦となる複数の共通部分を可能にすることにより

common1 = {a,c,d} 
common2 = {e,f,g} 
set1 = common1 + b 
set2 = common1 + e 
set3 = common2 + h 
set4 = common2 - g 

とすることができるであろう。このタイプの問題の名前、またはそれに類するものがありますか？それは圧縮に関連する可能性があるようだが、私はこれでどこから始めるにはあまりにも多くのリソースを見つけることができませんでした。

releventことができるいくつかの他の詳細：

• が有効であることができる一組を表現するために複数の共通部分を参照するために許可されるが、必須ではありません。私のユースケースについて
• 、セットは、典型的には約20の要素と約10の異なるセットであろう。

Answer 1

あなたはそれが離れて見えませんすべてのセットで、すべての原子の集合を見つけることができます。

{a,b,c,d,e,f,g,h}  | {a,b,c,d} = {a,b,c,d},{e,f,g,h} 
{a,b,c,d},{e,f,g,h}  | {a,c,d,e} = {a,b,c,d},{e,f,g,h} 
{a,c,d},{b},{e},{f,g,h} | {e,f,g,h} = {a,c,d},{b},{e},{f,g,h} 
{a,c,d},{b},{e},{f,g,h} | {e,f}  = {a,c,d},{b},{e},{f},{g,h} 

{a,b,c,d} = {a,c,d},{b} 
{a,c,d,e} = {a,c,d},{e} 
{e,f,g,h} = {e},{f},{g,h} 
{e,f}  = {e},{f} 

これは少し近いですが、最小限の内訳を解決しません。

私はそれがNP困難であると思われるので、あなたが最小限を見つけることができると思ういけません。集合Sを考えて、Sの各サブセットがノードGであるグラフを作成します。次に、サブセットの長さに応じてノード重みを与え、変化量に対応する各ノード間にエッジを描画します。 {bcd} - > {abe}の重みは4です。共通集合問題の最小限の解を見つけるには、最小重みスパニングツリーが必要ですあなたが興味を持っているセットのそれぞれを見つけてください。あなたがこれを使って最小限の共通セットを構築することができれば、これらは同等です。ノード加重グラフ内の最小加重木を求めることは、ノード加重シュタイナーツリー問題と呼ばれる。ノード重み付きスタイナーツリー問題は、スタイナーツリー問題と同等に表示できます。スタイナーツリーの問題は、NP-Hardであることが示されている可能性があります。だからあなたが解決しようとしている問題はNP-Hardだと強く疑う。

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node15.html

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node17.html