Discussion :

[GayaStudent]

Salut

J'ai un graphe orienté qui contient des cycles et des boucles. Je voudrais afficher tous les chemins entre deux noeuds en respectant une contrainte de longueur pour eviter de boucler infiniment sur un le meme noeud. J'ai essayé un plusieurs algorithmes mais ils ne marchent pas à cause des boucles.

Avez vous un bon algorithme qui peut résoudre mon problème?

Merci d'avance

[Invité]

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
noeudA
noeudB
noeudsVisites
explore(noeud)->
  si noeud == noeudB
    afficher(noeudVisites)
  pour tous les voisins de noeud as voisin
    si voisin dans noeudVisites
      //ne pas explorer... cest un cycle
    sinon
      noeudsVisites.push voisin
      explore(voisin)
      noeudsVisites.pop
 
explore(noeudA)

[GayaStudent]

Merci pour votre pseudo code galerien69. Mais je dois considérer les cycles et les boucles. C'est a dire je cherche un algorithme qui peut afficher tous les chemins entre deux noeuds d'un graphe orienté cyclique en respectant une contrainte de longueur pour eviter les boucles infinies sur un même noeud. par exemple: afficher tous les chemins de longueur <= 4 entre deux noeuds A et B.

J'ai essayé d'adapter l'algorithme de la recherche taboo en ajoutant une condition de longueur mais il ne donne pas les résultats voulus.

Avez vous une idée pour résoudre ce problème?

Merci

[Invité]

je ne vois pas en quoi mon algorithme ne répond pas à tes conditions.
A partir du moment ou les cycles sont détectés, quel est le problème?

[R. Daneel Olivaw]

J'ai l'impression que le problème n'est pas d'éviter les cycles.

Au contraire, si une boucle est suffisamment courte pour que l'emprunter plusieurs fois ne fasse pas dépasser la longueur maximal alors elle peut apparaitre n fois dans une solution.

Le seul problème est alors d'éviter les boucles infinies.

Si c'est bien ça, un simple compteur sans contrôle sur les nœuds déjà visités devrait suffire :

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
 
noeudA // nœud de départ
noeudB // nœud d'arrivé
pileDeNoeud // chemin actuellement parcouru
longueur_max = 4
 
fonction traiteNouveauNoeud ( nouveau_noeud )
{
    pileDeNoeud.ajouter(nouveau_noeud);
 
    si ( nouveau_noeud = noeudB) alors afficher pileDeNoeud
    sinon
    {
        si (pileDeNoeud.taille < longueur_max)
        {
            pour tout noeud accessible  depuis nouveau_noeud
            {
                 traiteNouveauNoeud(noeud )
            }
        }
    }
    pileDeNoeud.enlever(nouveau_noeud);
 
}
 
traiteNouveauNoeud (noeudA )

Cet algorithme tolère que l'on passe plusieurs fois sur le nœud de départ mais se s'arrête au premier passage sur le nœud d'arrivé et un cycle peut intervenir n fois tant que la longueur maximale ne dépasse pas le max.

[tbc92]

Bonsoir,
Je pense qu'on est en plein dans l'application de l'algorithme A*

Généralement, les tutoriels sur cet algorithme commencent par une exploration systématique de tous les chemins, puis optimisation, en choisissant le meilleur chemin.
Il suffit d'appliquer l'algo brut, avant optimisation.
La question qui peut devenir essentielle, c'est : 'Quel volumes de données ?'
Si chaque point a 3 ou 4 fils, et si on accepte des arbres jusqu'à 100 étapes ou plus, ça va vite devenir catastrophique en terme de performance.