java - 减少属性树

Question

我有一个包含数千个节点的树，由 boolean 属性装饰，如下所示(属性在括号中):

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) 可以由一个装饰器表示，而 (x=false,y=false,z=true) 则需要三个装饰器。
4. 子节点的数量将大大超过内部节点的数量(至少 25 比 1)
5. 树的初始状态会有很多冗余。
6. 我正在使用 Java，添加外部库来处理这个问题并不是什么大问题。

这些约束并不灵活，因为我正在开发大型企业系统的集成层，因此我所能做的就是尽量减少我们必须存储和传输的属性值的数量。

我认为约束 #3 让我陷入了困境，因为如果没有它，我就可以单独处理每个属性，这很简单(在我意识到更多属性即将到来之前，我已经实现了一个解决方案)。

我希望这足以描述一般问题。如果需要，我可以提供更多示例或信息。谢谢!

Answer 1

我认为 (3.) 主要可以被忽略，因为我们只对叶子感兴趣。 这是我的建议:

1. 对于所有具有单向 boolean 值的每个叶子，请使用快捷方式 (3.)。

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

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

这是一种启发式方法，我还没有尝试过，但如果我是你，这将是我的第一次尝试。 让我知道进展如何。