Changes between Version 7 and Version 8 of CaoCourseTme9

Timestamp:

May 9, 2007, 6:31:08 AM (18 years ago)

Author:

franck

Comment:

--

CaoCourseTme9

@@ -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.
 
-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é. 
+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 et 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.