Pourcentages et arbres

Question

J'ai un arbre non-ordonné. Chaque nœud représente une tâche qui peut être effectuée (1), non effectuée (0) ou qui a des tâches enfants.

Par exemple:

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

Supposons que les feuilles 1.2.1, 3.1 et 5 sont fait

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

Je veux calculer le pourcentage de l'intégralité de chaque nœud. Les feuilles sont facilement calculées avec 0% ou 100%, mais comment calculer tous les autres?

À l'heure actuelle, je marche l'arbre à partir des feuilles et chaque nœud est calculé sur la base du pourcentage d'exhaustivité des enfants. Par exemple:

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

Maintenant, plus d'enfants sont ajoutés à 1,2 (qui est plus une feuille, mais devient un nœud). Si les enfants ne sont pas "faits", 1.2 est toujours 0% et donc 1 est 50%, mais j'aimerais que 1 soit moins puis 50%, comme, descendant dans ses enfants et petits-enfants le nombre de tâches à être complété afin qu'il soit fait à 100% est plus grand!

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% 

Quelle est la meilleure façon de le calculer? Merci

Answer 1

Vous pouvez définir le% fait en totale (sous) nœuds fait divisé par le total des nœuds (sous). Compter seulement les feuilles.

Dans ce cas:

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

Ajout des nœuds supplémentaires:

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

Si cela ne suffit pas, vous pouvez ajouter un poids à chaque tâche et de calculer le poids complété divisé par le total poids.

Answer 2

vous pouvez essayer avec un post order visit (pseudo-code):

postorder(node) { 

    foreach(child : children) { 
     postorder(child) 
     node.visited++ 

     if (child.completed == 1) { 
      node.completed++   
     } 
    } 

    print("%d%%", (node.completed/node.visited) * 100) 
} 

Answer 3

Pour tout noeud, % DONE = Nombre de descendants laisse # done/total des descendants quitte

Où:

nombre de descendants laisse = somme (# enfants de feuilles descendant

Answer 4

Cela dépend du poids que vous voulez donner à chaque niveau. Si j'étais vous, je choisirais la première méthode que vous avez mentionnée (ie mettre le même poids sur des objets du même niveau) donc 1 avec 50% me semblerait juste et la différence d'avoir plus de nœuds serait vue par une augmentation plus lente de 'fait' pourcentage pour 1.2 noeud.

Pour obtenir un nœud à affecter les ancêtres plus lointains, vous pouvez calculer le pourcentage des ancêtres en moyenne de tous les leafs dans son sous-arbre (qui donnera l'achèvement de 33% pour la tâche 1), mais cela ne semble pas tout à fait juste pour moi.Tout dépend de la façon dont vous voulez vraiment représenter les données - je ne pense pas qu'il y ait une «bonne» façon de le faire.

Answer 5

Je pense que le pourcentage de chaque nœud est la valeur moyenne de ses pourcentages d'enfants (pas de sous-enfants).

Par exemple

1_per = (1.1_per + 1.2_per)/2 
3_per = (3.1_per + 3.2_per + 3.3_per)/3