Discussion :

[bugmenot]

Salut,

Voilà je travaille sur les graphes orientés, plus précisemment sur des graphes ayant des arcs valués par des symboles. Mon graphe représente donc un automate. Chaque arc qui relie 2 sommets, a pour longueur 1.

Je cherche donc un algo qui permet de trouver s'il existe un chemin de longueur k entre l'état initial ( le sommet source du graphe ) et un état final de l'automate ( un sommet quelconque ). Autrement dit si l'automate permet de générer des mots de longueur k.
Le graphe représentant l'automate peut comporter un ou plusieurs cycles, ou pas du tout.

Connaissez vous un algo qui permet de résoudre ce problème ? Ou avez vous une idée ?

Merci d'avance et @ bientot !

[Nemerle]

http://recursivite.developpez.com/?page=page_5 section IV-L

[bugmenot]

Ca m'a pas aidé :/

Ce que je veux, c'est un algo qui repose sur la recherche en profondeur à partir du sommet initial.

Si certain connaisse déjà le problème, un peu d'aide me ferai pas de mal siouplé

[FrancisSourd]

C'est l'algo de Ford-Bellman mais tu ne t'intéresse qu'à l'accessibilité d'un sommet sans t'accuper de la longueur des chemins.

A partir du sommet initial, on a trivialement tous les sommets qui peuvent être atteints en 1 arc (et le plus court chemin associé).

De manière récursive, quand on a les sommets accessibles par un chemin de k arcs depuis le sommet initial, on obtient facilement les sommets accessibles par un chemin de k+1 arcs (c'est l'ensemble des voisins)

C'est l'algo signalé par Nemerle, j'espère que le nom de l'algo (avec google) et ces quelques explications t'inspireront plus...

[sylk974]

Il y aurait une réponse naïve :

Tu fais un algo de plus court chemin en enlevant les cycles.
Si tu trouves un chemin de longueur inférieur à ton k
tu peux le faire augmenter grace aux cycles ...

[fearyourself]

Encore plus naïf,

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
Soit A l'ensemble des états accessible
 
Initialiser A avec l'état de départ.
 
De 1 jusqu'à k
  Pour chaque sommet s dans A
      Ajouter dans A les sommets adjacents à s (en enlevant les doublons)
 
Pour chaque noeud s dans A
   Si s n'est pas un état final, le retirer de A

Jc

[FrancisSourd]

C'est en pseudo-code ce que je disais plus haut sauf que là tu regardes s'il y a un chemin de longueur inférieure ou égale à k. Pour avoir une longueur eactement égale à k, il faut modifier le code ainsi

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Soit A l'ensemble des états accessible
 
Initialiser A_1 avec l'état de départ.
 
Pour i de 2 jusqu'à k
  Pour chaque sommet s dans A_{i-1}
      Ajouter dans A_i les sommets adjacents à s (en enlevant les doublons)
 
S'il y a un état final dans A_k, c'est gagné!

[fearyourself]

C'est en pseudo-code ce que je disais plus haut sauf que là tu regardes s'il y a un chemin de longueur inférieure ou égale à k

Tu as entièrement raison, va savoir pourquoi je l'ai loupé... Ca m'apprendra de lire en diagonale!

[chebreg]

Je pense qu’il ne faudrait pas se contenter des chemins les plus courts entre le nœud de départ S et les nœud terminaux F(i) mais plutôt essayer d'avoir la liste de tous les chemins sans cycle, allants de S vers tous les F(i), et marquer chaque chemin s’il comporte un cycle. En suite tu peux raffiner l’algorithme en réduisant cette liste par des règles.