TD d’algorithmique avanc´ee
Corrig´e du TD 12 : Heuristique de rangement
Jean-Michel Dischler et Fr´ed´eric Vivien
On a n objets. Le ie objet est de taille si avec 0 < si < 1. On souhaite ranger ces objets dans des boˆıtes
en utilisant le minimum de boˆıtes possibles, sachant que chaque boˆıte est de taille unitaire : chaque boˆıte
peut contenir un sous-ensemble quelconque des objets du moment que la somme des tailles de ces objets
n’exc`ede pas 1.
Ce probl`eme est NP-complet. Pour le r´esoudre on utilise l’heuristique Fischer-Price : on prend les objets
l’un apres l’autre et un objet est plac´e dans la premiere boˆıte qui peut l’accueillir. On note S =
1. Montrez que le nombre optimal de boˆıtes n´ecessaires est au moins ´egal `a (cid:100)S(cid:101).
n
i=1 si.
(cid:80)
Les boˆıtes doivent contenir une taille totale S d’objets. Chaque boˆıte ´etant de taille 1, il faut au moins
(cid:100)S(cid:101) boˆıtes pour contenir les objets ((cid:100)S(cid:101) est le plus petit entier sup´erieur ou ´egal `a S).
2. Montrez que l’heuristique Fischer-Price laisse au plus une boˆıte remplie `a moins de la moiti´e.
On raisonne par l’absurde et on suppose qu’il existe au moins deux boˆıtes, not´ees A et B, qui sont
remplies a moins de la moiti´e. Sans perte de g´en´eralit´es, on suppose que la boˆıte A a commenc´e a
ˆetre remplie avant la boˆıte B. Soit x le premier objet ajout´e a la boˆıte B. La boˆıte B ´etant a la fin
de l’algorithme remplie `a moins de la moiti´e et tous les poids ´etant positifs, x est de taille inf´erieure
a 1/2. A ´etant remplie a moins de la moiti´e `a la fin de l’ex´ecution de l’heuristique, et tous les poids
´etant positifs, A ´etait remplie a moins de la moiti´e quand x a ´et´e rajout´e a B. Donc l’heuristique, vu sa
d´efinition, a ajout´e x a A au lieu de commencer a remplir une nouvelle boˆıte (B). Il y a contradiction
et l’heuristique Fischer-Price laisse au plus une boˆıte remplie `a moins de la moiti´e.
Publicité
3. D´emontrez que le nombre de boˆıtes utilis´ees par l’heuristique Fischer-Price n’est jamais strictement
sup´erieur `a (cid:100)2S(cid:101).
Deux corrections diff´erentes : une « brutale » par l’absurde, et une plus « subtile » et qui permet
d’obtenir une borne plus fine :
(a) Nous venons de voir que l’heuristique Fischer-Price laisse au plus une boˆıte remplie `a moins de
la moiti´e. Donc toutes les boˆıtes sauf au maximum une sont remplies strictement `a plus de la
moiti´e. Raisonnons une fois de plus par l’absurde. Supposons que le nombre de boˆıtes utilis´ees, b,
est strictement sup´erieur `a (cid:100)2S(cid:101) :
b > (cid:100)2S(cid:101) ⇔ b ≥ 1 + (cid:100)2S(cid:101) ⇔ b − 1 ≥ (cid:100)2S(cid:101).
Or, d’apres ce qui pr´ecede, (au moins) b − 1 boˆıtes sont remplies strictement `a plus de la moiti´e.
Ces boˆıtes contiennent une taille totale t telle que :
t >
1
2
(b − 1) ≥ 1
2
(cid:100)2S(cid:101) ≥ 1
2
2S = S.
Donc t > S, ce qui est absurde puisque la taille totale des objets est S. Il y a donc contradiction
et le nombre de boˆıtes utilis´ees par l’heuristique Fischer-Price n’est jamais strictement sup´erieur
`a (cid:100)2S(cid:101).
(b) On note de nouveau b le nombre de boˆıtes utilis´ees par l’heuristique. On note ti la taille du contenu
de la ie boˆıte, c’est-`a-dire la somme des tailles des objets contenus dans cette boˆıte. La taille totale
Publicité
b
i=1 ti.
des objets (S) est bien sˆur ´egale `a la somme des tailles contenues dans les boˆıtes : S =
(cid:80)
Vu la question pr´ec´edente, au maximum une boˆıte peut ˆetre remplie `a moins de la moiti´e. Deux
cas de figure se pr´esentent :
1
i. Aucune boˆıte n’est moins qu’`a moiti´e remplie. Par cons´equent toutes les boˆıtes sont remplies
strictement plus qu’`a moiti´e et pour tout i ∈ [1, b], ti > 1
2 . D’o`u :
S =
b
(cid:88)
i=1
ti > b
1
2
⇒ b < 2S.
2 et pour tout i ∈ [2, b], ti > 1
ii. Exactement une boˆıte est remplie a moins de la moiti´e. Supposons qu’il s’agit de la premiere :
t1 ≤ 1
2 . On suppose, sans perte de g´en´eralit´e, que la deuxi`eme
boˆıte est celle, parmi les b − 1 boˆıtes remplies strictement plus qu’`a moiti´e, dont le contenu
est le plus petit : t2 = min2≤i≤b ti. On remarque que l’on a : t1 + t2 > 1 : sinon l’heuristique
Publicité
aurait utilis´e les objets d’une des deux boˆıtes pour compl´eter l’autre au lieu d’utiliser une boˆıte
de plus. On tire de ce qui pr´ec`ede :
S =
b
(cid:88)
i=1
ti = t1 +
b
(cid:88)
i=2
ti ≥ t1 + (b − 1)t2 = (t1 + t2) + (b − 2)t2 > 1 + (b − 2)
1
2
=
1
2
b.
On retrouve de nouveau : b < 2S.
Dans les deux cas on a montr´e l’in´egalit´e : b < 2S, d’o`u l’on peut tirer : b < (cid:100)2S(cid:101) en majorant le
membre droit par sa partie enti`ere. On peut trouver une borne plus fine en remarquant que b est
entier et que le plus grand entier inf´erieur ou ´egal `a 2S est (cid:98)2S(cid:99), ce qui nous donne la borne :
b ≤ (cid:98)2S(cid:99).
4. ´Etablir une borne ´egale `a deux pour l’heuristique Fischer-Price.
Soit b le nombre de boˆıtes utilis´ees par l’heuristique Fischer-Price et soit b∗ le nombre de boˆıtes d’une
Publicité
solution optimale. On doit donc montrer que b ≤ 2b∗. Or on sait que b ≤ (cid:100)2S(cid:101) et que (cid:100)S(cid:101) ≤ b∗. Il nous
suffit donc de montrer que (cid:100)2S(cid:101) ≤ 2(cid:100)S(cid:101). Or, par d´efinition : S ≤ (cid:100)S(cid:101). Or :
S ≤ (cid:100)S(cid:101) ⇒ 2S ≤ 2(cid:100)S(cid:101) ⇒ (cid:100)2S(cid:101) ≤ 2(cid:100)S(cid:101).
Par cons´equent :
b ≤ (cid:100)2S(cid:101) ≤ 2(cid:100)S(cid:101) ≤ 2b∗.
5. Donnez une impl´ementation de l’heuristique Fischer-Price.
Fischer-Price(s)
b ← 0
Pour i ← 1 `a n faire
j ← 1
tant que j ≤ b et si + taille[j] > 1 faire j ← j + 1
si j ≤ b
alors taille[j] ← taille[j] + si
sinon b ← b + 1
taille[b] ← si
6. Quelle est la complexit´e de votre heuristique ?
La premi`ere boucle comporte n it´erations, et la boucle ¡¡ tant que ¿¿ en compte au plus (cid:100)2S(cid:101) vu ce qui
pr´ecede. D’ou une complexit´e en O(nS). (On peut aussi remarquer que S ≤ n, car dans le pire cas il
faut une boˆıte par objet, et obtenir une complexit´e en O(n2))
2