Changes between Version 5 and Version 6 of CaoCourseTme9
- Timestamp:
- Apr 26, 2007, 10:52:36 AM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme9
v5 v6 9 9 Le but de ce TME est de programmer, en langage C, l'algorithme de routage A*. Cet algorithme recherche le chemin le plus court entre deux points (un point source et un point destination) dans un espace à deux dimensions contenant des obstacles qu'il faut contourner. L'espace est discrétisé afin de travailler sur des coordonnées entières. Un chemin est constitué de segments de droites. On contraint ces segments à être parallèles aux axes des abscisses et des ordonnées. On utilisera donc une distance de Manhattan. 10 10 11 = Principe Général =11 = A) Principe Général = 12 12 13 13 L'espace est représenté par un tableau à deux dimensions DS[X,Y]. Ce tableau est indexé par deux index (X,Y) représentant les coordonnées, et chaque case correspond donc à une position dans le plan. … … 31 31 Cet algorithme travaille en trois étapes phases : une phase d’initialisation, une phase d'expansion, consistant à faire grossir la zone connue en stockant les résultats dans les tableaux DS[x,y], et une phase de retour, où on calcule effectivement le chemin le plus court pour revenir de T à S, en utilisant le tableau DS[x,y]. 32 32 33 '''Etape initialisation :'''33 '''Etape initialisation pour LEE :''' 34 34 35 35 On initialise toutes les cases du tableau DS[x,y] à la valeur MAXINT, sauf les cases contenant un obstacle, qui prennent la valeur -1, et la case S, qui prend la valeur 0. On initialise la liste ordonnée FRONTIER qui ne contient que le point source S. 36 36 37 '''Etape expansion ):'''37 '''Etape expansion pour LEE :''' 38 38 {{{ 39 39 TANTQUE DS(T)==MAXINT … … 50 50 }}} 51 51 52 '''Etape retour :'''52 '''Etape retour pour LEE :''' 53 53 54 54 On reconstruit le chemin, de la cible T vers la source S, en recherchant pour chaque point P situé à une distance D un voisin situé à une distance (D-1). On place à chaque position faisant parti du chemin, le code -2. Il peut y avoir plusieurs solutions. Toutes les solutions sont équivalentes pour ce qui concerne la distance. Le choix d'une solution particulière peut être guidée par des contraintes du genre « éviter les changements de directions ». … … 229 229 }}} 230 230 231 232 233 Le code source et les fichiers objets de ce TME sont dans le répertoire cao/tme9. Vous y trouverez un Makefile permettant de générer un exécutable nommé xlee fonctionnel. Avec cet exécutable, vous pouvez créer un labyrinthe, choisir un point source, un point cible, et demander le calcul du chemin en utilisant l'algorithme de LEE ou de Astar. Vous allez devoir remplacer progressivement les fichiers objets fournis par vos propres fichiers objets. 231 Le Makefile fourni permet de générer un exécutable nommé xlee fonctionnel. Avec cet exécutable, vous pouvez créer un labyrinthe, choisir un point source, un point cible, et demander le calcul du chemin en utilisant l'algorithme de LEE ou de Astar. Vous allez devoir remplacer progressivement les fichiers objets fournis par vos propres fichiers objets. 234 232 235 233 == D1) réécrire la fonction expandlee() ==
