1

I have a tree of several thousand nodes, decorated by boolean attributes, something like this (attributes in parentheses):

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.

What I would like to do is find the smallest number of decorations necessary to preserve the values of the attributes, given the following constraints/info:

  1. Attributes are inherited by child nodes
  2. Only the resulting attributes of the leaf nodes are important (including inherited attributes). So if setting a "default" attribute on an interior node lets me drop a bunch of attributes on its children, that's okay.
  3. There is a shorthand in our model for setting all attributes to either true or false. For example, (x=false,y=false,z=false) can be represented by one decorator, whereas (x=false,y=false,z=true) would take three.
  4. The number of child nodes will greatly outnumber the interior nodes (at least 25 to 1)
  5. The initial state of the tree will have many redundancies.
  6. I'm using Java and adding an external lib to deal with this isn't a big deal.

These constraints are not flexible as I'm working on an integration layer with a Large Enterprise System, so all I can do is try to minimize the number of attribute values we have to store and transit.

I think constraint #3 is throwing me for a loop, because without it I could just deal with each attribute individually, which is simple (and I already implemented a solution to that before I realized more attributes were coming).

I hope this is descriptive enough to give a picture of the general problem. I can give more examples or information if required. Thank you!

4

1 回答 1

1

我认为（3.）主要可以忽略，因为我们只对叶子感兴趣。这是我的建议：

  1. 对于具有所有布尔值的每一片叶子，请使用快捷方式 (3.)。

  2. 然后对于每个内部节点，将属性分配给下面的叶子的多数值，而不是由 1 处理，并删除现在的冗余分配。

  3. 对于更高的内部节点，执行相同的操作，查看直接子节点，直至根节点。

这是一种启发式方法，我还没有尝试过，但如果我是你，这将是我的第一枪。让我知道事情的后续。

于 2013-04-30T00:38:20.300 回答