Discussion :

[greg3105]

Bonjour à toutes et à tous!!!

Je viens a vous car j'ai un petit soucis.

Je souhaiterais arriver a calculer un trajet de métro.

Je m'explique: j'ai un fichier texte qui comprends les ligne de métro avec les differentes stations.

Je voudrais permettre à l'utilisateur d'entrer ces deux stations (départ et arrivée) et ensuite que le programme calcul les routes pour le trajet avec les changement de lignes.

Mon problème en ce moment est que je n'arrive pas à imaginer l'algorithme me permettant de calculé la route de mon trajet.


Si quelqu'un pourrais m'éclairer ce serais très aimable.

Cordialement,

Greg3105

PS: Je vais faire mon programme en JAVA

[Matthieu Brucher]

Y'a pleins de sujets dans ce forum là-dessus !

[piff62]

Pour information, l'algorithme du plus court chemin s'appelle l'algorithme de dijkstra
En utilisant je pense que tu peux trouver toute la documentation necessaire

[larnicebafteur]

Il faut s'interesser à la théorie des graphes pour ce genre de problèmes.
On peut trouver un document interessant sur le net :
http://www4.ac-lille.fr/~math/classe...es/Graphes.pdf

On y trouve l'algorithme de dijkstra, mais il en existe d'autres ...

[BugFactory]

L'algirtithme A* est plus performant que l'algorithme de Dijkstra mais aussi bien plus complexe.

[TanEk]

Je ne vois pas où l'algorithme A* est bien plus complexe que l'algorithme Dijkstra. Si je ne m'abuse, ce n'est qu'un rajout d'une fonction heuristique. Corrigez-moi si je me trompe.

[Matthieu Brucher]

Tu ne te trompes pas.

[BugFactory]

Certes, ce n'est "que" l'ajout d'une heuristique.

C'est plus complexe pour plusieurs raisons. D'abord, c'est plus difficile à comprendre. L'algorithme de Disktra est immédiat, pas A*. Ensuite, il faut trouver une bonne heuristique. Ca peut être trivial tout comme ça peut être très difficile. Enfin, le débogage est compliqué par le fait que même avec une heuristique défailllante l'algorithme peut fonctionner normalement la plupart du temps.

[TanEk]

Ouais... je ne vois pas en quoi la notion de vol d'oiseau comme heuristique soit compliquée à comprendre... même un gamin de maternelle la comprend. Et je ne vois pas en quoi l'algorithme dijkstra est immédiat alors que passer de dijkstra à A* est immédiat.

Enfin, le débogage est compliqué par le fait que même avec une heuristique défailllante l'algorithme peut fonctionner normalement la plupart du temps.

Du moment qu'une heuristique donne de meilleurs résultats "statistiquement" (j'entends par là dans la plupart des cas), qu'elle soit "fausse" ou "vraie" n'a aucune importance, elle est meilleure point final.

[Nadine]

et l'avantage avec l'algo A* c'est que tu ne traites pas nécessairement toutes les données du problème alors que Disktra traite toutes les données

Conclusion A* est optimal!!

[Matthieu Brucher]

Sauf que le pire des cas arrive fréquemment dans un jeu, et là ça peut ramer comme un rat mort.

[TanEk]

et l'avantage avec l'algo A* c'est que tu ne traites pas nécessairement toutes les données du problème alors que Disktra traite toutes les données

Ce n'est pas vrai, si le noeud d'arrivé est distant de N du noeud de départ, dijkstra va parcourir tous les noeuds d'une distance inférieure à N du noeud de départ. S'il existe des noeuds d'une distance supérieure à N, dijkstra ne les parcourra pas. MAIS A* ne parcourt pas forcément tous les noeuds d'une distance inférieure à N (sauf dans le pire des cas).

Sauf que le pire des cas arrive fréquemment dans un jeu, et là ça peut ramer comme un rat mort.

Je pense que c'est très peu fréquent pour le problème du plus court chemin dans les jeux vidéos et même quasi inexistant (sauf peut-être dans les labyrinthes et encore...).

[BugFactory]

Du moment qu'une heuristique donne de meilleurs résultats "statistiquement" (j'entends par là dans la plupart des cas), qu'elle soit "fausse" ou "vraie" n'a aucune importance, elle est meilleure point final.

Attention, l'heuristique doit toujours sous-estimer ou égaler la distance réelle faute de quoi on ne trouve pas un chemin optimal.

[panda31]

et IDA* ? J'ai travaillé sur un projet de jeu SOKOBAN et pour ma part, mon travail consistait à l'implémentation de A* et un autre groupe était chargé de l'algorithme IDA*, son concurrent. D'après tout ce que j'ai vu dessus, il est plus adapté à de gros volumes de données que A* qui grossit très vite.