ALGORITHME A*

Signaler
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
-
cs_mersin
Messages postés
1
Date d'inscription
mercredi 20 avril 2011
Statut
Membre
Dernière intervention
11 mai 2011
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/33092-algorithme-a

cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2
herve.picard@int-evry.fr pour toute question
rrk275
Messages postés
542
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2
Sur des graphes de petites taille ( le metro étant extrement petit) ne suffit t'il pas de mettre un algorithme qui trouve le meilleur chemin type dijkstra? Enfin c'est toujours utile d'un point de vue algo et explicatif...
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2
Le métro n'est pas si petit que cela, il y a 300 stations de métro et pas mal non plus de RER
Dijkstraa n'est pas optimal quant à la solution proposée. Maintenant pour mon exemple, je reconnais que cela aurait pu être plus adapté
rrk275
Messages postés
542
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2
j'ai un temps de reponse assez long mais sur 10 000 noeuds et autant de chemins que tu veuilles l'algorithme djikstra mettra moins d'une seconde alors tes 300 stations... c'est pas optimal

Louis
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2
Je regrette, comme tu peux le constater dans mon commentaire l'approche formelle de Djikstraa s'est révélée moins rapide que AStar (utilisant une approche heuristique type BFS)

Après calculs un peu plus savant, il s'avère qu'AStar, s'il ne garantit pas une résolution optimale du pathfinding (au sens du chemin le moins coûteux) sera toujours plus rapide que son homologue
Cordialement