Changes between Version 2 and Version 3 of CaoCourseTme9
- Timestamp:
- Apr 23, 2007, 10:00:14 AM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme9
v2 v3 9 9 On cherche 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. En conséquence pour mesurer la distance, on utilisera donc une distance de Manhattan. 10 10 11 = A1) Représentation de l'espace=11 == A1) Représentation de l'espace == 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. … … 21 21 Le tableau DS[x,y] est un tableau d’entiers. La valeur contenue dans une case P(X,Y) de ce tableau contient en principe la distance DS(P) entre la source S et le point P, et la fonction principale de l’algorithme consiste à calculer ces distances DS(P). Au début de l’algorithme, ces distances sont donc inconnues, et toutes les cases du tableaux ne contenant pas d’obstacle sont initialisées à une valeur « infinie » (en pratique VIDE=MAXINT). La case S est initialisée à la valeur 0. On représente le fait qu’une case Z contient un obstacle, en initialisant DS(Z) avec la valeur OBSTABLE=-1. 22 22 23 = A2) Principe général de l’algorithme=23 == A2) Principe général de l’algorithme == 24 24 25 25 La méthode générale consiste à calculer progressivement les distances DS(P), en commençant par les points au voisinage de S, puis en élargissant peu à peu la zone autour de S dans laquelle les distances ont été calculées. Cette zone ''connue'' grossit peu à peu jusqu’à atteindre le point T. A un instant donné, il existe donc une zone connexe (autour du point S) regroupant les points pour lesquels la distance DS est connue est une autre zone (contenant le point T) regroupant les points pour lesquels la distance est DS est inconnue. Ces deux zones sont séparées par une ''frontière'', qui contient les points dont la distance DS est connue, mais qui peuvent avoir des voisins dont la distance DS n’a pas encore été calculée. Cette frontière constitue le périmètre de la zone connue, et évolue au cours de l’algorithme. Pour représenter cette frontière, on utilise une structure de donnée FRONTIER, qui est une liste chaînée ordonnée et dynamique, contenant les points P(X,Y) appartenant à la frontière à un instant donné. … … 89 89 90 90 91 = D1) Gestion du tableau (cf. xmaze.h)=91 == D1) Gestion du tableau (cf. xmaze.h) == 92 92 93 93 Le tableau est géré par une bibliothèque de fonctions graphiques, qui va se charger de l'initialisation (étape0) et de l'affichage du tableau dans une fenêtre X11. Seules quelques fonctions sont externalisées pour pouvoir être utilisées par les fonctions de routage … … 121 121 Cette fonction affiche sur la fenêtre X11, l'état du tableau DS. Les cases VIDE (valeur=MAXINT) sont affichées en noir. Les cases OBSTACLE (valeur=-1) sont affichées en rouge. Les cases CHEMIN (valeur=-2) sont affichées en jaune. Les cases positives (mais non VIDE) sont affichées en bleu. 122 122 123 = D2) Algorithme de Lee (cf. maze.h)=123 == D2) Algorithme de Lee (cf. maze.h) == 124 124 {{{ 125 125 typedef struct boundlee_t … … 168 168 169 169 170 = D3) Algorithme A*=170 == D3) Algorithme A* == 171 171 {{{ 172 172 typedef struct boundastar_t … … 230 230 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 les fichiers objets fournis par vos propres fichiers objets. 231 231 232 = E1) réécrire la fonction expandlee() = 233 234 = E2) réécrire les fonctions add_boundlee()=235 236 = E3) réécrire la fonction findpath()=237 238 = E4) réécrire la fonction expandastar()=239 240 = E5) réécrire les foncions add_boundastar()=232 = E1) réécrire la fonction expandlee() == 233 234 == E2) réécrire les fonctions add_boundlee() == 235 236 == E3) réécrire la fonction findpath() == 237 238 == E4) réécrire la fonction expandastar() == 239 240 == E5) réécrire les foncions add_boundastar() ==
