Passer une fois par chaque ville et revenir — au plus court.
L'énoncé tient en une ligne : étant donné des villes et les distances entre elles, trouver la tournée la plus courte qui les visite toutes une fois et revient au point de départ. Aucune notion difficile, aucun préalable. C'est pourtant le problème le plus étudié de toute l'optimisation combinatoire, et personne ne sait le résoudre vite.
La raison n'est pas qu'on manque d'idées : c'est que le nombre de tournées possibles écrase toute machine. La question intéressante n'est donc pas « quelle est la meilleure tournée », mais « comment obtenir une très bonne tournée, et comment savoir qu'elle est très bonne sans connaître la meilleure ». Les cinq planches suivent exactement ce fil : compter, construire, améliorer, encadrer, puis mesurer la constante universelle qui gouverne le tout.
Une tournée est un ordre de visite. En fixant la ville de départ et en remarquant qu'une tournée parcourue à l'envers a la même longueur, il reste
(n − 1)! / 2 tournées distinctes.
Pour 10 villes, 181 440 : une bagatelle. Pour 20 villes, 6·1016. Pour 30, 4·1030. Déplacez les villes à la souris ; le programme calcule l'optimum de deux façons — par examen de toutes les tournées, et par la programmation dynamique de Held et Karp, qui ramène le coût de (n−1)!/2 à n²·2n.
Une tournée optimale ne se croise jamais elle-même : si deux segments se coupaient, on pourrait les décroiser et raccourcir le trajet — c'est l'inégalité triangulaire. Le compteur de croisements affiche donc toujours 0 sur l'optimum, et presque toujours autre chose sur une tournée tirée au hasard. Cette remarque est la graine de toute la planche 3.
Voici, en échelle logarithmique, le nombre de tournées à examiner selon le nombre de villes, et ce qu'il faudrait de temps à une machine en examinant un milliard par seconde.
Puisque l'optimum est hors d'atteinte au-delà d'une vingtaine de villes, il faut fabriquer directement une tournée raisonnable. Quatre recettes classiques, toutes très rapides : suivre à chaque fois la ville la plus proche ; partir d'un petit circuit et y insérer les villes une à une, soit la plus proche, soit celle qui coûte le moins cher à insérer ; ou encore assembler les arêtes courtes tant qu'elles ne créent ni fourche ni boucle prématurée.
Le plus proche voisin a un défaut structurel visible à l'écran : il file droit tant qu'il trouve des voisins commodes, puis doit revenir chercher les oubliés en traversant toute la carte. Les insertions, elles, gardent à chaque étape un circuit complet — plus lentes à écrire, bien meilleures en pratique.
Prenez deux arêtes de la tournée, retirez-les, et rebranchez les deux morceaux dans l'autre sens : c'est le mouvement 2-opt. Si le nouveau trajet est plus court, on garde. On répète jusqu'à ce qu'aucun échange ne fasse plus gagner. Une seule règle, appliquée obstinément, transforme n'importe quelle tournée en une tournée sans croisement — et généralement à quelques pour cent de l'optimum.
Le contrôle décisif est le « meilleur échange encore possible » : une fois la descente terminée, on réexamine les n(n−3)/2 échanges et l'on vérifie qu'aucun ne gagne quoi que ce soit. La tournée est alors un optimum local — et le bouton des cinquante départs montre aussitôt la limite de la méthode : ces optima locaux ne sont pas tous égaux, et le hasard du départ décide de plusieurs pour cent.
Une heuristique donne une tournée, donc une borne supérieure. Pour affirmer qu'elle est bonne, il faut une borne inférieure : un nombre dont on est certain qu'aucune tournée ne descend en dessous. Retirer une arête d'une tournée laisse un chemin, donc un arbre couvrant : la longueur d'un arbre couvrant minimal est déjà une borne. Beaucoup mieux : le 1-arbre — un arbre couvrant sur les villes 2…n, plus les deux arêtes les moins chères issues de la ville 1 — est un minorant plus serré, qu'on peut resserrer encore en pénalisant les villes de mauvais degré. C'est la borne de Held et Karp.
Quand tous les sommets du 1-arbre atteignent le degré 2, le 1-arbre est une tournée : la borne inférieure et la borne supérieure se rejoignent, et l'optimalité est démontrée. C'est exactement ce que fait un solveur exact moderne — non pas énumérer, mais resserrer un encadrement jusqu'à ce qu'il se referme.
Le défaut du 2-opt est de ne jamais accepter de perdre. Le recuit simulé corrige cela en imitant le refroidissement d'un métal : à haute température, les échanges défavorables sont acceptés avec la probabilité e−Δ/T ; en refroidissant, cette tolérance disparaît et le système se fige. La tournée commence par se démêler dans le désordre, puis se resserre.
Le taux d'acceptation raconte le refroidissement mieux qu'un thermomètre : il part près de 100 %, chute lentement, et tombe à quelques pour cent quand la tournée se fige. Toute la difficulté du réglage est là — refroidir trop vite fige un mauvais état, refroidir trop lentement coûte du temps pour rien.
Voici le fait le plus surprenant du sujet. Jetez n villes au hasard, uniformément, dans un carré d'aire A. La longueur de la tournée optimale n'est pas quelconque : quand n grandit, elle s'approche de β·√(nA), où β est une constante universelle — la même pour tous les tirages, indépendante de tout. C'est le théorème de Beardwood, Halton et Hammersley (1959). Sa valeur n'est connue que numériquement : β ≈ 0,7124.
L'extrapolation ne tombe pas sur 0,7124 mais quelques pour cent au-dessus, et ce n'est pas un défaut de la mesure : les tournées mesurées ne sont pas optimales, elles sont issues d'une recherche locale. Le second bouton mesure cet excès indépendamment, en confrontant les mêmes tournées à la borne inférieure de Held-Karp de la planche 4 — et l'on retrouve, à peu de chose près, l'écart constaté sur la constante. Les deux écarts n'en font qu'un.