On considère une liste de points dont les coordonnées sont données.

Par exemple A(0;0), B(3;2), C(18;11)… X(100,100).

• On part toujours du premier de ces points (ici A),
• on cherche à atteindre le dernier point (ici X),
• entre deux points, la distance est calculée de façon habituelle :

$$d_{BC} = \sqrt{(x_C - x_B)^2 + (y_C - y_B)^2} \approx 17,49$$

• on ne passe pas deux fois par un même point,
• d'un point donné on a le droit d'atteindre tous ceux, non visités, à une distance inférieure à L (paramètre à définir)

On cherche à effectuer le trajet en totalisant une distance minimale.

On vous fournit un tableau de coordonnées. Par exemple :

coords = [(0,0), (40, 41), (16, 58), (0, 32), (30, 90), (29, 76), (88, 47), (17, 60), (54, 7), (24, 34), (55, 97), (62, 24), (80, 23), (11, 40), (78, 64), (4, 1), (35, 40), (19, 45), (69, 93), (0, 52), (58, 32), (100,100)]

On pourra aussi fournir les coordonnées sous forme d'un fichier comme coords.csv.

• On note le point à atteindre, Dest, qui est le dernier point,
• on part du premier point,
• et pour les pas suivant,
  • on cherche les points non visités à une distance inférieure à L,
  • parmi ceux-là, on sélectionne celui qui est le plus proche de Dest

Un premier module de fonctions

# glouton.py

from math import sqrt

def distance(p1, p2)->float:
    """
    p1: paire (x1, y1)
    p2: paire (x2, y2)
    renvoie la distance de p1 à p2
    """
    # à compléter

def glouton(coords, L:float):
    """
    coords: liste de coordonnées (x,y)
    L: longueur de saut maximal
    renvoie une liste de coordonnées du parcours glouton et sa longueur
    Si le chemin trouvé n'aboutit pas, renvoie chemin, -1
    parcours glouton : du premier au dernier point de coords,
      en sautant vers le plus proche de l'arrivée, par saut < L
      sans passer 2x au même endroit
    """
    
def coords_from_file(filename:str):
    """
    filename: nom de fichier
    renvoie la liste de coordonnées (x:int,y:int) contenues dans le fichier
    """

Un script de démonstration

# demo1.py

import matplotlib.pypplot as plt
from glouton import glouton

coords = [(0,0), (40, 41), (16, 58), (0, 32), (30, 90), (29, 76), (88, 47), (17, 60), (54, 7), (24, 34), (55, 97), (62, 24), (80, 23), (11, 40), (78, 64), (4, 1), (35, 40), (19, 45), (69, 93), (0, 52), (58, 32), (100,100)]

# ajouter l'exécution du code glouton avec L = 20
# puis l'affichage de tous les points avec matplotlib
# et l'affichage du parcours obtenu

Et une autre démonstration

# demo2.py

import matplotlib.pypplot as plt
import glouton

coords = glouton.coords_from_file('coords.csv')

# exécution de l'algo glouton avec L = 20
# affichage comme dans le précédent