Comparaison de l'algorithme de dijkstra et a* sur le trajet de métro parisien

Soyez le premier à donner votre avis sur cette source.

Vue 7 194 fois - Téléchargée 689 fois

Description

Bonjour, je suis en train de réaliser un projet sur la comparaison du rendement des algorithme A* et Dijkstra.

Le code que je fourni possède un petit beug que je n'arrive pas encore à résoudre :

Dijkstra fonctionne pas sur tous les trajets et A* non plus.

Pourriez m'aider?
Par la suite je rajouterai une modélisation en SDL.

Merci beaucoup

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
13
Date d'inscription
jeudi 15 octobre 2009
Statut
Membre
Dernière intervention
29 octobre 2013

Une fois placé sur une carte les stations sont placées aux bonne coordonnées ma foi. Ensuite les trajets sélectionnés par dijkstra correspondent bien à des trajets "sans crochets" donc ils sont probablement pertinents aussi. Par conséquent je pense que le ficher contient bien des données fiables mais attention elles datent d'au moins 3 ans.
Messages postés
17
Date d'inscription
samedi 16 décembre 2000
Statut
Membre
Dernière intervention
8 juillet 2011

Merci derdonn pour ta précision sur le fichier metro.txt. Tu pense que c'est des données réelles ou bien des chiffres crédibles qui ont étés inventés pour le projet ?

vdujardi je te fait signe si je trouve l'erreur.

Cordialement.
Messages postés
13
Date d'inscription
jeudi 15 octobre 2009
Statut
Membre
Dernière intervention
29 octobre 2013

Utiliser le trajet de métro parisien pour apprendre Dijkstra est probablement un classique chez les profs de programmation puisque j'avais également eu ça en TP de C en 1ere année d'école d'ingé. L'utiliser pour comparer Dijskstra/Astar c'est ça qui succite mon intérêt.

Perso je connais pas Astar. vdujardi tu penseras à poster une petite synthèse de tes résultats d'investigation à l'issue de ton projet?

Le fichier metro.txt passe probablement de main en main entre profs. Mais effectivement je m'étais posé la même question à l'époque... comment ils ont fait pour se procurer ce fichier?
Messages postés
17
Date d'inscription
samedi 16 décembre 2000
Statut
Membre
Dernière intervention
8 juillet 2011

Super projet, félicitation !

L'exemple est très concret, j'aime vraiment votre idée.
Il n'y a plus qu'a trouver le(les) bug(s).

Ça fait longtemps que je n'ai pas fait de C++, parce qu'aujourd'hui je programme en Java
(la mode ...).

C'est pas grave, je vais installer devcpp pour tester votre programme.
Je vous donne des nouvelles si je trouve le bug (je vous garantis pas une réponse rapide,
parce qu'en ce moment j'ai plutôt plein de travail).

PS1 : J'aimerai savoir comment vous avez trouvé les données pour le fichier "metro.txt"

PS2 : vous méritez la note maximum, mais il vaut mieux vous l'attribuer après debugage.

Cordialement

Numerico

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.