76
5 Mesures de Gibbs
recuit simulé. On peut choisir par exemple pour noyau d’exploration Q celui
de la marche aléatoire simple sur S n associée aux transpositions, donné par
Q(x, y) =
2
n(n−1)
si y = xτ pour une transposition τ ,
0
sinon.
Puisque les transpositions engendrent le groupe symétrique S n , le noyau de
transition Q est irréductible. On peut bien entendu choisir un noyau d’exploration plus riche, qui, par exemple, échange k villes tirées au hasard.
L’étude de l’ordre de grandeur de H(x) lorsque les positions v 1 , . . . , v n des
n villes sont aléatoires i.i.d. et n est grand fait l’objet du chapitre 20.
Fig. 5.1. Étapes de l’algorithme du recuit pour le voyageur de commerce (n = 10).