6.2 Mesures invariantes et algorithmes de simulation
161
L’un des probl` emes d’optimisation globale les plus connus consiste `
a chercher un circuit de longueur minimale, et reliant tous les points de E m . Un
circuit dans E m correspond clairement au choix d’une permutation des indices
des points de E m . Plus formellement, l’application
σ ∈ G m → (e σ(1) , e σ(2) , . . . , e σ(m) , e σ(m+1) ) ∈ C m
avec la convention σ(m +1) = σ(1), permet d’identifier l’ensemble des circuits
C m dans E m avec le groupe sym´ etrique G m sur {1, . . . , m}.
La longueur d’un circuit σ ∈ G m est donn´ ee par la fonction U d´ efinie par :
U (σ) =
m
p=1
d(e σ(p) , e σ(p+1) )
Fig. 6.5. Voyageur de commerce sur un cercle de 18 villes
161
L’un des probl` emes d’optimisation globale les plus connus consiste `
a chercher un circuit de longueur minimale, et reliant tous les points de E m . Un
circuit dans E m correspond clairement au choix d’une permutation des indices
des points de E m . Plus formellement, l’application
σ ∈ G m → (e σ(1) , e σ(2) , . . . , e σ(m) , e σ(m+1) ) ∈ C m
avec la convention σ(m +1) = σ(1), permet d’identifier l’ensemble des circuits
C m dans E m avec le groupe sym´ etrique G m sur {1, . . . , m}.
La longueur d’un circuit σ ∈ G m est donn´ ee par la fonction U d´ efinie par :
U (σ) =
m
p=1
d(e σ(p) , e σ(p+1) )
Fig. 6.5. Voyageur de commerce sur un cercle de 18 villes