7

a は複数の「カテゴリ」、b を持つオブジェクトです。たとえば、a1 には 3 つのカテゴリ b1、b2、b3 があります。問題は、カテゴリの数 (かなり大きくなる可能性があります) を、常に一緒に発生するグループに減らすことです。「最大共通サブセット」のこと。

たとえば、次のデータセットがあるとします。

a1{ b1,b2,b3 } 
a2{ b2,b3 }
a3{ b1,b4 }

b2 と b3 は常に一緒になることがわかります。

b23 = {b2,b3}

..そして、カテゴリ セットを次のように減らすことができます。

a1{ b1, b23 }
a2{ b23 }
a3{ b1,b4 }

したがって、私の問題は、この問題を解決するためのアルゴリズムを見つけることです。

Longest Common Sequence問題を調べ始めましたが、解決策になるかもしれません。b' = LCS(set_of_As)つまり、すべてのカテゴリがトラバースされるまで、このようなカテゴリを繰り返しグループ化するようなものです。ただし、これは完全ではありません。これを可能にするには、何らかの方法で入力ドメインを制限する必要があります。

明らかな何かを見逃していますか？あなたが私に指摘できる問題のドメインのヒントはありますか? そのような問題に対する他のアプローチを誰もが認識していますか。

4

2 に答える 2

7

a を含む b のセットを持つようにセットを変換します。

b1 { a1, a3 }
b2 { a1, a2 }
b3 { a1, a2 }
b4 { a3 }

新しい b セットの内容がソートされていることを確認します。

b セットを内容別に並べ替えます。

同じ要素を持つ任意の 2 つの隣接するセットは、同じ a セットで発生する b です。

于 2012-10-23T18:46:18.683 に答える
0

カテゴリに順序付けを課すことができれば、LCS で正しい方向に進んでいると思います (そうでない場合、LCS アルゴリズムは {b3, b4} と {b4, b3} を認識できません)。それらを課し、並べ替えて並べ替えることができれば、次のようなことがうまくいくと思います。


As = {a1={b1, b2},a2={b3},...}
while ((newgroup = LCS(As)) != empty) {
  for (a in As) {
     replace newgroup in a
  }
}
于 2012-10-23T18:46:22.647 に答える