Le problème du voyageur de commerce

Temps de lecture10 min

En bref

Résumé de l’article

Dans cet article, vous découvrirez un problème célèbre en informatique, appelé le « problème du voyageur de commerce » (ou « Traveling Salesperson Problem », TSP). Ce problème consiste à déterminer dans quel ordre parcourir tous les sommets d’un graphe complet en minimisant la distance totale. Ce problème a de nombreuses applications pratiques… mais il est difficile à résoudre !

Points clés à retenir

  • Le TSP est le problème de trouver le chemin le plus court qui passe par tous les sommets d’un graphe.

  • Il est connu pour être un problème très difficile : sa version de décision est NP-complète.

  • Le TSP peut être utilisé pour prouver que d’autres problèmes sont au moins aussi complexes, grâce à une technique appelée « réduction ».

Contenu de l’article

Vidéo

Veuillez consulter la vidéo ci-dessous (en anglais, affichez les sous-titres si besoin). Nous fournissons également une traduction du contenu de la vidéo juste après, si vous préférez.

Information
Cliquez ici pour afficher la traduction de la vidéo.

Bonjour, et bienvenue dans cette leçon sur l’algorithmique et les mathématiques discrètes !

Dans le cours d’aujourd’hui, vous allez découvrir le problème du voyageur de commerce, qui est probablement l’un des problèmes les plus connus en informatique. Il est également souvent utilisé comme premier exemple de problème NP-complet, ce qui signifie que nous n’avons pas encore identifié d’algorithme de résolution rapide.

Le problème du voyageur de commerce

Commençons par quelques définitions de base : étant donné un ensemble de villes et le coût de déplacement entre chaque paire de villes, le problème du voyageur de commerce, ou TSP en abrégé, consiste à trouver le moyen le moins coûteux de visiter toutes les villes et, éventuellement, de revenir au point de départ.

Les problèmes comme le TSP sont appelés “problèmes d’optimisation”, car l’objectif est de trouver des paramètres qui optimisent une certaine quantité, qui, dans le cas du TSP, est de minimiser le coût total.

Le TSP peut être représenté par un graphe pondéré, où les sommets représentent les villes, et les poids sur les arêtes représentent le coût de déplacement entre les paires de villes. Résoudre le TSP revient à trouver un chemin passant une et une seule fois par tous les sommets du graphe et ayant un poids total minimal.

Exemple

Prenons un exemple. Considérons le graphe suivant, où le point de départ est le sommet $v_1$. Supposons une situation où le voyageur n’a pas besoin de revenir au sommet initial.

Le chemin $( \{v_1,v_4\}, \{v_3,v_4\}, \{v_2,v_3\} )$ a un poids total de $3 + 1 + 8 = 12$. Ce chemin pourrait potentiellement être une solution du TSP.

Cependant, ce n’est pas une solution optimale, car nous pouvons trouver un chemin avec un poids plus faible.

Le chemin $( \{v_1,v_3\}, \{v_3,v_4\}, \{v_2,v_4\}) $ a un poids total de $4 + 1 + 2 = 7$, et c’est le chemin le plus court partant de $v_1$ et passant par tous les sommets du graphe. Ainsi, c’est la solution optimale du TSP pour ce graphe.

Le TSP dans les problèmes quotidiens

Le TSP est un problème récurrent dans de nombreux domaines de l’informatique. Voici quelques exemples.

Le TSP apparaît naturellement comme un sous-problème dans de nombreuses applications de transport et de logistique, comme, par exemple, la planification des itinéraires des bus scolaires pour récupérer les élèves à différents endroits. D’autres exemples modélisables comme des TSP incluent la planification des livraisons de repas à domicile et l’acheminement des camions postaux pour la collecte des colis.

Le TSP intervient également lorsqu’il s’agit de minimiser le temps et les coûts d’un voyage potentiellement long et coûteux. C’est le cas, par exemple, pour les satellites qui doivent passer par un certain nombre de lieux différents pour accomplir leurs missions.

