266
20 Problème du voyageur de commerce
globale comme par exemple le recuit simulé, abordé dans la section 5.3, pour
produire en un temps raisonnable une solution approchée : une permutation
pour laquelle le minimum est (presque) atteint.
Plutôt que de rechercher une permutation optimale, nous nous intéressons
dans ce chapitre à la valeur du minimum, et à son comportement lorsque n
est grand et les points X 1 , . . . , X n sont des variables aléatoires indépendantes
et de même loi μ sur R
d . On note L n = L n (X 1 , . . . , X n ) la longueur minimale
de la tournée, qui est une fonction de X 1 , . . . , X n .
Fig. 20.1. Trajet le plus court pour n = 20 points uniformément répartis dans le
carré unité obtenu par l’algorithme stochastique du recuit simulé (chapitre 4).
Théorème 20.1 (Bearwood-Halton-Hammersley). Il existe une constante
0 < γ d < ∞ qui dépend de d 2 telle que si μ est à support compact et
de densité f : R
d
→ R + par rapport à la mesure de Lebesgue, alors
L n (X 1 , . . . , X n )
n (d−1)/d
p.s.
−→
n→∞
γ d
R d
f (x)
(d−1)/d dx.
En particulier L n (X 1 , . . . , X n ) est d’ordre
√ n en dimension d = 2. Nous
allons établir ce théorème lorsque μ est la loi uniforme sur le cube [0, 1]
d .
Nous allons montrer que la variable aléatoire L n (X 1 , . . . , X n ) est d’autant
plus concentrée autour de son espérance E(L n (X 1 , . . . , X n )) que n est grand,
puis que cette espérance est d’ordre n
(d−1)/d .