README : Algorithmes de Dijkstra et A*
Introduction
Ce projet explore les algorithmes de Dijkstra et A*, deux méthodes clés pour la recherche de chemins optimaux dans des graphes pondérés. En partant de Dijkstra, étudié en R2.07, nous approfondissons avec l'algorithme A*, une amélioration qui intègre une heuristique pour une recherche plus rapide dans certaines situations.
Objectifs
- Comprendre l'algorithme de Dijkstra : Analyser ses bases et identifier ses limites pour des cas pratiques.
- Découvrir l'algorithme A* : Voir comment l'ajout d'une heuristique permet de réduire le nombre de nœuds à explorer et d'optimiser le temps de recherche.
- Étudier des applications concrètes dans différents domaines :
- Navigation GPS et applications de cartographie (Waze, Google Maps) : Calculs d'itinéraires optimisés en temps réel.
- Jeux vidéo : A* est utilisé pour la navigation de personnages dans des environnements complexes avec obstacles.
- Réseaux informatiques : Pour optimiser la transmission des données en trouvant les routes les plus efficaces.
Modélisation avec Unity
Pour visualiser ces algorithmes, nous utilisons Unity afin de modéliser des exemples interactifs. Cette modélisation permet d'illustrer le comportement des algorithmes dans des environnements similaires à ceux des applications GPS ou des jeux vidéo.
Structure du projet
Ce projet comprend :
- Documentation et Implémentations de Dijkstra et A* en Python et Markdown dans un Jupyter Notebook,
- Scène Unity pour une visualisation interactive,