Une heuristique n'est pas une approximation

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 25 — Algorithmes probabilistes, approximation, séparation et évaluation

Énoncé

Le glouton du sac à dos prend les objets par rapport valeur/poids décroissant.

Construire une famille d'instances où son rapport à l'optimum tend vers $0$ .
Le corriger d'une ligne pour en faire une $1/2$ -approximation.

Corrigé

1. Deux objets suffisent, et une capacité $C$ qu'on fait grandir :

Objet	poids	valeur	rapport valeur/poids
$A$	$1$	$2$	$2$
$B$	$C$	$C$	$1$

Le glouton prend $A$ d'abord — son rapport est le meilleur —, puis $B$ ne tient plus : il reste $C - 1$ de capacité et $B$ pèse $C$ . Il rend $2$ . L'optimum prend $B$ seul et rend $C$ . Mesures :

$C$	glouton	optimum	rapport
$10$	$2$	$10$	$0, 200$
$100$	$2$	$100$	$0, 020$
$1000$	$2$	$1000$	$0, 002$
$1 0^{6}$	$2$	$1 0^{6}$	$2 \cdot 1 0^{- 6}$

Le rapport tend vers $0$ : aucune constante $ρ$ ne convient. Le glouton du sac à dos n'est pas une $ρ$ -approximation, pour aucun $ρ$ . C'est ce que le tableau récapitulatif du chapitre note d'un « aucune garantie ».

2. La correction tient en une ligne : comparer le résultat du glouton à celui de la meilleure solution à un seul objet, et garder le meilleur des deux.


(* 1/2-approximation du sac a dos.
   Entrees : poids p, valeurs v (positives), capacite c.
   Sortie  : une valeur atteignable >= OPT/2. Complexite : O(n log n). *)
let glouton_ameliore p v c =
  let meilleur_seul = ref 0 in
  for i = 0 to Array.length p - 1 do
    if p.(i) <= c && v.(i) > !meilleur_seul then meilleur_seul := v.(i)
  done;
  max (glouton p v c) !meilleur_seul

La preuve. On peut supposer que tout objet tient seul dans le sac : un objet plus lourd que la capacité n'entre dans aucune solution, et les deux algorithmes l'ignorent à l'identique. Soit alors $j$ le premier objet que le glouton refuse par manque de place, et $G^{'}$ la valeur qu'il a accumulée avant $j$ ; on a $G^{'} \leq G$ , puisque le glouton continue après $j$ .

La relaxation continue — objets triés par rapport décroissant, fractionnement autorisé — donne une borne supérieure de $O P T$ , et cette borne vaut $G^{'}$ plus une fraction de $v_{j}$ . Donc

$O P T \leq G^{'} + v_{j} \leq G + v_{j} \leq 2 max (G, v_{j}) \leq 2 \cdot glouton_ameliore .$

La dernière inégalité vient de ce que $v_{j}$ est la valeur d'un objet qui tient seul dans le sac, donc $v_{j} \leq$ meilleur_seul.

Vérification : sur $200000$ instances tirées au hasard, le rapport minimal du glouton seul descend à $0, 0667$ , tandis que celui du glouton amélioré ne descend pas sous $0, 5294$ — au-dessus de la garantie $0, 5$ , comme il se doit.

Ce que cet exercice enseigne. Une heuristique et une approximation peuvent différer d'une ligne de code, mais elles ne diffèrent pas d'un peu : l'une n'a aucune garantie, l'autre en a une, prouvée sur toute instance. Et remarquer que la preuve suit exactement le patron annoncé par le chapitre : on minore l'optimum — ici en le majorant par $G + v_{j}$ —, jamais on ne le calcule.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.