MInimum树覆盖

Question

我想了解怎样才是找到最小树覆盖度的最佳方法。让我解释一下。

我有一个表示树的自引用结构，它的深度有限。

树中的节点可以在逻辑上“选择”。从应用程序的角度来看，这意味着用户希望获得一些有关所选内容的聚合信息。

假设用户选择节点A、D、I、J、L和M。

我想要做的是能够重组用户选择，以便选择覆盖整个选择的最小节点集。

对于这个例子：

• 节点i和j可以由它们的公共父节点F覆盖，因此我选择F并删除I和J。
• 节点M可以被它的父节点H覆盖，所以我选择H并删除M
• 节点D已经被节点A覆盖，所以我删除了D

在此之后，没有什么可以进一步重构-算法停止，我应该得到以下选择。

首先，我不知道“最低保险”是否是个好名字。第二，我找不到更好的短语，所以谷歌不是我最好的朋友。

另外要注意的是，树本身可以存储：

• 内存中
• 在事务数据库中
• 在OLAP数据库中(不再完全自引用)

我被卡住了

编辑

我一直在想这个问题，也许有一个解决办法，我必须加以分析。

可介绍以下内容：

• 让我们称树为“模板树”
• 让我们把选择称为“选择树”
• 模板树的每个节点都有一个预先计算出来的冗余属性-子节点数。
• 选择树可以是“脏的”或“干净的”。
  • 添加节点后，如果尚未完成任何操作，则处于脏状态
  • 重组完成后，一切正常

• 选择树的每个节点都有冗余的属性-所选子节点的数目和状态:选择或鬼。
• 选择树是内存中双链接树的变体(子树知道它的父树，父树知道它的子树)。

之后，在选择树中添加一个节点(选择-节点)将像这样工作。让我们将选择树中新节点的新父节点称为选择父节点，并将模板树中新节点的父节点称为模板父节点。让我们调用选择树节点选择的子节点-子节点，以及模板树节点模板的子节点-子节点。

1. 设置选择树的脏状态
2. 删除所有选择-选择的子节点
3. 如果选择树中不存在，则获取选择节点的模板-父节点及其子属性数；将选择-父节点添加为鬼节点，选择的子节点数=1。
4. 如果在选择树中存在，则访问选择-选择的父节点并增加其所选的子节点数。
5. 如果选择父节点选择的子节点数等于模板子节点数，则将其状态从“鬼”提升到“选定”；将该选择节点视为新节点，并从1开始。
6. 设置选择树的干净状态

我很好奇这个算法是否已经作为一个实现存在于某个地方。它的行为显然不会比O(log(n))更糟糕，对吗？当然，如果它在逻辑上不缺少什么的话。

Answer 1

您想要的效果可以通过对树的一次传递，使用深度第一次迭代来实现。

访问节点时，执行两个条件操作。

• 如果选择了节点的所有子节点，则将当前节点标记为“选定”。
• 如果选择当前节点，则取消选择该节点的所有子节点。

在您的示例中，这些测试使节点I、J和M的选择分别达到F和H，而第二个测试导致取消选择节点D。

该算法不对树的存储方式做任何假设，而只是假设您可以到达每个节点，并且可以在节点X本身之前处理节点X的子节点。

如果该过程是交互式的，则该过程可以更简单：

1. 检查是否已选中所选节点的任何父节点(直接或间接)。如果是，则再次取消选择节点。
2. 如果该节点仍被选中，请遍历该节点下的树并取消选择该节点的所有子节点(直接和间接)。
3. 如果选择了节点及其所有同级节点，则选择父节点并取消选择父节点的子节点。重复此步骤，直到到达没有选择所有兄弟节点的节点为止。

这通常是更有效的，因为在每一个选择，你通常只需要走一小部分树。