Le déploiement de la fibre optique pose le problème de desservir un ensemble de lieux tout en limitant les travaux de construction nécessaires. Un tel problème peut généralement être formalisé comme un TSP.

La planification d’une machine pour percer des trous dans un objet lors d’un processus de fabrication peut également être vue comme un TSP. Les trous à percer sont les “villes”, et le coût de déplacement est le temps nécessaire pour déplacer la tête de perçage d’un trou à l’autre.

Le TSP comme réduction pour d'autres problèmes

En informatique, une réduction est une méthode permettant de transformer un problème en un autre problème, pour lequel des solutions sont déjà connues.

Intuitivement, le problème $P$ est réductible au problème $Q$ si un algorithme permettant de résoudre efficacement le problème $Q$ peut également être utilisé pour résoudre le problème $P$. En quelque sorte, cela signifie que lorsque vous résolvez le problème $Q$, une partie de ce que vous faites peut également être considérée comme la résolution du problème $P$.

Plus formellement, réduire un problème $P$ à un problème $Q$ se fait en trouvant deux algorithmes polynomiaux $alg_1$ et $alg_2$ tels que, si l’algorithme $alg_Q$ résout le problème $Q$, alors l’algorithme concaténé $ [alg_1, alg_Q, alg_2]$ résout le problème $P$.

Pour mieux comprendre la réduction, pensez à la traduction de langues. Imaginez que vous avez un moyen de résoudre un problème en français, mais que votre problème est exprimé en anglais. Une solution possible est de d’abord traduire votre problème en français, de le résoudre en français, puis de traduire la solution en anglais. C’est un exemple de réduction.

Continuons en anglais. Pas de français, promis !

La réduction est un moyen très pratique d’obtenir rapidement des résultats. Par exemple, la réduction peut être utilisée pour prouver qu’un problème peut être résolu par un algorithme donné, ou pour montrer qu’un problème est au moins aussi difficile qu’un autre.

En d’autres termes, si $P$ est réductible à $Q$, alors vous pouvez résoudre $P$ en utilisant un algorithme conçu pour résoudre $Q$.

Cela ne vous dit rien sur la capacité à résoudre $Q$ en utilisant un algorithme conçu pour résoudre $P$. Ainsi, nous pouvons seulement dire que $Q$ est au moins aussi difficile que $P$.

Le méta-graphe

Voyons maintenant comment le problème de ramasser tous les morceaux de fromage d’un labyrinthe se réduit au TSP.

Considérons ce labyrinthe, qui montre également son graphe associé.

Les morceaux de fromage sont représentés par des sommets jaunes. Notre position de départ est indiquée en rouge.

Il est facile de voir comment déterminer le chemin le plus court pour ramasser tous les morceaux de fromage revient en quelque sorte à résoudre un TSP. Cependant, si nous utilisons ce graphe pour résoudre le TSP, vous pouvez voir que nous passerons par de nombreux sommets parasites, qui ne contiennent pas de fromage. Nous aimerions ne passer que par les sommets contenant un morceau de fromage.

Nous proposons donc de transformer notre graphe en un nouveau graphe, que nous appelons le “méta-graphe”. Les sommets du méta-graphe sont la position de départ plus les morceaux de fromage. Le poids entre deux sommets dans le nouveau graphe correspond à la longueur d’un chemin le plus court entre les sommets correspondants dans le labyrinthe. Si nous faisons cela pour chaque paire de sommets colorés dans l’exemple précédent, nous obtenons un graphe complet avec sept sommets. Pour décider comment passer d’un sommet à un autre, un algorithme de routage doit être utilisé.

Nous pouvons maintenant résoudre le problème de trouver l’itinéraire le plus court pour ramasser tous les morceaux de fromage. Tout d’abord, nous construisons le méta-graphe. Ensuite, nous résolvons le TSP sur le méta-graphe. Enfin, nous utilisons le routage pour trouver les itinéraires correspondants dans le labyrinthe.

Ainsi, nous avons concaténé trois algorithmes, les premier et troisième étant polynomiaux, et prouvé que notre problème est réductible au TSP.

