Changes between Version 4 and Version 5 of CaoCourseTme9

Timestamp:

Apr 26, 2007, 10:46:12 AM (18 years ago)

Author:

alain

Comment:

--

CaoCourseTme9

@@ -5 +5 @@
 [[PageOutline]]
 
-= A) Objectif =
+= Objectif =
 
 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. 
 
-== A1) Représentation de l'espace ==
+= Principe Général =
 
 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 (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.
 
-== A2) Principe général de l’algorithme ==
-
-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é. 
+Le principe général de l’algorithme 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é. 
 
 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.
@@ -226 +224 @@
 = D)  Travail à effectuer =
 
+Créez un répertoire de travail '''tme9''', et copiez dans ce répertoire tous les fichiers et répertoires qui se trouvent dans
+{{{
+/users/enseig/encadr/cao/tme9
+}}}
+
+
+
 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.
 
@@ -237 +242 @@
 
 == D5) réécrire les foncions add_boundastar() ==
+
+= Compte-Rendu =
+
+Il ne vous est pas demandé de compte-rendu écrit pour ce TME, mais vous devrez faire une démonstration
+de votre code au début du prochain TME.
+