7.5 Espaces de permutations
211
θ (i,j) =
1 . . . i + 0 . . . i + p ... i + (j − i) = j ... N
1 . . . (j − 0) . . . (j − p) . . . (j − (j − i)) = i . . . N
Apr` es avoir not´ e que l’on a
θ (i,j) θ (i+1,j−1) =
1 . . . i i + 1 . . . j − 1 j . . . N
1 . . . j j − 1 . . . i + 1 i . . . N
et
θ (i,j) θ (i+1,j−1) θ (i+2,j−2) =
1 . . . i i + 1 i + 2 . . . j − 2 j − 1 j . . . N
1 . . . j j − 1 j − 2 . . . i + 2 i + 1 i . . . N
il est assez ais´ e de v´ erifier que ces inversions correspondent ` a des produits de
transpositions
θ (i,j) = θ (i,j) θ (i+1,j−1) θ (i+2,j−2) . . . θ (i+[
j−i
2 ],j−[
j−i
2 ])
Les syst` emes de voisinages associ´ es `
a ces inversions locales sont alors d´ efinis
de la fa¸ con suivante :
σ ∼ τ ⇐⇒ ∃i ≤ j : τ = σθ (i,j)
En termes matriciels, on peut noter que l’on a
σθ (i,j) =
1 . . . i + 0 . . . i + p ...
i + (j − i) = j
. . . N
σ(1) . . . σ(j − 0) . . . σ(j − p) . . . σ(j − (j − i)) = σ(i) . . . σ(N )
Le processus d’exploration al´ eatoire correspondant est donn´ e par la dynamique al´ eatoire suivante
σ n = σ n−1 θ Un
o` u U n d´ esigne une suite de variables al´ eatoires ind´ ependantes, et uniform´ ement
choisies dans l’ensemble U .
7.5.5 Fonctions ´ energie
La longueur d’un circuit σ ∈ G N entre N villes {v 1 , v 2 , . . . , v N }
v σ(1) → v σ(2) → . . . → v σ(N −1) → v σ(N ) → v σ(1)
est donn´ ee par la fonction V d´ efinie par :
V (σ) =
N
i=1
d(v σ(i) , v σ(i+1) )
avec la convention σ(N + 1) = σ(1) lorsque p = N , de sorte que v σ(N +1) =
σ(1). L’objectif du voyageur de commerce est de trouver le circuit minimisant
ce crit` ere.