Conclusion

Dans la prochaine leçon, nous verrons comment coder une solution au TSP.

Combien de solutions possibles ?

Dans PyRat, le rat part d’une case fixée, et doit ramasser $k$ morceaux de fromage, sans revenir à son point de départ. Une solution est donc un ordre dans lequel ramasser les morceaux de fromage, et il y a $k!$ ordres possibles : $k$ choix pour le premier morceau, $k - 1$ pour le deuxième, etc.

Un algorithme qui essaie tous ces ordres doit donc en examiner :

Morceaux de fromage $k$ Nombre d’ordres $k!$ Temps à $10^9$ ordres par seconde
5 120 120 ns
10 3 628 800 3,6 ms
15 $1,3 \cdot 10^{12}$ 22 min
20 $2,4 \cdot 10^{18}$ 77 ans
21 (partie par défaut) $5,1 \cdot 10^{19}$ 1600 ans

Dans la variante où l’on revient au point de départ, un tour ne dépend pas du sommet par lequel on le commence, ni du sens dans lequel on le parcourt : il y a alors $\frac{(n-1)!}{2}$ tours différents pour $n$ villes. Cela ne change pas grand-chose à la croissance du nombre de solutions.

Pour aller plus loin

Les propriétés du méta-graphe

Son coût de construction

Le méta-graphe a $k + 1$ sommets (la position de départ et les morceaux de fromage). Pour calculer les poids de ses arêtes, il suffit de lancer un algorithme de Dijkstra depuis chacun de ces sommets, soit $k + 1$ parcours. Dans un labyrinthe à $n$ cases, chacun coûte $O(n \cdot log(n))$ (voir l’article sur l’algorithme de Dijkstra), donc la construction du méta-graphe coûte $O(k \cdot n \cdot log(n))$.

C’est une complexité polynomiale, négligeable devant celle de la résolution du TSP sur le méta-graphe. C’est d’ailleurs ce qui fait de cette transformation une réduction au sens de la vidéo.

L’inégalité triangulaire

Les poids du méta-graphe vérifient l’inégalité triangulaire : pour tous sommets $a$, $b$ et $c$ du méta-graphe, on a $d(a, c) \leq d(a, b) + d(b, c)$. Autrement dit, faire un détour par $b$ ne raccourcit jamais le trajet de $a$ à $c$.

Preuve
Cliquez ici pour afficher la preuve.

Le poids $d(a, c)$ est la longueur d’un plus court chemin de $a$ à $c$ dans le labyrinthe. Or, en mettant bout à bout un plus court chemin de $a$ à $b$ et un plus court chemin de $b$ à $c$, on obtient un chemin de $a$ à $c$ dans le labyrinthe, de longueur $d(a, b) + d(b, c)$ (éventuellement avec des cases répétées, ce qui ne pose pas de problème ici : on peut les retirer et obtenir un chemin encore plus court). Comme $d(a, c)$ est la longueur du plus court de tous les chemins de $a$ à $c$, on a bien $d(a, c) \leq d(a, b) + d(b, c)$.

Cette propriété n’est pas qu’une curiosité. Le TSP sur des graphes qui la vérifient, appelé TSP métrique, reste NP-complet, mais il admet des algorithmes d’approximation avec des garanties : par exemple, l’algorithme de Christofides trouve un tour au plus 1,5 fois plus long que le tour optimal. C’est aussi elle qui justifie l’intuition, exploitée dans l’activité pratique, qu’il vaut mieux ramasser les morceaux de fromage proches les uns des autres à la suite, plutôt que de faire des allers-retours.

Un algorithme exact plus rapide : Held-Karp

Essayer tous les ordres est très coûteux, car de nombreux calculs sont refaits. Par exemple, les ordres qui commencent par $(A, B, C)$ et par $(B, A, C)$ continuent de la même manière à partir de $C$ : seul compte le meilleur des deux débuts. L’algorithme de Held-Karp (1962) exploite cette remarque grâce à la programmation dynamique vue en cours d’algorithmique.

