188
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
Fig. 6.12. Echantilonneur de Gibbs sur le disque
Bien que ces mesures puissent paraˆ ıtre triviales et ´ el´ ementaires, le simple
calcul du cardinal de l’ensemble A peut s’av´ erer un probl` eme d’´ enum´ eration
combinatoire complexe.
A titre d’exemple, examinons le probl` eme d’optimisation combinatoire du
remplissage d’un sac ` a dos ne pouvant supporter qu’un certain poids. Ce
remplissage s’effectue sur la base d’une collection d’objets ayant chacun un
poids. Ce probl` eme se mod´ elise de la fa¸ con suivante :
On num´ erote par un indice i variant de 1 ` a d l’ensemble de ces objets. On
affecte ensuite `
a chacun des objets un couple de nombres (p i , w i ). Le premier
nombre p i repr´ esente le poids de l’objet i, le second nombre w i repr´ esente sa
valeur (prix, taille, longueur, indice qualit´ e). Pour indiquer si un objet i est
mis ou non dans le sac `
a dos, on utilise souvent un code binaire. On note
U i = 1 si l’objet est pris, U i = 0 si l’objet est laiss´ e de cˆ ot´ e. Dans ce syst` eme
de notations, l’ensemble de toutes les configurations possibles de sac `
a dos est
d´ ecrit par l’ensemble produit :
E = S
d
avec S = {0, 1}