TD d’algorithmique avanc´ee
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
Advertisement
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 =
n
i=1 si.
(cid:80)
Advertisement
1. Montrez que le nombre optimal de boˆıtes n´ecessaires est au moins ´egal `a (cid:100)S(cid:101).
2. Montrez que l’heuristique Fischer-Price laisse au plus une boˆıte remplie `a moins de la moiti´e.
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).
4. ´Etablir une borne ´egale `a deux pour l’heuristique Fischer-Price.
5. Donnez une impl´ementation de l’heuristique Fischer-Price.
Advertisement
6. Quelle est la complexit´e de votre heuristique ?