Version imprimable
Bonjour
Je ne sais pas quel algo choisir, je dois effectivement donner le plus cours chemin entre deux sommets dans un graphe. Les arrêtes non pas de valeur de longueur.
L'algorithme de Dijkstra n'a pas l'air d'être bon pour ce genre de graphe et l'algorithme A* me semble peu rapide dans certain cas.
Alors lequel choisir ? en connaissez-vous d'autre ?
Merci
Bonjour,
Si vous dites que le A* est un peu lent, alors je dirai que votre problème est NP-Complet (voir le signification sur le net).
Pour résoudre le problème, il faut utiliser des méthodes méta-heuristiques tel que le Algorithmes génétiques, recherche dispersée, colonies de fourmis.
Graphe non valué, recherche de chamin => problème NP-Complet :calim2:
Je pense plutôt qu'il s'agit d'un problème de taille d'instances, mais juste avec les infos initiales on ne peut pas t'aider.
ah ? pourquoi ?Citation:
Envoyé par Damoun
Le titre c'est: Le plus court chemin, et non pas un chemin quelconque. s'il s'agit seulement de trouver le chemin alors A* sera suffisant et rapide.Citation:
Envoyé par IDontLikeYou
Je suis bien d'accord, d'où le fait que je dise qu'on manque d'infos. Par contre je ne vois toujours pas ce que le NP-Complet vient faire là dedans ...Citation:
Envoyé par Bucketpc
Edit : d'ailleurs sur un graphe non valué au pire tu tapes un parcours complet en O(nm), donc ce doit forcément être un problème de taille d'instance.
D'apres ce que j'ai vu (wikipedia), A* peine a trouver le chemin dans cette situation:
http://upload.wikimedia.org/wikipedi...labyrinthe.png
Apres je ne vois pas quoi donner en plus comme precision
http://fr.wikipedia.org/wiki/Fichier...labyrinthe.png
Tu fais un parcours en largeur à partir de l'arrivée, en indiquant à chaque fois que tu passes sur un noeud la distance (la plus courte) entre ce noeud et l'arrivée.
Le chemin le plus court, ensuite, est celui dont les noeuds sont évalués à la plus faible distance.
Problème résolu. C'est du O(n).
Sa me semble bien comme solution :p
Merci