Aller au contenu

Glouton, Livraisons à Manhattan

Un livreur new-yorkais organise sa tournée. Le quartier dans lequel il évolue est un quadrillage : toutes les rues suivent l'axe Nord ↔ Sud ou l'axe Est ↔ Ouest.

Les adresses de ses livraisons sont donc des couples de coordonnées, (2, 3) par exemple. La première coordonnée est l'abscisse du point, la seconde son ordonnée.

Ces adresses de livraison sont données dans une liste python. Par exemple :

Python
1
clients = [(1, 3), (2, 2), (4, 2), (4, 1), (5,0)]

Ce qui correspond à la carte ci-dessous :

La carte

Afin de déterminer son itinéraire, il décide de toujours livrer en priorité l'adresse la plus « proche » de sa position actuelle. Se déplaçant le long des rues, il mesure la distance \(AB\) entre deux points de coordonnées \((x_A\,; y_A)\) et \((x_B\,; y_B)\)

Fonctions à compmléter⚓︎

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def distance_manhattan(p1: tuple, p2: tuple) -> int:
    '''
    Renvoie la distance de Manhattan entre p1 et p2
    '''
    x1,y1 = p1 # dépaquetage de p1
    x2,y2 = p2
    return ...

def le_plus_proche(p:tuple, clients: list)-> tuple:
    '''
    Renvoie l'indice du client étant à la distance la plus proche de p (point où on se trouve)
    '''
    dmin = distance_manhattan(p,clients[0]) # distance 1er client
    cproche = 0
    for i in range(1,len(clients)):
        if distance_manhattan(....) < ... :
            dmin = ...
            cproche = ...
    return cproche # retourne l'indice du plus proche

Algorithme glouton⚓︎

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def tournee(depart: tuple, clients: list) -> list:
    '''
    Retourne une liste ordonnée des clients choisis avec un algorithme glouton
    A chaque étape, on choisit le plus proche du point où l'on se trouve
    et le client est retiré de la liste
    '''
    tour = [] # pour insérer les clients dans l'ordre
    p = ... # p est le point où on se trouve
    while len(clients) > 0: # tant qu'il reste des clients à livrer
        indp = .. # trouve le plus proche, c'est son indice qui est retourné par le_plus_proche
        p = clients[indp]    # met à jour p
        ...    # l'ajoute  tour
        ...    # le retire de la liste des clients, en utilisant pop(indice)

Calcul de la distance totale⚓︎

Enfin, on peut calculer la distance totale de la tournée, somme de la distance du depart au premier point, des distances entre deux poinst consécutifs de la tournée et enfin du dernier point au départ.

Python
1
2
3
4
5
6
7
8
9
def distance_totale(depart: tuple, tour: list) -> int:
    '''
    retourne la disatnance totale depart -> tour -> depart
    '''
    distance = distance_manhattan(depart, tour[0])
    distance += ... # ajouts de la somme des distances entre deux points consecutifs
    distance += ... # retour au départ

    return distance