algo de graph - Algo - Programmation
Marsh Posté le 28-06-2003 à 20:45:32
un algo déterministe? qui te retournera toujours le même chemin?
Marsh Posté le 28-06-2003 à 21:22:59
ReplyMarsh Posté le 29-06-2003 à 17:52:02
Y'a des critères pour le parcours du graph ?
Parceque si on ne connait pas les éventuels critères, on pourra pas répondre je pense (mais bon, j'y connais pas grand chose en graphe )
Marsh Posté le 29-06-2003 à 18:32:02
MagicBuzz a écrit : Y'a des critères pour le parcours du graph ? |
tout à fait.
non seulement il faut des critères de parcours mais également des info sur le type de graphe.
Marsh Posté le 30-06-2003 à 19:17:17
en fait l'algorithme doit compter les chemins de longueur donnée entre deux n?uds d?un graphe (avec ou sans répétition)
et un autre algorithme doit compter les chemins sans répétition de longueur donnée entre deux noeuds
Marsh Posté le 30-06-2003 à 19:22:37
bah si tu n'as que ça comme info, j'ai bien peur que tu doives te taper un bête backtracking
Marsh Posté le 30-06-2003 à 19:44:24
Les résultats doivent être conservés dans des matrices. NbChemins[1..N,1..N,1..Lmax] Lmax (longueur des chemins) : 1 à 12.
Ex : NbChemins[8,1,10] : nombre de chemins de longueur 10 qui nous permettent de nous rendre du n?ud 8 au n?ud 1
alors je me prépare à me mettre une corde au coup
Marsh Posté le 30-06-2003 à 19:57:27
gizmo a écrit : ton graphe est orienté ou pas? |
pas orienté
Marsh Posté le 30-06-2003 à 20:04:41
bah c'est assez con alors:
tu pars d'un sommet et tu notes les distances pour chaque voisin (et réciproquement) dans ton tableaux et tu mets tous les voisins dans une "pioche". Suivant l'algo tu marques ou pas les arrètes utilisées pour éviter les répétitions.
Tu pioches un voisin au hasard et tu recommences comme pour le premier (sauf arrètes marquées), mais en plus, pour chaque voisin que tu atteind, tu peux récupérer toutes les valeurs qu'il a déjà parcouru pour gagner du temps.
Et tu jètes les voisins quand ils ont dépassé 12.
Marsh Posté le 30-06-2003 à 20:54:16
j'ai déjà fait un truc du genre en java, mai j'ai pu le code
Marsh Posté le 02-07-2003 à 20:11:22
gizmo a écrit : bah c'est assez con alors: |
si c'est si con pourquoi ta pas pondu le code qui le fait
Marsh Posté le 02-07-2003 à 22:54:04
parce que je ne suis pas partisan de l'assistanat. S'il n'est pas capable de pondre un algo comme ça maintenant, ce n'est pas la peine qu'il continue dans cette voie. Lui donner des pistes, oui, lui macher le travail, non.
Marsh Posté le 03-07-2003 à 05:50:07
tu peux commencer par créer une matrice pour savoir les noeud du graph qui se touche....
tu auras une matrice avec des 0 et des 1
ensuite tu fais des power de ça...
Marsh Posté le 03-07-2003 à 20:46:49
salut
j'ai réussi à faire
? Le premier algorithme qui doit compter les chemins de longueur donnée entre deux n?uds d?un graphe (avec ou sans circuits);
il me reste à faire celui ci
? Le deuxième algorithme qui doit compter les chemins sans circuits de longueur donnée entre deux noeuds.
quelqu'un a une idée?
Marsh Posté le 28-06-2003 à 20:38:12
je recherche un algo déterministe pour les graphes pour aller d'un noeud x à un noeud y
---------------
Borland rulez: http://pages.infinit.net/borland