1

次のようなブール属性で装飾された数千のノードのツリーがあります(括弧内の属性):

Root (x=true, y=true, z=false)
   Interior 1
       Leaf 1 (x=false, z=false)
       Leaf 2 (x=false, y=false, z=false)
   Interior 2
       Leaf 3
   etc.

私がやりたいことは、次の制約/情報を考慮して、属性の値を保持するために必要な装飾の最小数を見つけることです:

  1. 属性は子ノードに継承されます
  2. リーフ ノードの結果の属性のみが重要です (継承された属性を含む)。したがって、内部ノードに「デフォルト」アトリビュートを設定して、その子ノードに一連のアトリビュートをドロップできるのであれば、それで問題ありません。
  3. 私たちのモデルには、すべての属性を true または false に設定する省略形があります。たとえば、(x=false,y=false,z=false)1 つのデコレータで表すことができますが、(x=false,y=false,z=true)3 つ必要です。
  4. 子ノードの数が内部ノードの数を大幅に上回ります (少なくとも 25 対 1)。
  5. ツリーの初期状態には多くの冗長性があります。
  6. 私は Java を使用しており、これに対処するために外部ライブラリを追加することは大したことではありません。

私は大規模エンタープライズ システムとの統合レイヤーで作業しているため、これらの制約は柔軟ではありません。そのため、私にできることは、保存して転送する必要がある属性値の数を最小限に抑えることだけです。

制約 3 がループに陥っていると思います。それがなければ、各属性を個別に処理するだけで済みます。これは単純です (さらに属性が追加されることに気付く前に、その解決策を既に実装していました)。

これが一般的な問題の全体像を示すのに十分な説明であることを願っています. 必要に応じて、さらに例や情報を提供できます。ありがとうございました！

4

1 に答える 1

1

(3.) は主に無視できると思います。これは、リーフに対してのみ関心があるためです。これが私が提案するものです：

  1. すべてのブール値を一方向に持つすべての葉については、ショートカット (3.) を使用します。

  2. 次に、内部ノードごとに、1 で処理されない下の葉の過半数値に属性を割り当て、冗長な割り当てを削除します。

  3. 上位の内部ノードについても、ルートまでの直接の子を見て、同じことを行います。

これはヒューリスティックで、試したことはありませんが、もし私があなただったら、最初に試してみます。それがどうなるか教えてください。

于 2013-04-30T00:38:20.300 に答える