Différences

Ci-dessous, les différences entre deux révisions de la page.

--- itc:tps:tp5:chemin_plus_court [2022/01/18 12:23] – goupillwiki
+++ itc:tps:tp5:chemin_plus_court [2022/01/18 22:13] (Version actuelle) – goupillwiki
@@ Ligne 4: / Ligne 4: @@
 <code python>
-nuage = [(43, 63), (26, 71), (94, 31), (16, 0), (54, 79), (80, 37), (8, 21), (99, 18), (23, 77), (15, 52), (65, 86), (4, 40), (58, 18), (3, 8), (80, 26), (83, 35), (34, 88), (71, 84), (59, 66), (41, 36), (0, 99), (34, 6), (9, 15), (48, 42), (46, 91), (68, 36), (30, 21), (15, 29), (82, 15), (2, 94), (66, 17), (13, 1), (85, 14), (6, 23), (60, 73), (1, 27), (55, 98), (18, 14), (41, 76), (97, 56), (54, 73), (61, 75), (22, 43), (87, 73), (97, 40), (92, 76), (73, 98), (41, 31), (51, 9), (35, 89)]
+nuage = [(43, 63), (26, 71), (94, 31), (16, 0), (54, 79), (80, 37),
+         (8, 21), (99, 18), (23, 77), (15, 52), (65, 86), (4, 40),
+         (58, 18), (3, 8), (80, 26), (83, 35), (34, 88), (71, 84),
+         (59, 66), (41, 36), (0, 99), (34, 6), (9, 15), (48, 42),
+         (46, 91), (68, 36), (30, 21), (15, 29), (82, 15), (2, 94),
+         (66, 17), (13, 1), (85, 14), (6, 23), (60, 73), (1, 27),
+         (55, 98), (18, 14), (41, 76), (97, 56), (54, 73), (61, 75),
+         (22, 43), (87, 73), (97, 40), (92, 76), (73, 98), (41, 31),
+         (51, 9), (35, 89)]
 </code>
@@ Ligne 11: / Ligne 19: @@
 Recherchez une méthode par algorithme glouton. La réponse devra être une liste comme celle ci-dessus mais ordonnée selon l'ordre du parcours choisi.
-===== Représenter la solution =====
+===== Représenter la nuage =====
 On peut utiliser ''matplotlib'' pour représenter la solution :
@@ Ligne 18: / Ligne 26: @@
 import matplotlib.pyplot as plt
-X, Y = zip(*solution)
+X, Y = zip(*nuage)
 plt.scatter(X,Y, c='b') # nuage de points bleus
-X.insert(0,0) # pour ajouter le départ en (0,0)
-Y.insert(0,0)
-plt.plot(X,Y,'r') # le parcours en rouge
 plt.axis('equal') # orthonormé
 plt.show()
 </code>
+===== Quelques pistes =====
+Il sera utile de calculer la distance entre deux points :
+<code python>
+def distance(A, B):
+    '''
+    A: paire x,y
+    B: paire x,y
+    renvoie la distance AB
+    '''
+</code>
+considérant un point de référence ''%%ou_je_suis%%'' et un une liste ''%%points%'', il sera utile de trouver le point le plus proche parmi les ''%%points%%'', et d'extraire ce point de la liste.
+<code python>
+def extraire_plus_proche(points, ou_je_suis):
+    '''
+    points: liste de paires x,y. Représentent des points du plan.
+    ou_je_suis: paire x,y. Le point où on se trouve maintenant.
+    recherche dans la liste points, le point le plus proche de ou_je_suis
+    extrait ce point de la liste et le renvoie.
+    '''
+</code>
+et enfin la fonction principale :
+<code python>
+def plus_court_chemin(nuage, depart):
+    '''
+    nuage: liste des x,y  des points du nuage
+    depart: x, y du point de départ
+    cherche, en utilisant l'algorithme glouton, le plus court chemin partant de depart
+    et passant une fois par chaque point du nuage
+    renvoie ce chemin sous forme d'une liste de points.
+    '''
+</code>
+===== Affichage du nuage et de la solution ======
+On reprend l'affichage précédent en ajoutant le tracé de la solution.
+<code python>
+import matplotlib.pyplot as plt
+X, Y = zip(*nuage)
+plt.scatter(X,Y, c='b') # nuage de points bleus
+chemin = plus_court_chemin(nuage, (0,0))
+X, Y = zip(*chemin)
+plt.plot(X, Y, 'b')
+plt.axis('equal') # orthonormé
+plt.show()
+</code>