Voyageur de commerce

La distance

On souhaite rédiger un algorithme glouton pour résoudre le problème du voyageur de commerce. Pour cela, on doit comprendre le fonctionnement des tableaux à deux dimensions.

Si vous ne savez pas ce qu'est une liste à deux dimensions, réalisez cet exercice.

On utilisera donc une liste de listes sous la forme distances[ville1][ville2] pour connaître la distance de ville1 à ville2, tous deux des entiers de 0 à n exclu. On déduit rapidement que distances[ville1][ville2] et distances[ville2][ville1] ont la même valeur.

Dans l'exemple ci-dessous, on obtient :

1
villes = ["A", "B", "C", "D"]  # Donc n = 4
2
distances = [[0, 4, 3, 1],
3
             [4, 0, 1, 2],
4
             [3, 1, 0, 5],
5
             [1, 2, 5, 0]]
Instance du problèmeInformations[1]

Question

À l'aide du tableau des distances donné en introduction, rédiger le contenu des variables villes et distances associées.

La ville la plus proche

On cherche désormais à connaître la ville la plus proche d'une ville donnée, connaissant les villes déjà visitées ou non.

Pour chaque ville non visitée, on doit regarder sa distance avec la ville actuelle, et renvoyer la ville la plus proche trouvée.

Afin de connaître les villes déjà visitées, on dispose d'une liste de booléens qui associe à chaque ville une valeur True si elle a déjà été visitée et False sinon.

Par exemple, si visitees = [True, False, True, False, False], alors les villes numérotées 1, 3 et 4 peuvent être la prochaine destination.

Question

Compléter la fonction plus_proche(ville, distances, visitees) qui renvoie le numéro de la prochaine ville à visiter.

  • ville est un entier indiquant la ville actuelle.

  • distances est une liste de listes comme défini plus haut.

  • visitees est une liste indiquant si une ville a été visitée ou non. On suppose que visitees[ville] vaut True.

N'oubliez pas de rédiger les docstrings de votre fonction, avec un exemple simple vu en cours.

1
def plus_proche(ville, distances, visitees):
2
    # On règle un cas de base où la distance est très grande
3
    ville_plus_proche = -1
4
    distance_plus_proche = 10000000
5
6
    n = len(visitees)
7
    
8
    # On regarde parmi toutes les villes
9
    for une_ville in range(n):
10
        # Si cette ville n'est PAS déjà visitée
11
        if not ...... :
12
            distance_entre_villes = distances[.....][.....]
13
            # Si cette distance est plus petite que celle enregistrée
14
            if ..... < ..... :
15
                # On met à jour le meilleur résultat.
16
                ville_plus_proche = .....
17
                distance_plus_proche = .....
18
19
    # On renvoie la ville la plus proche
20
    return ville_plus_proche
L'algo final
Il ne reste plus qu'à appliquer le principe de l'algorithme glouton vu en cours.
Question
Compléter la fonction voyageur_glouton(villes, distances, depart) ci-dessous :
1
def voyageur_glouton(villes, distances, depart):
2
    """
3
    Doc-string à compléter avec l'exemple vu en cours
4
    """
5
    n = .....
6
    visitees = [False] * n  # Permet de créer une liste contenant n fois la valeur False
7
    courante = .....  # Ville qu'on est en train de visiter (ville de départ au début)
8
    visitees[.....] = True
9
    chemin = [.....]  # Chemin de visite final
10
11
    while False in visitees:
12
        suivante = plus_proche(.....)
13
        courante = .....  # La nouvelle ville courante
14
        chemin.append(.....)
15
        visitees[.....] = True
16
17
    chemin.append(.....)
18
    return .....
Question
Pour les plus rapides :
  • Afficher le résultat sous forme de texte, et en calculant la distance parcourue.
  • Testez votre fonction avec d'autres valeurs.
  • Rédiger un algorithme qui teste tous les chemins possibles, et mesurer son temps d'exécution. Le comparer à l'algorithme glouton.