Pour chaque ensemble $S$ de morceaux de fromage et chaque morceau $v$ de $S$, on calcule $best(S, v)$, la longueur d’un plus court chemin qui part de la position de départ $s$, ramasse exactement les morceaux de $S$, et termine par $v$ :

  • Si $S$ ne contient que $v$, alors $best(\{v\}, v) = d(s, v)$.
  • Sinon, l’avant-dernier morceau $u$ est un autre élément de $S$, et $best(S, v) = \min\limits_{u \in S \setminus \{v\}} \left( best(S \setminus \{v\}, u) + d(u, v) \right)$.

On calcule ces valeurs par taille croissante de $S$, et la longueur du meilleur chemin est le minimum des $best(S, v)$ quand $S$ contient tous les morceaux de fromage. Voici une implémentation, qui prend en entrée les distances du méta-graphe :

​
import itertools

def held_karp ( distances: dict[int, dict[int, int]],
                source:    int
              ) ->         tuple[int, list[int]]:

    """
    Finds a shortest path that starts at the source and visits all other vertices of a complete graph, with Held-Karp's algorithm.

    Args:
        distances: The distances between all pairs of vertices (e.g., a meta-graph).
        source:    The vertex at which the path starts.

    Returns:
        A tuple containing the length of the path, and the path itself as a list of vertices.
    """

    # Vertices to visit, after the source
    others = [vertex for vertex in distances if vertex != source]
    if not others:
        return 0, [source]

    # best[(subset, last)] gives the length of a shortest path that starts at the source, visits exactly the vertices of the subset, and ends at last
    # It also gives the vertex visited just before last on that path, to rebuild it at the end
    best = {}
    for vertex in others:
        best[(frozenset([vertex]), vertex)] = (distances[source][vertex], source)

    # Subsets are considered by increasing size, so that the values needed for a subset are already known
    for size in range(2, len(others) + 1):
        for subset in itertools.combinations(others, size):
            subset = frozenset(subset)
            for last in subset:
                rest = subset - {last}
                best[(subset, last)] = min((best[(rest, previous)][0] + distances[previous][last], previous) for previous in rest)

    # The best path visits all vertices, and can end anywhere
    all_vertices = frozenset(others)
    length, last = min((best[(all_vertices, last)][0], last) for last in others)

    # Rebuild the path, going back from its last vertex
    path = [last]
    subset = all_vertices
    while path[-1] != source:
        previous = best[(subset, path[-1])][1]
        subset = subset - {path[-1]}
        path.append(previous)
    path.reverse()
    return length, path

Il y a $2^k$ ensembles $S$, et pour chacun, $k$ valeurs à calculer en considérant $k$ avant-derniers possibles : la complexité est $O(k^2 \cdot 2^k)$ en temps, et $O(k \cdot 2^k)$ en mémoire. C’est toujours exponentiel, mais bien plus petit que $k!$. Voici les temps mesurés en Python, sur des méta-graphes construits à partir de labyrinthes PyRat :

Morceaux de fromage $k$ Essayer tous les ordres Held-Karp Mémoire utilisée par Held-Karp
8 19 ms 0,7 ms négligeable
10 1,9 s 5 ms négligeable
12 environ 4 min (estimé) 26 ms négligeable
14 environ 12 h (estimé) 0,14 s quelques dizaines de Mo
16 plusieurs mois (estimé) 0,8 s 185 Mo
18 plus d’un siècle (estimé) 4,8 s 670 Mo

Held-Karp trouve la solution optimale en quelques secondes là où essayer tous les ordres prendrait plus d’un siècle. Mais sa consommation de mémoire, multipliée par environ 4 tous les 2 morceaux de fromage, devient vite la vraie limite : avec les 21 morceaux de fromage d’une partie par défaut, il faudrait plusieurs gigaoctets. Le TSP reste un problème difficile, et c’est pourquoi les séances suivantes s’intéressent à des algorithmes qui renoncent à trouver la solution optimale.

Pour aller encore plus loin