208
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
Fig. 7.3. Exemple de chemin associ´ e `
a une permutation pour N = 4 villes
Il existe sur cet espace diverses fa¸ cons de sp´ ecifier des syst` emes de voisinage
sur l’ensemble G N . Pour les d´ efinir plus pr´ ecis´ ement, il convient d’introduire
les fonctions de transposition θ (i,j) ∈ G N des indices i et j
θ (i,j) =
1 . . . i . . . j . . . N
1 . . . j . . . i . . . N
Un premier syst` eme de voisinage ´ el´ ementaire consiste ` a convenir que deux permutations σ et τ sont voisines d` es qu’elles ne diff´ erent que d’une transposition
d’indices
σ ∼ τ ⇐⇒ ∃i ≤ j : τ = σθ (i,j)
En termes matriciels, nous avons
τ = σθ (i,j) =
1 . . . i . . . j
. . . N
σ(1) . . . σ(j) . . . σ(i) . . . σ(N )
7.5.2 Explorations locales
Il est tout ` a fait envisageable de visiter l’espace G N tout entier ` a l’aide de
ces syst` emes de voisinages. Autrement dit, tout site τ est accessible en sautillant d’un voisinage ` a un autre, `
a partir d’un quelconque point de d´ epart σ.