Discussion :

[Morvan Mikael]

Bonjour,

Pour un problème de calcul sur un arbre. En effet, sur un organigramme d'entreprise je dois remonter les consommations de chaque personne, chaque personne étant dans un service et dans une filiale
Par exemple:
Entreprise
|
__________________________
Filiale1 Filiale2 Filiale3
_____________ ______ |
| | | | | |
Per1 Pers2 Per3 Pers4 Pers5 Pers5

Si les personnes ont pris chacun 3 crayons Bic, je dois remonter la somme de crayon Bic au niveau du service puis au niveau de la filiale puis au niveau de l'entreprise. Je dois donc parcourir mon arbre des feuilles vers la racine.

Pour des raisons de performances (100 000 personnes possibles) et de taille de pile limitée, je ne peux pas faire du récursif!

Merci pour votre aide,
Mikaël Morvan

[Neo82]

Je ne sais pas si c'est posible de parcourir un arbre de facon itérative....

L'algo de récursion n'étant pas terminal... enfin je ne sais pas

Qu'appelles tu taille de pile réduite? Il y a tellement de monde que ca dans l'arbre ;)?

@++

[Morvan Mikael]

Le nombre de personne peut atteindre 150 000 avec de nombreuses propriétés à remonter (une trentaine).
Le problème de la récursivité est que tout est mis sur la pile et vu le nombre d'élément, ça peut déborder et donc crack!

[chicorico]

Salut,

Il est tout à fait possible de parcourir un arbre de facon iterative.

Va faire un tour là :

http://lmi17.cnam.fr/~anceau/Documents/xtc_5.pdf

C'est un mini cours sur les arbres, il y a un fonction de parcours d'arbre iterative en page 4.

[Morvan Mikael]

Merci mais ce cours parle d'arbre binaire et j'ai des arbres n-aires
De plus, il faut que je remonte les informations et pas que je trouve mes feuilles.

Merci encore,
Mikaël Morvan

[Lrhoul]

Je pense qu'il doit y avoir un moyen en récursif, de ne pas prendre beaucoup de ressources (ni en performance, ni sur la pile)...

Si tu t'amuse avec de l'itérative, ça doit être très faisable (car, si je ne me trompe pas, il est toujours possible de passer de l'un à l'autre). Ceci dit, je ne te promet la simplicité ...

Pour par être venu poster pour rien, voila mon idée :

