Discussion :

[mainecoon]

Bonjour,

Par rapport au schéma donné en pièce jointe, un diagramme de PERT (sans les dates au plus tôt et au plus tard), je recherche un moyen de trouver tous les chemins possibles.

J'ai défini la table de correspondances suivante :
----------
A;B
A;D
B;C
C;FIN
D;C
D;F
DEBUT;A
DEBUT;E
E;G
F;FIN
G;F
G;H
H;FIN
----------

Le programme doit afficher :
---------------------------
DEBUT -> A -> B -> C -> FIN
DEBUT -> A -> D -> C -> FIN
DEBUT -> A -> D -> F -> FIN
DEBUT -> E -> G -> F -> FIN
DEBUT -> E -> G -> H -> FIN


Il faut bien entendu utiliser une fonction récursive.


Des propositions ?

(Je code en VBA et en VB.NET.)

Merci de votre aide !

[mainecoon]

Voici une solution : (en VBA - Access 2003)
------------------

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
29
30
31
32
33
34
35
36
37
38
39
40
41
Option Compare Database
Private myDAODB As DAO.Database
 
Private Sub mysubLANCEMENT()
 
    myCHEMIN = ""
    Set myDAODB = CurrentDb
    Call mysubREC("DEBUT", "DEBUT")
 
    Set myDAODB = Nothing
 
End Sub
 
 
 
Private Sub mysubREC(myTACHE As String, myCHEMIN As String)
 
Dim myQuery As String
Dim myNextTache As String
Dim myDAOREC As DAO.Recordset
Dim mycheminsauv As String
 
If Not myTACHE = "FIN" Then 'si on n'est pas a la dernière tâche
    myQuery = "SELECT tbDEPENDANCES.* FROM tbDEPENDANCES WHERE (tbDEPENDANCES.TACHEDEPART = """ & myTACHE & """);"
    Set myDAOREC = myDAODB.OpenRecordset(myQuery)
    mycheminsauv = myCHEMIN
    Do Until myDAOREC.EOF = True
        myNextTache = myDAOREC!TACHEARRIVEE
        myCHEMIN = myCHEMIN & myNextTache
        Call mysubREC(myNextTache, myCHEMIN)
        myCHEMIN = mycheminsauv
        myDAOREC.MoveNext
    Loop
    myDAOREC.Close
Else
    'on est à la fin d'un chemin...
    Debug.Print myCHEMIN
End If
 
 
End Sub

Je suis intéressé par d'autres solutions !

Si qn a une idée...

[skip78]

Ce que je ne comprends pas c'est que le diagramme de P.E.R.T. sert justement à représenter le chemin critique. Donc pourquoi vouloir afficher l'ensemble des chemins ?

Et sinon tu n'auras aucune réponse en code dans la rubrique 'algorithmes' donc je te conseillerais vivement d'aller dans la rubrique apporpriée (VBA)
Moi perso j'en touche pas une en VBA

[mainecoon]

Bonjour,

Pourquoi avoir la liste des chemins ? Parce que j'en ai besoin !

Pour le langage, je ne pouvais pas aller en VBA, car ce n'est pas trop une question de langage...
Je le voulais bien aussi en VB.NET, en C# ou autre...

Alors, soit je postais sur x forum ou sur un forum généraliste...

Skip78, sinon as-tu une autre solution a mon problème ?

[skip78]

Bah au niveau algorithmique oui je sais comment fonctionne Pert, mais pour t'aider à partir de ton programme c'est impossible du fait que ca soit en VBA ... Par conséquent je ne connais pas ton problème .

En effet en language algorithmique, récupérer les chemins se dit 'recuperer les chemins' LOL

D'ailleurs j'ai pas l'impression que ca soit P.E.R.T. ton truc ???
Ca ressemble plus à un simple graph orienté je trouve

[Jedai]

En effet en language algorithmique, récupérer les chemins se dit 'recuperer les chemins' LOL

Ca dépend tout de même de la structure... Ici par exemple un simple parcours en profondeur suffit.

--
Jedaï

[skip78]

Oui mais comme je l'ai dit plus haut, BFS ou DFS ca s'utilise dans le cadre des graphs orientés, pas dans les diagrammes de PERT.
Enfin bref tout ca pour dire qu'il n'y a pas de réel problème ici, à moins que ca soit du code, mais ca ne semble pas être le cas ...

[borisd]

Que ce soit du PERT ou la méthode des potentiels ou autre chose, le problème a l'air de n'être que l'énumération des chemins possibles entre deux sommets dans un graphe décomposable en niveau (ça évite de marquer les sommets pour éviter les boucles).
En récursif pour stocker les chemins de s à t, un algo général peut être :

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
 
Fonction explorer(s:in,t:in,L:out) (L est la liste de chemins)
c <- liste composée de s 
explorer(t,L,c)
Fin fonction
 
Fonction explorer(t:in,L:in/out,c:in)
i <- dernier élément de c
si i = t alors
  ajouter c à L
sinon
  pour tout successeur j de i faire
    ajouter j en fin de c
    explorer(t,L,c)
    supprimer le dernier élément de c
  fin pour
fin si
Fin Fonction

C'est assez mal écrit, mais je ne sais pas si tu connais les structures de file et les termes algorithmiques qui vont avec...