Discussion :

[Chablis]

Bonjour tout le monde,
J'essais de créer une liste des chemins possible à partir d'un arbre.

J'ai trois objets : Séquence, Opération, Choix
J'ai formé un arbre à partir de ces objets. Les feuilles sont des Opérations et Séquence et Choix sont des noeux qui peuvent contenir plusieurs branches.

En entrée j'ai un arbre qui contient différents chemins, un chemin est appelé un processus. J'aimerai à partir de cet arbre obtenir tous les processus possibles sous forme d'une liste de liste.

J'ai fait un schémas pour l'illustrer (en pièce jointe).

Je voudrais faire une fonction qui passe de l'arbre à la liste de tous les processus possibles. J'ai commencé à réfléchir sur un algorithme récursif mais je ne m'en sors pas. Auriez vous déjà rencontré ce type de problème ? Si oui pourriez vous m'aider ?

En attendant, j'ai écris un prgm qui me permet d'obtenir la liste [chauffage, [[laminage,roulage],ecrasage]] mais ce n'est pas une liste de processus.

[Flodelarab]

Bonjour

L'algorithme récursif est une bonne idée.

Tu crées une fonction définie comme suit :
A chaque branche, tu fais la liste des branches filles.
Pour chacune des filles, tu appelles la fonction en transmettant les ancêtres.
Quand une branche n'a plus de fille, afficher la liste des ancêtres et le nom de la branche.

Ainsi tu auras la liste de tous les chemins possibles.
Comme il y a plusieurs chemins, tu as une liste (de chemins).
Et comme une suite d'ancêtres est une liste, tu obtiens bien une liste de liste.

[Chablis]

Merci pour ta réponse.

Je ne comprends le bout "tu appelles la fonction en transmettant les ancêtres".

Je comprends le principe, j'ai fait cet algorithme :

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def af(arbre,i):#renvoie une liste de processus, un processus peut etre une liste d'operations ou une unique operation (str)
 
    if isinstance(arbre,Sequence):
        return [af(arbre.Enfants[i],i) for i in range(len(arbre.Enfants))]
 
    if isinstance(arbre,Operation):
            return arbre.Nom
 
    if isinstance(arbre,Boucle):  #je considere que boucle n'a qu'un seul enfant
        for i in range(arbre.N):
            af(arbre.Enfants[0],0)
    if isinstance(arbre,Choix):
        return [af(arbre.Enfants[i],0) for i in range(len(arbre.Enfants)) ]

Quand j'applique mon algorithme avec l'arbre "Sequence1" (sur la photo), j'obtient le résultat : [chauffage,[[laminage,roulage],ecrasage]]J'aimerai obtenir : [[chauffage,laminage],[chauffage,roulage],[chauffage,ecrasage]].

[Flodelarab]

Le tout n'est pas cohérent. Ton arbre est mal dessiné.

Les "choix" doivent être aux intersections.

Et "chauffage" n'est pas commun à tous les parcours de ton arbre.
Pourtant "chauffage" commence tous tes processus rêvés.

[anapurna]

salut

si je comprend bien ta structure est de ce genre ?

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
 
BOCK0  [
DEBUT SEQUENCE1
  BOCK1  [chauffage]
  BOCK2  [  
    TEST1 OUI
       BOCK3[ecrasage]
    TEST1 NON
      BOCK4
      [ TEST2  OUI
          laminage
       TEST2  NON
          roulage
        FIN TEST2
      ]
   FIN TEST1
  ]
FIN SEQUENCE1
]

Donc quand tu vas le lire et le mettre dans l'arbre tu devrais obtenir

[chauffage,[ecrasage,[laminage,roulage]]]

[SEQUENCE1,[TEST1,[TEST2]]]

test processus doivent imperativement etre une liste même de 1 element mais
en fait le processus doit être une feuille de ton arbre et pas un nœud

pour obtenir ceci
[[chauffage,laminage],[chauffage,roulage],[chauffage,ecrasage]]
il te faut repérer la dernière feuille et vérifier que tu n'est pas déjà passé par celle-ci
et remonter dans ton arbre jusqu’à la racine