Tu descend ton arbre en récursif et tu le parcours les sous arbres en itératif. Sauf si ton arbre à des milliers de niveaux (ce qui n'est pas le cas dans ton sujet) ta pile ne risque rien ....

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
Fonction Traitement_de_noeud( Noeud N )
{
     Déclarer et initialiser variable_information pour stocker information;
 
     Si(N n'a pas de Sous-Noeud)
     {
          Renvoyer informations voulues;
     }
     Sinon
     {
          Pour chaque Sous-Noeud de N
         {
              variable_information = 
                          Combinaison(variable_information, 
                                              Traitement_de_noeud(sous-noeud)
                                             );
         }
         Renvoyer variable_information;
     }
}

PS : Combinaison, c'est pour réunir les multiples résultats, ça peut être une simple addition.

[yannickd]

ben en fait pour les arbres généraux il suffit d'adapter l'algorithme qui devient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Pile P
p.push(noeud_racine)
tant que (P n'est pas vide)
faire
 Noeud A = P.Pop()
 Traitement_de_A
 pour tous les noeuds de A
 faire 
      P.push(fils_de_A)
 fin pour
fin tant que

voila

[Trap D]

ben en fait pour les arbres généraux il suffit d'adapter l'algorithme qui devient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Pile P
p.push(noeud_racine)
tant que (P n'est pas vide)
faire
 Noeud A = P.Pop()
 Traitement_de_A
 pour tous les noeuds de A
 faire 
      P.push(fils_de_A)
 fin pour
fin tant que

voila

C'est toi qui gère la pile qui elle peut devenir immense !! On en revient au même point.

J'ai peut-être mal compris le problème : tu dois parcourir tout ton arbo pour faire des calculs de consommation.
Une possibilité c'est le parcours par niveau en utilisant une file d'attente qu'il enfile les noeuds fils de chaque noeud pere. A chaque noeud tu totalises dans des variables globales les données qui t'intéressent et tu passes au noeud suivant en défilant, etc.
Si on réfléchit bien, c'est exactement ce que vient de dire yannickd sauf que j'utilise une file

[Sub0]

Je pose une question hors sujet peut-être (dans ce cas veuillez m'excuser)

Pourquoi ne pas utiliser une base de données ?
Ça me semble tout à fait approprié au problème, surtout vu le nombre de personnes au final... Avec une base de données, tu n'aurais pas de problème de pile, les requêtes de recherches seraient bien plus rapides, il deviendrait possible de réaliser bien plus de choses qu'avec un autre moyen... à+

[Morvan Mikael]

Bonjour et merci pour vos réponses. Elles m'ont permis de trouver la solution.
En fait, il faut descendre jusqu'aux feuilles puis remonter des feuilles vers la racine en faisant attention à ne pas compter plusieurs fois les compteurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
Fonction descend(Noeud)
Pile P
p.push(noeud)
tant que (P n'est pas vide)
faire
 Noeud A = P.Pop()
 
  Si j'ai des fils alors
  pour tous les noeuds de A
  faire
      P.push(fils_de_A)
  fin pour 
  Sinon //Je suis une feuille
    Remonter(A)
 
Fin Tant Que
Fin Fonction
 
Fonction Remonter(Feuille)
Noeud A= Noeud.Pere
 
tant que A Existe
  TraitementCompteur(A)
  A= A.Pere
Fin tant que
 
Fin Fonction

Voila, la seule à faire regarder c'est que la fonction de traitement des compteur est appelée plusieurs fois pour le même noeud donc il faut ajouter des flags de traitement à chaque parcours.
A part ça, codé en Delphi c'est très rapide: 300 ms pour traiter un arbre de 40 000 éléments!
Merci encore pour votre aide.

Ps: pour répondre à Sub0, mon arbre est constitué d'après une base de données mais faire de la récursion sur la base de données et vraiment très coûteux au niveau perf.

[Sub0]

Ps: pour répondre à Sub0, mon arbre est constitué d'après une base de données mais faire de la récursion sur la base de données et vraiment très coûteux au niveau perf

Je ne suis pas du tout d'accord avec cette affirmation ! Les moteurs de bases de données sont justement prévus, optimisés pour pouvoir stocker et traîter des millers d"éléments... Les requêtes sont très rapides et l'avantage par rapport à ce que tu prévois d'utiliser, est que tu peux réaliser différentes recherches de toutes sortes, des statistiques avec une simple requête (tu n'es pas obligé de recoder la boucle de recherche)...
Performances ? Imagines-tu des organisations traitant des millers d'enregistrements (comme DVP par exemple) utiliser autre chose qu'une base de données ?
Et puis je n'ai pas trop compris ta recherche en réalité de dois t'avouer, puisque je vois toujours une récursivité dans ton algo avec "tant que" et "pour tous"... Mais bon, si c'est suffisant pour ton application et que tu es content de toi, c'est l'essentiel. N'oubli pas d'ajouter la tag résolu, à+

[yannickd]

subO euh je crois ke tu trompe dans la notion de recursion

Et puis je n'ai pas trop compris ta recherche en réalité de dois t'avouer, puisque je vois toujours une récursivité dans ton algo avec "tant que" et "pour tous"...

dans les cours sur la recursion il est écrit dans la première page

Une procédure récursive est une procédure qui s'appelle elle-même.

je ne vois pas en quoi un "tant que" et "pour tous" montre une recursion.
ca s'appelle des boucles. C'est vrai qu'il y a une idée de récursivité puisqu'un arbre est une structure récursive. L'algo n'est pas récursif.

[Sub0]

oui, tu as raison ! Ça m'arrive d'être à côté de la plaque...
Merci de me l'avoir fait remarquer, à+