Discussion :

[esperance]

salut
j'ai developper un unprogramme en java qui permet de calculer les chemins possible de longeur 1 jusqu'a N-1 avec N nombre de noeuds de graphe. Mon problemme c'est qu'il es trop long en temp d'execution. je sais bien ce temps a cause au nombre d'iteration . Est ce que tu peut me donner d'autre truc pour passer ou minimiser le temps en trouvant les cas possibles entre les couples des noeuds dans un graphe complet
Merci

[PRomu@ld]

Quel algo a tu utilisés ?

En fait la fermeture transitive doit pouvoir se calculer en n^3 avec Warshall.

On peut l'optimiser un petit peu comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
M : matrice booléenne
 
M <- Matrice d'adjacence du graphe.
 
POUR k de 1 à n FAIRE
     POUR i de 1 à n FAIRE
          SI M[i,k] ALORS
               POUR j de 1 à n FAIRE
                    M[i,j] <- M[i,j] OU M[k,j]
               FIN POUR
          FIN SI
     FIN POUR
FIN POUR

En fait l'optimisation consiste à ne faire la boucle la plus imbriquée que dans le cas où M[i,k] est vrai. (car sinon ça revient à faire M[i,j] <- M[i,j] ). Tu peux faire une seconde optimisation en rajoutant un test lors de la deuxième boucle pour ne pas tester les valeurs sur la diagonale (rien ne sert de calculer si tu as un chemin de i à i).

[Jean-Marc.Bourguet]

Tu cherches a determiner les noeuds accessibles ou a enumerer tous les chemins possibles? L'enumeration est potentiellement exponentielle en fonction du nombre de noeud simplement parce qu'il y a un nombre exponentiel de resultats a enumerer. Et ca prend effectivement du temps.