Algorithmes probabilistes, approximation, séparation et évaluation

Le programme cite ce problème ici, après l'avoir cité au chapitre chap:exploration pour le retour sur trace. La version Las Vegas est brutale :

(* Renvoie un placement valide de n reines. Précondition : n >= 4.
   TOUJOURS correct ; temps aléatoire. *)
let rec reines_las_vegas n =
  let pos = Array.init n (fun i -> i) in
  melanger pos;                       (* une permutation au hasard *)
  if valide pos then pos else reines_las_vegas n

Une permutation garantit déjà qu'aucune reine ne partage sa ligne ni sa colonne : il ne reste à vérifier que les diagonales. Le résultat rendu est toujours valide ; c'est le nombre d'essais qui est aléatoire.

Le quickselect choisit un pivot au hasard et ne récurse que d'un côté :

(* k-ième plus petit élément de t (k à partir de 0).
   Précondition : 0 <= k < longueur. Espérance : Theta(n) ; pire cas : Theta(n²). *)
let rec selection t k =
  let pivot = t.(hasard (Array.length t)) in
  let inf = filtre (fun x -> x < pivot) t
  and egal = filtre (fun x -> x = pivot) t
  and sup = filtre (fun x -> x > pivot) t in
  if k < Array.length inf then selection inf k
  else if k < Array.length inf + Array.length egal then pivot
  else selection sup (k - Array.length inf - Array.length egal)

C'est encore un Las Vegas, et non un Monte-Carlo : le résultat est toujours le bon élément, seul le temps est aléatoire. Le programme cite ce problème sans le classer ; la définition donnée plus haut tranche.

Trier coûterait $\Theta (n\log n)$ ; ici l'espérance est $\Theta (n)$, car le pivot aléatoire élimine en moyenne la moitié du tableau. Le pire cas reste $\Theta (n^2)$ — mais il exige une suite de pivots systématiquement extrêmes, dont la probabilité décroît exponentiellement. Aucun adversaire ne peut la provoquer, puisqu'il ne connaît pas les tirages.

Le chapitre chap:textes le notait : la recherche par empreintes est un Monte-Carlo — une égalité d'empreintes peut être une collision — rendu exact par une vérification caractère par caractère. C'est un schéma courant : on emploie un test rapide et faillible pour écarter la masse, puis un test lent et sûr sur le peu qui reste.

Construite et démontrée au chapitre chap:gloutons. On en rappelle l'argument, car il est le patron du genre : les arêtes qui déclenchent une prise forment un couplage $M$ ; toute couverture doit contenir au moins un sommet par arête de $M$, donc $|OPT|\ge |M|$ ; l'algorithme prend $2|M|$ sommets. D'où $|ALG|\le 2|OPT|$.

La structure de toute preuve d'approximation est là : trouver une minoration de l'optimum — ici $|M|$ — puis majorer la solution rendue par un multiple de cette minoration. On ne compare jamais à l'optimum lui-même, qu'on ne sait pas calculer.

Le programme suggère d'indiquer, « par exemple sur le problème MAX2SAT, que la méthode probabiliste peut fournir de bons algorithmes d'approximation ». MAX2SAT : étant donné une fnc à deux littéraux par clause, satisfaire le plus de clauses possible.

L'algorithme : tirer chaque variable à pile ou face, indépendamment.

L'analyse. Une clause à deux littéraux est fausse dans exactement un cas sur quatre — celui où ses deux littéraux sont faux. Chaque clause est donc satisfaite avec probabilité $3/4$. Par linéarité de l'espérance, sur $m$ clauses :

$$\mathbb{E}[\text{clauses satisfaites}]=\frac{3}{4}m.$$

Comme l'optimum ne peut dépasser $m$, cet algorithme trivial est une $3/4$-approximation en espérance. Et il ne regarde même pas la formule.

Ce que cet exemple enseigne : la linéarité de l'espérance ne demande aucune indépendance entre les clauses, alors qu'elles en partagent les variables. C'est ce qui rend l'argument si court — et c'est exactement ce que le programme appelle « la méthode probabiliste ».

La borne classique vient de la relaxation continue — que le programme cite : « on peut évoquer sur des exemples quelques techniques d'évaluation comme les méthodes de relaxation ». On autorise à couper les objets, ce qui rend le problème facile : le glouton par rapport valeur/poids décroissant y est alors optimal.

(* Meilleure valeur atteignable en poursuivant depuis l'objet i avec la
   capacité c ; objets TRIÉS par rapport valeur/poids décroissant.
   Borne SUPÉRIEURE : on autorise à fractionner le dernier objet. *)
let borne p v i c =
  let reste = ref c and total = ref 0.0 and k = ref i in
  while !k < Array.length p && p.(!k) <= !reste do
    reste := !reste - p.(!k);
    total := !total +. float_of_int v.(!k);
    incr k
  done;
  if !k < Array.length p then                      (* la FRACTION du suivant *)
    total := !total +. float_of_int v.(!k)
                       *. float_of_int !reste /. float_of_int p.(!k);
  !total

(* Valeur maximale, exacte. On coupe dès que la borne ne bat pas le record. *)
let sac_bb p v n capacite =
  let record = ref 0 in
  let rec explorer i c acquis =
    if acquis > !record then record := acquis;
    if i < n && float_of_int acquis +. borne p v i c > float_of_int !record then begin
      if p.(i) <= c then explorer (i + 1) (c - p.(i)) (acquis + v.(i));   (* on prend *)
      explorer (i + 1) c acquis                                          (* on laisse *)
    end
  in
  explorer 0 capacite 0;
  !record

Pourquoi la relaxation donne bien une borne supérieure : toute solution entière est une solution fractionnaire particulière, donc l'optimum fractionnaire est au moins égal à l'optimum entier. La branche ne peut pas rapporter davantage.