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 (donné) 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 ?
Si possible un algo qui repose sur la recherche en profondeur à partir du sommet initial.
 
Merci d'avance et @ bientot !

Ben tu donnes la réponse toi-même, non ? Tu fais une recherche en profondeur toute simple. Style :
 

 
Ca revient en gros à regarder si un mot donné de longueur k sur un alphabet à une lettre unique est reconnu par l'automate non déterministe correspondant à ton graphe où toutes les lettres se confondent en une.

Le problème c'est que si le graphe comporte un circuit ou un arc reflexif ( un sommet pointe sur lui meme ), l'algo va tourner en rond.
 
Le problème est que cet algo ( je pense ) n'effectue pas toutes les possibilitées. Si au bout de k étapes, on est pas sur un état final, il faut revenir en arrière pour visiter le successeur suivant de l'état précédent ( s'il existe ).

Mon programme ne boucle pas indéfiniment puisqu'il atteint une profondeur de k. De plus tous les chemins possibles sont explorés, c'est le principe du parcours en profondeur.
 
Il faut "penser récursivement" : ma boucle explore tous les successeurs de "etat_courant" (si on renvoie VRAI à un moment, c'est fini), donc elle explore tous les chemins possibles de longueur k à partir de l'état initial si besoin.

d'ou l'importance de borner la taille du mot a rechercher  
tu ne peux pas , avec ce type d'algo retrouver des mot de type ab*

flo850 pour l'instant je ne cherche pas a trouver si un mot ab* ou abba* peut etre généré par l'automate représenter par le graphe.
 
Je cherche juste à savoir s'il peut générer des mots de longueur k.
 
( Quand j'aurai fini ce probleme, il me faudra savoir, si l'automate peut générer des mots ayant pour facteur une sous suite de symbole donnée. Par exemple on me donne la suite abba, je dois savoir si un mot du style b'abba'bba peut etre engendré par l'automate )

Ben l'algo je te l'ai donné, je vois pas ce qu'il te faut de plus... Tu peux l'optimiser en évitant de boucler k-i fois sur le même état s'il est terminal, mais le principe du parcours en pronfondeur c'est ça, et mon algo fonctionne très bien.

J'ai codé ton algo :
 

 
Mais ca ne marche pas

Dans le cas où le graphe se résume a un seul sommet qui posséede un arc reflexif, ca coince déjà ^^
 
Car il va aller sur le successeur ( donc lui meme ), il va relancer la fonction, ca va aller sur le successeur ( lui meme encore ), et il va encore relancer, et ainsi de suite ...

Si cpt == k, il faut s'arrêter que l'état courant soit terminal ou non ! Là en effet tu as une jolie récursion infinie.
 
Je te conseille aussi de créer des "boîtes noires" du style "est_terminal()", "est_initial()"... enfin bref, faire de la programmation objet, ça me paraît être adapté à la situation.

 
c'est différent de :
 

Si cpt = k, il ne faut pas s'arreter forcément.
 
En effet, si on part de l'état initial qui ne possede dans ces successeurs qu'un sommet x, lequel x possede un arc reflexif ( et d'autres successeurs ), lorsqu'on va arriver sur x, on va revenir sur x, puis encore sur x, jusqu'a avoir cpt = k. Donc selon toi il faut s'arreter et conclure que le graphe n'engendre pas de mot de longueur k. Hors on n'aura pas visité la descendance complete de x.
 
Du coup pour résoudre le probleme, cela devient plus compliqué, et je n'y arrive pas :@

Tu parlais d'automate dans ton premier post... Pour moi "engendrer" un mot de longueur k voulait dire "l'automate fini correspondant au graphe reconnaît le mot de longueur k". Dans ton exemple, après k itérations, si l'état sur lequel on a bouclé est terminal, alors le mot est reconnu, sinon le mot n'est pas reconnu.

Un mot de longueur k est un mot quelconque possédant k symboles.
 
Si l'état sur lequel on a bouclé n'étais pas terminal, alors il faut quand meme exploré le reste du graphe ( qui dans mon cas représente bien un automate non déterministe )

 
Si ton graphe ne comporte qu'un sommet qui boucle sur lui même je ne vois pas ce qu'il reste à explorer... S'il comporte d'autres sommets, ils seront explorés puisque qu'à partir de chaque sommet on explore tous ses voisins et donc au final tous les états accessibles (en au plus k transitions évidemment !) puisqu'on part de l'état initial.
 
Ça me paraît quand même pas difficile à comprendre... Il faut voir que l'algorithme que j'ai décrit plus haut réalise un backtracking, c'est à dire qu'il teste si en partant du premier voisin du sommet courant, le résiduel de longueur k-1 est reconnu, sinon il regarde en partant du deuxième voisin, et ainsi de suite jusqu'à ce qu'il en trouve un à partir duquel on atteint un état terminal au bout de k-i itérations (s'il n'en trouve pas la boucle se termine et la fonction renvoie FAUX).

MERCIIIII A TOI alerim ! ! !
 
Tu m'as ouvert les yeux
 
Il me manquait juste un test dans mon code ( oublie ), du coup l'algo ne fonctionnait pas ^^
 
En effet j'ai rajouté à ton algo :
 

 
Le test si on avait depassé k.
 
VOILA en tout cas un grand merci à toi, tu as eu du courage avec moi ^^
 
Allé merci encore et @ bientot peut etre

Hum, je suis pas sûr que tu aies tout saisi si tu penses qu'il est utile de tester i > k. C'est inutile puisque pour appeler rechercher avec la valeur k+1 pour le paramètre i, il faudrait avoir passé "SI i == k ALORS" avec i == k. Or dans ce cas, on quitte la fonction donc ça n'est pas possible d'atteindre une valeur strictement supérieure à k pour i.
 
En revanche dans ton implémentation du dessus, tu ne fais pas que tester "i == k", tu testes également si l'état courant est terminal. Finalement tu as dû écrire quelque chose du style :
 

 
qui est équivalent à :
 

 
qui fait l'économie d'un niveau de récursion.

Si on ne met pas le test cpt > k, cela ne marche plus.
 
En effet, pour TOUT cpt != k, on ne retournera rien avec ton premier test. Donc on arriverai directement sur la boucle while et là, la boucle peut etre infinie à cause des cycles ou arcs reflexifs ...

Pour la complexité par contre, t'as une idée ?
 
Je pense que c'est du O(n + m) mais le parametre k a son importance quand meme
 
n = nombre de sommet
m = nombre d'arc

 
Non, combien de fois faut-il le répéter... Quand cpt vaudra k, la récursion (ce que tu appelles la boucle) se terminera sauf si tu fais le test que tu as ajouté dans le if (savoir si l'état courant est terminal ou pas) et qui n'est pas au même endroit dans mon algo. Je le répète une dernière fois : mon algo est correct et ne boucle PAS indéfiniment et ta version est inutilement compliquée.
 
Edit: Hum j'ai lu un peu trop vite, tu parles de la boucle "while" qui pourrait être infinie ? Si ça se produit c'est un problème d'implémentation. Tu dois  récupérer la liste des sommets qui peuvent être atteints à partir du sommet courant. Cette liste est finie et tu la parcours séquentiellement, donc ta boucle while ne devrait pas pouvoir être infinie en aucun cas. Et de toutes façons dans ce cas le test cpt > k n'a absolument rien à voir avec ce problème.
 
Ah puis aussi :
 

 
Ben si cpt != k, c'est nécessairement que cpt < k, et donc on n'a pas fini. Et donc on rentre la boucle while qui elle va se terminer (puisqu'à un moment cpt vaudra k, il faut comprendre que la récursion n'est pas infinie, en aucun cas !).

LOOOL, on ne marque pas les sommets visités, donc si y'a un arc reflexif, on va boucler sur un somment et aucun test dans ton algo permet de palier a ce probleme.
En bref, ton algo marche si on rajoute mon test, c'est tout ca que je constate, et je trouve ca tout a fait logique !

 
Bon t'as rien compris tant pis pour toi, on pourra pas me reprocher de pas avoir essayé.
 
Ciao.

C'est bon lol j'ai compris ^^
 
En fait quand j'avais implémenté j'ai laissé if(est_terminal) quand i == k. Au lieu de faire un return(est_terminal).
 
Ton algo marchait donc bien ^^
 
Allé merci encore