Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
[graphe]les pls court chemin (rectification)
bonjour
je ne me rappelle plus (moi je crois que non) mais est-ce que c'est possible de connaitre le nombre de chemin maximal dans un graphe apartir de sa representation matrcielle ( en supposant qu'il n'y a pas de cycle dans mon graphe (je reglerai ce probleme avec le marquage)
merci
Je ne crois pas qu'il y ait une relation simple entre la matrice adjacence et le nombre de chemins du graphe. Tu dois confondre avec la propriété qui donne le nombre de parcours (on peut donc répéter les noeuds) de longueur donnée, entre deux noeuds du graphe, qui est :
"Si A est la matrice d'adjacence du graphe, le nombre de parcours de longueur k entre les noeuds i et j est égal à A^k (i, j)"
Par contre, il y a un autre moyen pas trop dur pour connaître le nombre de chemins dans ton cas. Tu dis que tu as un graphe sans cycle, c'est donc une forêt (ensemble d'arbres). Dans chaque composante connexe de ton graphe (qui est donc un arbre), tu sais que chaque noeud est relié par exactement un chemin à tout autre noeud de l'arbre.
Par conséquent, si tu as n noeuds dans ton arbre, tu as n*(n-1) chemins dans cet arbre. Il suffit donc de compter les nombres de noeuds de chaque composante connexe.
donc tu dis que si il n'y a pas de cycle dans le graphe, et supposant que dans mon graphe (ça sera la cas, car en fait c'est un automate d'etat finis)
il y'a un etat final et un etat debut, je peux connaitre tout les chemin qui vont de mon etat debut vers l'etat final, sans parcours le graphe
mais je crois qu'il y'a un probleme avec, car ça peut etre non deterministe
(t'as deux arcs qui sortent du meme etat vers un meme etat)
t'es sure que une composante connexe c'est un arbre?Envoyé par Denis++
je vais voir sur google mais je n'en suis pas sure
sans oublier que le graphe c'est des arcs diriges, donc je viens de voir sur googlemais le probleme que c'est orienteUn graphe est connexe ssi il existe un chemin entre chaque paire de sommets.
A B C D F
A 0 2 8 0 0
B 0 0 4 6 0
C 0 4 0 1 0
D 0 0 2 0 8
F 0 0 0 0 0
donc ce n'est pas vraiment une matrice d'adjecence mais de cout, donc est-ce apartir de cela on peut calculer le nombre maximal?
Tu peux calculer le chemin le plus long.
Ton graphe est sans cycle, si j'ai bien lu, donc tu auras le bon résultat...
Un algorithme de Bellman adapté devrait faire l'affaire.
Et ta matrice est bien une matrice d'adjacence, sauf qu'elle est valuée.
c'est pas ce que je veux mais le nombre maximaum de chemin entre l'letat de depart et l'etat final,
en d'autre terme
combien y'a t'il de chemin entre l'etat de depart et l'etat final?
Alors utilises une liste d'ajacence !
Tu peux partir de ta matrice et faire une lista d'ajacence, puis compter le nombre de chemins qui contiennent ces deux états.
Pardon, j'avais mal lu
ok je crois que je melange deux probleme different
en fait le premier c'est deux connaitre le nombre de chemin possible dans un graphe (mais je peux m'en passer ce n'est pas le plus utiles)
le deuxieme probleme mais c'est vraiment la le probleme
c'est de trouver le plus court chemin, le deuxieme plus court chemin, ainsi de suite sans faire un parcours complet du graphe
NEED HELP
Le plus court chemin, c'est toujours d'un sommet à un autre...
Je ne comprends pas ton "Deuxième plus court chemin"...
As-tu regarder l'algorithme de Bellman, par exemple ?
Ou encore de Dijkstra ?
salut progman
tu sais apres m'etre penche sur l'algorithme de djikstra
je crois que le probleme se rapporte a un branch and bound
je vais te poser une question et tu vas comprendre mon probleme
que fais l'algorithme djikstra? : il trouve le plus court chemin entre deux noeud, et si je veux connaitre le plus court chemin et le deuxieme plus court chemin (imagines que je cherche le plus court chemin enntre deux ville mais il y'a un probleme sur la derniere partie de la route ( mais theroriquement on ne sait pas ou se trouve le probleme, donc cherches moi le deuxieme plus court chemin
penches toi sur le probleme ça parrait facile mais c'est un peu dur
je crois que le branch and bound serait bien
Je suis désolé, mais en gros, tu cherches le plus court chemin d'une ville a une autre, ces deux villes pouvant être séparées par une troisième ville ?
C'est ça ?
Si c'est ça, Djikstra te le fait, mais un parcours en profondeur est plus adapté.
Ce n'est que mon avis, des algos il en existe plein, reste à savoir ce que tu veux exactement
je suis desole mais je n'arrive a bien m'expliquer
bon je vais faire un message tres detaille ( si on me comprends pas si que je ne parle plus en français) et moi qui voulait faire prof
bon voila le probleme,
-j'ai un graphe value.
-il contient un etat de depart (toujours le meme) appelons le S
-il contient X etat
- il contient un etat final appellons le F
- il y'a T chemins entre S et F, chaque chemin a un cout Ct
- la question trouvez moi les Q premier chemin |Q|<=|T|, tel que le cout des Q chemins soit ordonne par odre croisssant
desole je ne peux etre plus clair
OK, bon, je comprends déjà mieux.
Les solutions que j'ai ne sont pas optimisées (c'est fait en 5 minutes), mais l'idée ne doit pas être mauvaise...
En gros, il faut :
- Compter le nombre de chemins de S à F
- Calculer le coût de chacun de ces chemins
- Trier ces coûts
Comment compter ?
Appliquer l'algorithme de Floyd-Warshall te permettra de savoir si un chemin existe d'un sommet S à un autre sommet. Il fera un calcul de fermeture transitive. A mon avis c'est obligatoire. Autre solution : utiliser une liste d'ajacence, qui te donnera directement le nombre de chemins, ainsi que les sommets pour aller de S à F. Quand tu as cette liste, si on suppose que cetteliste ne se limite pas à une liste, mais qu'elle permet d'avoir les coûts entre chaque sommets, alors tu pourras calculer les coûts de chacun de ces chemins et ensuite faire le tri croissant.
Je préfère rappeler que l'algorithme de Djikstra ne s'applique qu'à des graphes valués de coûts positifs ou nuls (pour d'autres types, se reporter à Ford ou Bellman).
je ne comprend pas bien ta solution , mais je crois que c'est une solution exhaustive, si tu calcules tout les chemins, moi je voulais dire les Q chemin sans calculer les autres tu vois
en utilisant les branch and bound (sepration et evaluation) tu prend que les noeuds qui sont soit disant interessants, donc voila, si je me suis trompe sur l'exhausitivite de ta solution dis le moi
Je ne pense pas que ma solution soit exaustive.
Relis, mais je ne pense pas...
Le Branch and Bound, je ne connais pas.
Pour ma solution, il te faut créer une liste d'adjacence pour ton graphe, mais suivant le langage tu pourras réaliser plus ou moins facilement une liste utilisable pour le calcul des coûts de façon directe (par exemple, en POO, en créant une liste d'objets, chacun ayant un nom et un coût).
J'ai un algo qui pourrait t'aider mais je ne me souviens plus de son nom ou auteur... désolé pour les puristes. En gros, cet algo est semblable à un parcours en largeur prenant en compte les valuations. Il faut générer des chemins au fur et à mesure et les stocker dans une liste triée.
Au debut le chemin est représenté par ton seul état initial. Tu appliques tout les arcs partant de l'état initiale et ajoutes les chemins résultant dans la liste trié. Ensuite, tu prends le premier chemin de la liste triée(celui de cout le plus faible) et tu appliques les arcs sortant en ajoutant a nouveau les chemins résultant à la liste triée. et ainsi de suite.
Tu vois à peu près le truc?
oui c cela le principe du branch and bound (sepration evaluation)
donc si vous avez des liens ou il y'a une implementation de base pour cette algo , je vais l'adapter a mon probleme, le plus dur c'est de trouver la fonction de cout des chemin , car c'est pas des longueurs, mais des probablites, des risques, et une importance, donc
il faut que je me penche sur cela
Branch and Bound
Tenir compte du passif ( attribuer une valeur à chaque branche)
Utilise une liste ( ou file d'attente avec priorité)
1. Placer le nœud début de longueur 0 dans la liste.
2. Répéter jusqu'à ce que liste vide ou nœud recherché trouvé :
a) Si la première branche contient le nœud recherché, fin avec succès.
c) Sinon
- supprimer la branche de la liste et former des branches nouvelles en étendant la branche supprimée d'une étape.
- calculer les coût cumulés des branches et les ajouter dans la liste de telle sorte que la liste soit triée en ordre croissant.
3. Autrement " pas d'élément"
Et bien au moins je saurai comment ça s'appelle pour la prochaine fois!
moi je ferai quelque modification , car je ne cherche juste la meilleur branche, mais le premiere , la deuxieme ect, jusqu'a n defini par l'utilisateur
Ca va, c'est pas trop compliqué comme modification. Rien à voir avec le chemin que t'auras déjà parcouru
Répondre avec citation
Partager