4

アルゴリズムの問​​題があります。解決方法がわかりません。多分誰かが私を助けることができますか？

オブジェクトがあります。各オブジェクトには同じ機能があります。次の表に示すことができます。

                 Feature1    Feature2    Feature3   Feature4
      Object1       1           0           1          1

      Object2       0           0           0          1

      Object3       0           1           1          1

      Object4       0           1           0          0

ここで、オブジェクトの最小サブセットをすべて見つけたいと考えています。各サブセットは、各特徴に対して少なくとも 1 つの値「1」を持つ必要があります。上の表の結果は、{Object1, Object3} と {Object1, Object4} の 2 つのサブセットです。時間がかかりすぎる可能性があるため、考えられるすべてのサブセットを生成することはできません。

4

2 に答える 2

8

これはまさに集合被覆問題です。問題はNP困難であるため、正確な最小値が必要な場合、すべての可能なサブセットを生成することは、時間内に他のソリューションよりもそれほど悪くはありません。

しかし、いくつかの多項式時間近似アルゴリズムがあります。詳細については、ウィキペディアのページを参照してください。「最良」は、次のように実行される欲張りアルゴリズムです。

  1. 実装されていない機能を{Feature1、Feature2、Feature3、...}として初期化します
  2. 実装されていない機能のほとんどを実装するオブジェクトを選択します。
  3. すべての機能が実装されるまで2を繰り返します。
于 2010-09-21T18:01:31.057 に答える
4

特定の機能（または複数の機能）の唯一の所有者であるすべてのオブジェクトを必然的に含めることにより、問題を減らすことができます。 Object1持っているのは1つだけFeature1なので、ソリューションにその1つが必要であることがわかります。

于 2010-09-21T18:01:37.943 に答える