Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1843 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  algo de graph

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

algo de graph

n°442814
os2
Posté le 28-06-2003 à 20:38:12  profilanswer
 

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
mood
Publicité
Posté le 28-06-2003 à 20:38:12  profilanswer
 

n°442816
Willyzekid
Posté le 28-06-2003 à 20:45:32  profilanswer
 

un algo déterministe? qui te retournera toujours le même chemin?


---------------
Horizon pas Net, reste à la buvette!!
n°442830
os2
Posté le 28-06-2003 à 21:22:59  profilanswer
 

en plein ca


---------------
Borland rulez: http://pages.infinit.net/borland
n°443143
MagicBuzz
Posté le 29-06-2003 à 17:52:02  profilanswer
 

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 :D)

n°443173
gizmo
Posté le 29-06-2003 à 18:32:02  profilanswer
 

MagicBuzz a écrit :

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 :D)


tout à fait.
non seulement il faut des critères de parcours mais également des info sur le type de graphe.

n°444500
os2
Posté le 30-06-2003 à 19:17:17  profilanswer
 

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


---------------
Borland rulez: http://pages.infinit.net/borland
n°444510
gizmo
Posté le 30-06-2003 à 19:22:37  profilanswer
 

bah si tu n'as que ça comme info, j'ai bien peur que tu doives te taper un bête backtracking

n°444553
os2
Posté le 30-06-2003 à 19:44:24  profilanswer
 

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 :)


---------------
Borland rulez: http://pages.infinit.net/borland
n°444561
trueslash
(╯°□°)╯︵ MMM
Posté le 30-06-2003 à 19:48:34  profilanswer
 

prolog  [:tatanka]


---------------
sympathisant UBCT
n°444566
gizmo
Posté le 30-06-2003 à 19:51:51  profilanswer
 

ton graphe est orienté ou pas?

mood
Publicité
Posté le 30-06-2003 à 19:51:51  profilanswer
 

n°444575
os2
Posté le 30-06-2003 à 19:57:27  profilanswer
 

gizmo a écrit :

ton graphe est orienté ou pas?


pas orienté


---------------
Borland rulez: http://pages.infinit.net/borland
n°444577
gizmo
Posté le 30-06-2003 à 20:04:41  profilanswer
 

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.

n°444596
okeefe
Posté le 30-06-2003 à 20:54:16  profilanswer
 

j'ai déjà fait un truc du genre en java, mai j'ai pu le code

n°446846
okeefe
Posté le 02-07-2003 à 20:11:22  profilanswer
 

gizmo a écrit :

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.


 
si c'est si con pourquoi ta pas pondu le code qui le fait

n°446963
gizmo
Posté le 02-07-2003 à 22:54:04  profilanswer
 

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.

n°447079
okeefe
Posté le 03-07-2003 à 05:50:07  profilanswer
 

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...

n°448099
os2
Posté le 03-07-2003 à 20:46:49  profilanswer
 

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?


---------------
Borland rulez: http://pages.infinit.net/borland

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  algo de graph

 

Sujets relatifs
[VBA] [ALGO] Découper une chaine de charactères d'après séparateurAlgo de génération de dégrade [RESOLU]
[Java/Algo] Reconnaitre un disque dans un image[Algo] + longue Sequence commune à 2 sequences
Algo pour conversion Timestamp <-> Date ISOalgo de conversion d image 16 bits en 24 bits
Algo QuickSearch[SGBD]Créer un graph des clés étrangères à partir d'une base existante
[Algo] Affichage d'un tableau dans un format particulierprobleme d'algo pour affichage de graph
Plus de sujets relatifs à : algo de graph


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR