346
11 Optimisation et Combinatoire ´ enum´ erative
σ =
1 . . . N
σ(1) . . . σ(N )
telle que σ(1) = 1, de sorte ` a minimiser la distance
d(v σ(1) , v σ(2) ) + . . . + d(v σ(N −1) , v σ(N ) ) + d(v σ(N ) , v σ(1) )
qu’il aura parcourue en effectuant le circuit
v σ(1) = v 1 −→ v σ(2) −→ . . . −→ v σ(N ) −→ v σ(1) = v 1 .
On notera par la suite G N l’ensemble des permutations de {1, . . . , N}. Pour
chaque σ ∈ G N , on utilisera la convention σ(N + 1) = σ(1) et on notera
U : σ ∈ G N → U (σ) =
N
p=1
d(v σ(p) , v σ(p+1) ) ∈ R + .
Pour chaque p ≥ 1, on d´ esigne par G N (p) et G
N (p) les sous-ensembles de G N
d´ efinis par
G N (p) = {σ ∈ G N ; σ(p) = 1}
G
N (p) = {σ ∈ G N (p) ; U (σ) = min
τ ∈G N (p)
U (τ )}.
On prendra comme espace d’´ etat E = G N . Il existe sur cet espace diverses
fa¸ cons de sp´ ecifier des syst` emes de voisinage.
– Permutation de deux indices :
σ ∼ τ ⇐⇒ ∃i ≤ j : σ =
1 . . . i . . . j
. . . N
τ (1) . . . τ(j) . . . τ(i) . . . τ(N )
– Inversion d’une suite d’indices :
σ ∼ τ ⇐⇒ ∃i ≤ j : σ =
1 . . . i + 0 . . . i + p . . .
i + (j − i) = j
... N
τ (1) . . . τ(j − 0) . . . τ(j − p) . . . τ(j − (j − i)) = τ (j) . . . τ(N )
Dans les deux cas, on peut montrer que pour chaque σ et τ ∈ G N il existe une
suite (σ 0 , . . . , σ N ) d’´ el´ ements de G N telle que
σ 0 = σ ∼ σ 1 ∼ . . . ∼ σ N = τ.
Pour r´ ealiser l’algorithme de recuit, on utilisera une probabilit´ e de transition
K(σ, τ ) d´ efinie par l’un de ces syst` emes de voisinage, c’est-` a-dire
K(σ, τ ) =
1
|V(σ)|
1 V(σ) (τ ),
V(σ) = {τ ∈ G N ; τ ∼ σ}.
– V´ erifier que
σ ∼ τ ⇐⇒ K(σ, τ ) > 0.
– En d´ eduire que
∀σ, τ ∈ G N ,
K
N (σ, τ ) > 0.