TD d’algorithmique avancée
Corrigé du TD 12 : Heuristique de rangement
Jean-Michel Dischler et Frédéric 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ède pas 1.
Ce problème est NP-complet. Pour le résoudre on utilise l’heuristique Fischer-Price : on prend les objets
l’un apres l’autre et un objet est placé dans la premiere boˆıte qui peut l’accueillir. On note S =
1. Montrez que le nombre optimal de boˆıtes nécessaires est au moins égal à (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 étant 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érieur ou égal à S).
2. Montrez que l’heuristique Fischer-Price laisse au plus une boˆıte remplie à moins de la moitié.
On raisonne par l’absurde et on suppose qu’il existe au moins deux boˆıtes, notées A et B, qui sont
remplies a moins de la moitié. Sans perte de généralités, on suppose que la boˆıte A a commencé a
être remplie avant la boˆıte B. Soit x le premier objet ajouté a la boˆıte B. La boˆıte B étant a la fin
de l’algorithme remplie à moins de la moitié et tous les poids étant positifs, x est de taille inférieure
a 1/2. A étant remplie a moins de la moitié à la fin de l’exécution de l’heuristique, et tous les poids
étant positifs, A était remplie a moins de la moitié quand x a été rajouté a B. Donc l’heuristique, vu sa
définition, a ajouté 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 à moins de la moitié.
3. Démontrez que le nombre de boˆıtes utilisées par l’heuristique Fischer-Price n’est jamais strictement
supérieur à (cid:100)2S(cid:101).
Deux corrections différentes : 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 à moins de
la moitié. Donc toutes les boˆıtes sauf au maximum une sont remplies strictement à plus de la
Publicité
moitié. Raisonnons une fois de plus par l’absurde. Supposons que le nombre de boˆıtes utilisées, b,
est strictement supérieur à (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écede, (au moins) b − 1 boˆıtes sont remplies strictement à plus de la moitié.
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ées par l’heuristique Fischer-Price n’est jamais strictement supérieur
à (cid:100)2S(cid:101).
(b) On note de nouveau b le nombre de boˆıtes utilisées par l’heuristique. On note ti la taille du contenu
de la ie boˆıte, c’est-à-dire la somme des tailles des objets contenus dans cette boˆıte. La taille totale
b
i=1 ti.
des objets (S) est bien sûr égale à la somme des tailles contenues dans les boˆıtes : S =
(cid:80)
Vu la question précédente, au maximum une boˆıte peut être remplie à moins de la moitié. Deux
cas de figure se présentent :
1
i. Aucune boˆıte n’est moins qu’à moitié remplie. Par conséquent toutes les boˆıtes sont remplies
strictement plus qu’à moitié et pour tout i ∈ [1, b], ti > 1
2 . D’où :
S =
b
Publicité
(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é. Supposons qu’il s’agit de la premiere :
t1 ≤ 1
2 . On suppose, sans perte de généralité, que la deuxième
boˆıte est celle, parmi les b − 1 boˆıtes remplies strictement plus qu’à moitié, dont le contenu
est le plus petit : t2 = min2≤i≤b ti. On remarque que l’on a : t1 + t2 > 1 : sinon l’heuristique
aurait utilisé les objets d’une des deux boˆıtes pour compléter l’autre au lieu d’utiliser une boˆıte
de plus. On tire de ce qui précède :
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.
Publicité
Dans les deux cas on a montré l’inégalité : b < 2S, d’où l’on peut tirer : b < (cid:100)2S(cid:101) en majorant le
membre droit par sa partie entière. On peut trouver une borne plus fine en remarquant que b est
entier et que le plus grand entier inférieur ou égal à 2S est (cid:98)2S(cid:99), ce qui nous donne la borne :
b ≤ (cid:98)2S(cid:99).
4. Établir une borne égale à deux pour l’heuristique Fischer-Price.
Soit b le nombre de boˆıtes utilisées par l’heuristique Fischer-Price et soit b∗ le nombre de boˆıtes d’une
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éfinition : 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équent :
b ≤ (cid:100)2S(cid:101) ≤ 2(cid:100)S(cid:101) ≤ 2b∗.
5. Donnez une implémentation de l’heuristique Fischer-Price.
Fischer-Price(s)
b ← 0
Pour i ← 1 à 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é de votre heuristique ?
La première boucle comporte n itérations, et la boucle ¡¡ tant que ¿¿ en compte au plus (cid:100)2S(cid:101) vu ce qui
précede. D’ou une complexité 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é en O(n2))
2