Changes between Version 8 and Version 9 of CaoCourseTme9

Timestamp:

May 9, 2007, 6:43:38 AM (18 years ago)

Author:

franck

Comment:

--

CaoCourseTme9

@@ -23 +23 @@
 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.
-
 = B)  Algorithme de LEE et algorithme A* =
+
+Il y a différentes façons de faire évoluer la frontière entre la zone connue et la zone inconnue, 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.
+
+== B1) Algorithme de Lee ==
 
 Publié en 1961 (C. Y. Lee, "An algorithm for path connection and its application", IRE Trans. Electronic Computer, EC-10, 1961) cet algorithme permet de trouver de façon certaine le chemin le plus court ente deux points, mais il est coûteux en temps de calcul. Il consiste à faire grossir la zone connue de façon isotrope, dans toutes les directions autour du point S. Plus précisément, cet algorithme garantit que tous les points situés à une distance D du point source S auront été calculés avant de commencer à calculer les points situés à une distance D+1. 
@@ -54 +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 ».
 
+== B2) Algorithme A* ==
 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.