GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Chemin le plus court ======

On se donne un nuage de point :

<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)]
</code>

On cherche le chemin le plus court partant de ''(0,0)'' et passant exactement une fois par tous les points.

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 nuage =====

On peut utiliser ''matplotlib'' pour représenter la solution :

<code python>
import matplotlib.pyplot as plt

X, Y = zip(*nuage)

plt.scatter(X,Y, c='b') # nuage de points bleus

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>