| 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. |
| | 21 | Le tableau DS[X,Y] est un tableau d’entiers. La valeur contenue dans une case (X,Y) de ce tableau contient en principe la distance DS(P) entre la source S et le point P de coordonnées (X,Y). 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 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 -1. |
| 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 |
| 26 | | |
| 27 | | Il y a différentes façons de faire évoluer cette frontière, correspondant à différentes stratégies d’exploration de l’espace autour de S, et nous étudierons |
| 28 | | |
| 29 | | = B) Algorithme LEE Maze = |
| | 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 tous les points P(X,Y) appartenant à la frontière à un instant donné. |
| | 26 | |
| | 27 | Il y a différentes façons de faire évoluer cette frontière, correspondant à différentes stratégies d’exploration de l’espace autour de S, et nous étudierons successivement deux algorithmes dans le cadre de ce TME. |
| | 28 | |
| | 29 | = B) Algorithme de LEE et algorithme A* = |
| 35 | | Étape 0 (initialisation) : |
| 36 | | |
| 37 | | On initialise toutes les cases du tableau DS[x,y] à la valeur VIDE=MAXINT, sauf les cases contenant un obstacle, qui prennent la valeur OBSTACLE=-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. |
| 38 | | |
| 39 | | Étape 1 (expansion) : |
| | 35 | '''Etape initialisation :''' |
| | 36 | |
| | 37 | 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. |
| | 38 | |
| | 39 | '''Etape expansion) :''' |
| 54 | | Étape 2 (retour) |
| 55 | | |
| 56 | | 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 CHEMIN=-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 ». |
| 57 | | |
| 58 | | = C) Algorithme A* = |
| 59 | | |
| 60 | | L'algorithme A* (prononcer A-star) est une variante de l’algorithme de Lee. Il est beaucoup plus rapide, car on ne déplace plus la frontière de façon isotrope dans toutes les directions, mais, on essaie de calculer en priorité les points qui permettent de se rapprocher de la destination T (la frontière est « attirée » par la destination T). Il y a un prix à payer : La conséquence de cette optimisation est que la solution trouvée n’est pas toujours optimale. |
| 61 | | |
| 62 | | L’algorithme A* travaille également en trois phases. Les deux phases d’initialisation et de retour sont inchangées. Seule la phase d’expansion est légèrement modifiée. |
| 63 | | |
| 64 | | Pour cela on définit, pour chaque point de la frontière la quantité COUT(P), qui est une estimation optimiste de la distance entre S et T, si on passe par le point P : |
| | 54 | '''Etape retour :''' |
| | 55 | |
| | 56 | 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 ». |
| | 57 | |
| | 58 | L'algorithme A* (prononcer A-star) est une variante de l’algorithme de Lee. Il est beaucoup plus rapide, car on ne déplace plus la frontière de façon isotrope dans toutes les directions, mais, on essaie de calculer en priorité les points qui permettent de se rapprocher de la destination T (la frontière est « attirée » par la destination T). Il y a un prix à payer pour cette optimisation : la solution trouvée n’est pas toujours optimale. L’algorithme A* travaille également en trois phases. Les deux phases d’initialisation et de retour sont inchangées. Seule la phase d’expansion est légèrement modifiée. |
| | 59 | |
| | 60 | Pour cela on définit, pour chaque point P de la frontière la quantité COUT(P), qui est une estimation optimiste de la distance entre S et T, si on passe par le point P : |
| 88 | | = D) Structures de données et fonctions d’accès = |
| 89 | | |
| 90 | | |
| 91 | | == D1) Gestion du tableau (cf. xmaze.h) == |
| 92 | | |
| 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 |
| | 84 | = C) Structures de données et fonctions d’accès = |
| | 85 | |
| | 86 | |
| | 87 | == C1) Gestion du tableau == |
| | 88 | |
| | 89 | Le tableau est géré par une bibliothèque de fonctions graphiques (cf. xmaze.h), qui va se charger de l'initialisation 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 |
| 228 | | = E) Travail à effectuer = |
| 229 | | |
| 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 |
| 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() == |
| | 226 | = D) Travail à effectuer = |
| | 227 | |
| | 228 | 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. |
| | 229 | |
| | 230 | == D1) réécrire la fonction expandlee() == |
| | 231 | |
| | 232 | == D2) réécrire les fonctions add_boundlee() == |
| | 233 | |
| | 234 | == D3) réécrire la fonction findpath() == |
| | 235 | |
| | 236 | == D4) réécrire la fonction expandastar() == |
| | 237 | |
| | 238 | == D5) réécrire les foncions add_boundastar() == |
