Problème — Le sac à dos par séparation et évaluation — exercice corrigé d'informatique (MP2I/MPI) (chapitre 25)

1. La relaxation continue. On autorise à prendre une fraction d'objet. Le problème devient facile, et le glouton par rapport valeur/poids décroissant y est optimal :

Preuve. Soit une solution fractionnaire optimale $z$ qui ne suit pas l'ordre glouton : il existe $i < j$ avec $z_{i} < 1$ et $z_{j} > 0$ , alors que $v_{i} / p_{i} \geq v_{j} / p_{j}$ . Transférons une quantité $ε$ de poids de $j$ vers $i$ : la valeur varie de $ε (v_{i} / p_{i} - v_{j} / p_{j}) \geq 0$ . La solution reste réalisable et n'a pas perdu de valeur. En répétant, on atteint la solution gloutonne, qui est donc optimale.

La borne majore l'optimum entier : toute solution entière est une solution fractionnaire particulière (avec des $z_{i} \in {0, 1}$ ), donc

$O P T_{entier} \leq O P T_{fractionnaire} = borne .$

Elle est optimiste, comme le chapitre l'exige. Et elle est la meilleure borne qu'on puisse tirer de la relaxation, puisqu'elle est l'optimum du problème relâché : la seule façon de faire mieux serait de relâcher moins.

2. L'algorithme.


(* Borne superieure sur ce qu'on peut encore gagner depuis l'objet i avec la
   capacite c. Precondition : objets TRIES par rapport valeur/poids decroissant.
   Complexite : O(n - i). *)
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 d'un sac a dos, EXACTE.
   Entrees : poids p, valeurs v (tries par rapport decroissant), capacite.
   Sortie  : la valeur optimale. Complexite : O(2^n) au pire. *)
let sac_bb p v capacite =
  let n = Array.length p in
  let record = ref 0 in
  (* INVARIANT : record est la meilleure valeur COMPLETE deja rencontree ;
     toute branche dont la borne ne la depasse pas est inutile. *)
  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));
        explorer (i + 1) c acquis
      end
  in
  explorer 0 capacite 0;
  !record

Terminaison : variant $n - i$ , qui décroît strictement à chaque appel. Correction : on ne coupe que si $acquis + borne \leq record$ ; comme la borne majore ce que la branche peut ajouter, aucune solution de valeur $>$ record n'y était. Le résultat reste exact.

3. La mesure, sur $30$ instances aléatoires par taille, capacité fixée à la moitié du poids total :

$n$	retour sur trace	séparation et évaluation	rapport
$10$	$1304$	$30$	$44$
$15$	$40355$	$45$	$902$
$20$	$1280238$	$60$	$21457$
$24$	$20154640$	$62$	$324726$

(Le résultat des deux méthodes a été comparé, à chaque instance, à celui d'une programmation dynamique exacte : identique.)

Ce que le tableau montre. Le retour sur trace double son coût à chaque objet ajouté — on lit $2^{n + 1}$ dans la colonne. La séparation et évaluation, elle, explore une soixantaine de nœuds quelle que soit la taille sur cette famille d'instances. Le pire cas reste exponentiel — la borne peut être inutile sur des instances construites exprès —, mais l'écart pratique atteint cinq ordres de grandeur à $n = 24$ .

4. Le tri est ce qui rend la borne bonne. La borne repose sur l'optimalité du glouton fractionnaire, qui n'est vraie que si les objets sont dans l'ordre des rapports décroissants. Deux conséquences :

Sans tri, la fonction borne rendrait encore une majoration valable — elle prend des objets jusqu'à saturation, ce qui reste $\leq$ l'optimum fractionnaire — mais beaucoup plus lâche, et l'élagage s'effondrerait.
Avec tri, l'ordre d'exploration lui-même s'améliore : la branche « on prend » est essayée d'abord sur les objets les plus rentables, donc un bon record apparaît très tôt, et c'est ce record qui coupe tout le reste.

Le tri fait donc double emploi : il rend la borne serrée, et il fait trouver vite une bonne solution. C'est exactement ce que le programme appelle « évoquer l'intérêt d'ordonner les données avant de les parcourir ». Le coût du tri, $O (n lo g n)$ , est négligeable devant ce qu'il économise.

Problème — Le sac à dos par séparation et évaluation

Énoncé

Corrigé

Exercices semblables