math - 百分比和树

Question

我有一棵无序树。每个节点代表一个可以完成(1)、不能完成(0)或有子任务的任务。

例如:

1
-1.1
-1.2
--1.2.1
--1.2.2
-1.3
2
3
-3.1
4
-4.1
--4.1.1
5

假设叶子 1.2.1、3.1 和 5 完成

1
-1.1
-1.2
--1.2.1*
--1.2.2
-1.3
2
3
-3.1*
4
-4.1
--4.1.1
5*

我想计算每个节点的完成百分比。叶子很容易用 0% 或 100% 计算，但如何计算所有其他值？

目前，我从树叶开始遍历树，每个节点都是根据子节点的完整百分比计算的。例如:

1      50%
-1.1*  100%
-1.2   0%
2      0%
3      33%
-3.1*  100%
-3.2   0%
-3.3   0%

现在，更多的 child 被添加到 1.2(不再是叶子而是成为节点)。如果 child “未完成”，1.2 始终为 0%，因此 1 为 50%，但我希望 1 小于 50%，因为，下降到他的子孙中要完成 100% 完成的任务数量更多!

1       50%
-1.1*   100%
-1.2    0%
--1.2.1 0%
--1.2.2 0%
2       0%
3       33%
-3.1*   100%
-3.2    0%
-3.3    0%

最好的计算方法是什么？谢谢

Answer 1

您可以将完成百分比定义为完成的总(子)节点数除以总(子)节点数。只数叶子。

在这种情况下:

       1  (1/2 = 50%)
      / \
   1.1*  1.2

添加额外的节点:

       1  (1/3 = 33%)
      / \
   1.1*  1.2 (0/2 = 0%)
         / \
    1.2.1   1.2.2

如果这还不够，您可以为每个任务添加一个权重，并计算完成的权重除以总权重。