j’ai bien lu le topic de post de GloP sur la place des sujets et je pense (oui ca m’arrive) que je ne me suis pas trompé de forum (enfin j’espère).
Donc, voilà la situation : j’ai un projet pour l’université qui traite des recherches de trajets sur un réseau ferroviaire (trajet optimal, puis avec des contraintes de minimisation des attentes…). Pour l’instant je n’en suis qu’au stade de la réflexion mais je me demande quel algorithme de parcours de graphe est le plus approprié.
D’après mes connaissances et d’après une recherche sur Google, il semblerait que l’algorithme de Dijkstra soit assez bien adapté.
D’où ma question : est-ce-que je devrai utiliser celui-ci ou un autre (par ex: A*…) ?
Pour un simple trajet optimal d’un point à un autre, fais un Dijkstra.
Le rajout de conditions spécifiques(genre temps d’attente max à chaque gare ?) est simplement rajouté dans ton test pour savoir si le chemin testé vaut la peine d’être poursuivi (celui qui regarde si tu dépasses pas déjà ton meilleur chamin trouvé).
Si tu veux tous les chemins de chaque point à tous les autres, tu utilises Floyd je pense.
(Me souviens plus du A* d’ailleurs, tu me rafraichis la mémoire ?)
Ce message a été édité par Xma le 06/10/2004 Ce message a été édité par Xma le 06/10/2004
[quote](Me souviens plus du A* d’ailleurs, tu me rafraichis la mémoire ?)
[i]
[/i] A* est une sorte de version améliorée de Dijkstra où chaque noeud du graphe possède des coordonnées.
Le noeud que l’on visite après est celui dont la distance estimée entre lui et le point d’arrivée ajoutée à la longueur du trajet déjà parcouru est la plus faible (je sais pas si j’ai été clair sur ce coup là).
[quote]j’ai fait ca pendant mes etudes en IA, et il me semble qu’on avait utilisé A*
de memoire hein
on avait meme fait ca en lisp …[/quote]
Effectivement, je viens juste de le faire en IA, en Lisp.
Enfin, pour en revenir à mon problème, il ne me semble pas que l’algorithme de Floyd soit des plus appropriés. Etant donné qu’il va falloir que je gère un graphe assez costaud (le réseau ferroviaire suédois) et pour des raisons de rapidité d’exécution évidentes, il me faut le top du top de l’algorthime de parcours de graphe (dans la limite du codable quand meme).
Donc si quelqu’un a une autre piste que Floyd, je suis preneur.
Il me semble (je ne suis pas un expert en la matière) que A* c’est un Dijkstra amélioré. De plus (et là j’en suis sûr) c’est A* qui est utilisé dans la quasi totalité des jeux pour faire un pathfinding efficace et rapide. Donc moi je dirais A*.
[quote][quote]j’ai fait ca pendant mes etudes en IA, et il me semble qu’on avait utilisé A*
de memoire hein
on avait meme fait ca en lisp …[/quote]
Effectivement, je viens juste de le faire en IA, en Lisp.
Enfin, pour en revenir à mon problème, il ne me semble pas que l’algorithme de Floyd soit des plus appropriés. Etant donné qu’il va falloir que je gère un graphe assez costaud (le réseau ferroviaire suédois) et pour des raisons de rapidité d’exécution évidentes, il me faut le top du top de l’algorthime de parcours de graphe (dans la limite du codable quand meme).
Donc si quelqu’un a une autre piste que Floyd, je suis preneur.
[/quote]Ben tu n’as pas donné ta question exacte …
Si tu veux faire une recherche d’itinéraire à la demande :
soit tu fais un Dijkstra avec le départ/arrivée introduit par l’utilisateur (amélioré avec des critères supplémentaires si tu veux). --> O(N²)
soit tu fais un Floyd, qui te donnera , en une fois, un tableau avec toutes les trajets minimaux entre chaque paire de gare. --> O(N³)
Mais tu trouveras pas vraiment beaucoup mieux pour trouver les trajets optimaux.
Maintenant si tu as des contraintes de temps d’éxécution, tu peux te tourner vers les algos génétiques, mais qui ne te fourniront pas de façon certaine une solution optimale…
[quote]Maintenant si tu as des contraintes de temps d’éxécution, tu peux te tourner vers les algos génétiques, mais qui ne te fourniront pas de façon certaine une solution optimale…[/quote]Mais qui te fileront une solution proche d’un truc sympa en temps fini, c’est deja ca A priori quand j’en ai fait on m’a dit que c’est comme ca que sont geres les trajets des controlleurs aeriens (ouai ca fait peur) parceque les algo en 3d prendrait trop de temps poru determiner une solution optimale et que l’essentiel c’est surtout qu’ils se rentrent pas dedans, pas qu’ils mettent 1min30 au lieu de 2min a atterir… Ce message a été édité par GloP le 06/10/2004
[quote][quote]Maintenant si tu as des contraintes de temps d’éxécution, tu peux te tourner vers les algos génétiques, mais qui ne te fourniront pas de façon certaine une solution optimale…[/quote]Mais qui te fileront une solution proche d’un truc sympa en temps fini, c’est deja ca A priori quand j’en ai fait on m’a dit que c’est comme ca que sont geres les trajets des controlleurs aeriens (ouai ca fait peur) parceque les algo en 3d prendrait trop de temps poru determiner une solution optimale et que l’essentiel c’est surtout qu’ils se rentrent pas dedans, pas qu’ils mettent 1min30 au lieu de 2min a atterir… Ce message a été édité par GloP le 06/10/2004[/quote]Tout-à-fait, je trouve aussi que c’est une solution bien plus élégante que de “bêtement” tester tous les chemins Mais bon, si pour son projet à l’unif, ils veulent de l’optimal, ils seront ptet pas contents… donc à voir selon l’énoncé.
Mais algos génétiques rulez ! (quand on voit comment ils explosent (en terme de qualité du résultat en seulement qques tours de boucle) Dijkstra pour les problèmes classiques type voyageur de commerce… Ce message a été édité par Xma le 07/10/2004