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

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