On se donne un nuage de point :

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

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.

On peut utiliser matplotlib pour représenter la solution :

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()

Il sera utile de calculer la distance entre deux points :

def distance(A, B):
    '''
    A: paire x,y
    B: paire x,y
    renvoie la distance AB
    '''

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.

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.
    '''

et enfin la fonction principale :

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.
    '''

On reprend l'affichage précédent en ajoutant le tracé de la solution.

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()