Problème du Voyageur de Commerce (TSP)

1. Histoire et Contexte

Contrairement aux ponts de Königsberg, le Problème du Voyageur de Commerce (Traveling Salesperson Problem ou TSP) n'est pas né d'un casse-tête de cour, mais d'une nécessité pratique. Il est mentionné pour la première fois en 1832 dans un manuel allemand destiné aux commis voyageurs itinérants, qui donnait des conseils pour organiser leurs tournées postales sans repasser deux fois par le même relais.

Sa formulation mathématique rigoureuse a été posée dans les années 1930 à Vienne par Karl Menger, puis popularisée aux États-Unis par Hassler Whitney (qui lui a donné son nom actuel). Très vite, les mathématiciens se rendent compte que ce problème d'apparence inoffensive résiste à toutes leurs méthodes de résolution :

"Le problème consiste à trouver le chemin le plus court reliant un ensemble de points donnés. Ce problème est bien sûr résoluble en un nombre fini d'essais. Mais la règle qui consisterait à toujours aller vers le point le plus proche ne donne pas en général le chemin le plus court. Le problème demeure non résolu à ce jour."
— Karl Menger, 1930

Pendant la Guerre Froide, la célèbre RAND Corporation (le laboratoire d'idées de l'armée américaine) offre des prix à quiconque proposera un algorithme efficace, le problème étant crucial pour la logistique militaire. C'est là qu'en 1954, George Dantzig, Ray Fulkerson et Selmer Johnson réalisent une percée spectaculaire en résolvant le problème pour une carte de 49 villes américaines. Ils venaient d'inventer la méthode de séparation et évaluation (Branch and Bound), posant les bases de l'optimisation combinatoire moderne.

2. Définition Mathématique

Problème d'optimisation :
Soit $G = (V, E)$ un graphe complet non orienté, et $w : E \to \mathbb{R}^+$ une fonction de pondération (le "coût" ou la "distance").
L'objectif est de trouver un cycle hamiltonien (un cycle passant par chaque sommet de $V$ exactement une fois) $C$ tel que le poids total $\sum_{e \in C} w(e)$ soit minimal.

3. La classe $\mathcal{NP}$ et Vérificateur Interactif

Pourquoi est-ce NP-difficile ?

Pour n villes, le nombre de tournées distinctes est (n-1)!/2.

n villes	Tournées	Temps (1ns/tournée)
10	181 440	< 1 ms
15	43,5 milliards	43 secondes
20	6×10¹⁶	2 ans
50	3×10⁶²	↑ âge de l'Univers

La force brute est O(n!) — totalement infaisable pour n grand.

Qu'est-ce que NP-difficile ?

P = problèmes résolubles en temps polynomial (« faciles »).

NP = problèmes dont une solution peut être vérifiée en temps polynomial.

NP-difficile = tout problème de NP peut se réduire polynomialement vers lui. Résoudre efficacement un problème NP-difficile permettrait de résoudre efficacement tous les problèmes de NP. On ne connaît pas d'algorithme polynomial. Si P≠NP (très probable), il n'en existe pas.

NP-complet = NP-difficile et dans NP (solution vérifiable en temps polynomial). C'est l'intersection des deux classes.

Le TSP-décision (existe-t-il une tournée ≤ k ?) est NP-complet. Le TSP-optimisation (trouver la tournée minimale) est NP-difficile mais pas dans NP (on ne peut pas vérifier qu'une tournée est optimale sans tout explorer).

Exercice : Jouez le rôle du générateur de certificat

Dans ce graphe complet $K_6$, essayez de trouver le cycle hamiltonien de poids minimum en cliquant successivement sur les sommets (survolez les arêtes pour mieux lire leur poids, vous pouvez déplacer les sommets si besoin pour mieux lire le graphe).

Votre Certificat :
Aucun sommet sélectionné

Poids actuel : 0