Table des matières
Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Analyse du Contexte et Cahier des Charges . . . . . . . . . 4
1.1 Contexte du projet . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Objectifs du projet . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Organisation du rapport . . . . . . . . . . . . . . . . . . . . . 4
2 Fondements théoriques . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Fondements théoriques . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Notions de base sur les graphes . . . . . . . . . . . . . . . . . 5
2.3 Présentation de l’algorithme A* . . . . . . . . . . . . . . . . . 5
2.4 Comparaison avec d’autres algorithmes . . . . . . . . . . . . . 5
3 Étude et conception . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1 Analyse des besoins (diagramme de use case) . . . . . . . . . . 6
3.2 Choix des structures de données . . . . . . . . . . . . . . . . . 6
3.3 Présentation de l’algorithme A* . . . . . . . . . . . . . . . . . 6
3.4 Conception de l’architecture logicielle (diagramme de classes
et de séquence) . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Implémentation de l’algorithme A* . . . . . . . . . . . . . . 7
4.1 Développement en Python . . . . . . . . . . . . . . . . . . . . 7
4.2 Tests sur des graphes simples . . . . . . . . . . . . . . . . . . 7
4.3 Gestion des pondérations et directions . . . . . . . . . . . . . 7
5 Visualisation et interface utilisateur . . . . . . . . . . . . . . 8
5.1 Choix des bibliothèques graphiques . . . . . . . . . . . . . . . 8
5.2 Intégration de la bibliothèque Tkinter . . . . . . . . . . . . . . 8
5.3 Résultats et exemples visuels . . . . . . . . . . . . . . . . . . . 8
Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . 9
1
Annexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2
Introduction générale
L’algorithme A* (prononcé « A étoile ») est un algorithme de recherche
de chemin largement utilisé en informatique, et plus particulièrement dans le
domaine de l’intelligence artificielle. Son rôle principal est de trouver le che-
min le plus court entre un nœud initial et un nœud final dans un graphe, tout
en optimisant les ressources et le temps de calcul. Cet algorithme combine les
avantages de la recherche en largeur et de la recherche informée grâce à une
fonction d’évaluation heuristique, ce qui lui permet d’être à la fois efficace et
performant.
Le choix de ce sujet s’inscrit dans la volonté d’approfondir les concepts
fondamentaux des algorithmes de recherche et leur application pratique dans
le traitement de problèmes complexes. En effet, l’algorithme A* est un exemple
emblématique d’algorithme de planification, utilisé dans de nombreux do-
maines tels que la robotique, la navigation, les jeux vidéo, et la modélisation
de réseaux. Son importance réside dans sa capacité à gérer des graphes orien-
tés avec des poids positifs tout en garantissant un résultat optimal lorsqu’une
heuristique admissible est utilisée.
L’objectif du projet est d’étudier l’algorithme A* en théorie et de le pro-
grammer en Python pour résoudre le plus court chemin sur des graphes
complexes, avec une interface visuelle montrant les graphes et les chemins
trouvés.
En résumé, ce projet ambitionne de fournir à la fois une base théorique
solide et une application concrète de l’algorithme A*, mettant en lumière son
utilité et ses performances dans le domaine de la recherche de chemin.
/////////////////
3
Chapitre 1
Analyse du Contexte et Cahier
des Charges
1.1 Contexte du projet
1.2 Problématique
1.3 Objectifs du projet
1.4 Organisation du rapport
4
Chapitre 2
Fondements théoriques
2.1 Fondements théoriques
2.2 Notions de base sur les graphes
2.3 Présentation de l’algorithme A*
2.4 Comparaison avec d’autres algorithmes
5
Chapitre 3
Étude et conception
3.1 Analyse des besoins (diagramme de use case)
3.2 Choix des structures de données
3.3 Présentation de l’algorithme A*
3.4 Conception de l’architecture logicielle (dia-
gramme de classes et de séquence)
6
Chapitre 4
Implémentation de l’algorithme
A*
4.1 Développement en Python
4.2 Tests sur des graphes simples
4.3 Gestion des pondérations et directions
7
Chapitre 5
Visualisation et interface
utilisateur
5.1 Choix des bibliothèques graphiques
5.2 Intégration de la bibliothèque Tkinter
5.3 Résultats et exemples visuels
8
Conclusion générale
9
Annexe
10