TD d’algorithmique avancée
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
Publicité
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 =
n
i=1 si.
(cid:80)
Publicité
1. Montrez que le nombre optimal de boˆıtes nécessaires est au moins égal à (cid:100)S(cid:101).
2. Montrez que 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).
4. Établir une borne égale à deux pour l’heuristique Fischer-Price.
5. Donnez une implémentation de l’heuristique Fischer-Price.
Publicité
6. Quelle est la complexité de votre heuristique ?