Comment faire tenir au mieux mes affaires dans ces cartons ?

© Thomas Perkins – Fotolia.com

Je viens de passer mon bac et je vais commencer mes études supérieures – en informatique, bien sûr ! Comme il n’y a pas d’université dans ma petite ville, je vais devoir déménager. Autrement dit, je vais devoir emballer tout ce qui se trouve dans mes armoires et sur mes étagères dans des cartons de déménagement. Pour limiter les frais, je m’efforcerai d’utiliser le moins de cartons possible pour ranger mes affaires.

Si je retirais toutes mes affaires successivement des étagères et que je remplissais les différents cartons au fur et à mesure, je risquerais de gaspiller beaucoup de place. En effet, ces objets ont des tailles et des formes différentes, il resterait donc beaucoup d’espace vide dans les cartons.

Je parviendrais sans doute à la solution optimale, c’est-à-dire à utiliser le nombre minimal de cartons, si j’essayais toutes les possibilités l’une après l’autre. Mais j’ai beaucoup d’affaires, il me faudrait une éternité et ma chambre se transformerait vite en un véritable capharnaüm.

Je préfère donc placer les objets les uns après les autres dans les cartons, dans l’ordre où ils me tombent sous la main quand je les enlève des armoires et des étagères. Si je procède de cette façon, la question qui se pose est alors de savoir combien il me faudra de cartons supplémentaires par rapport à la solution optimale. Pour le trouver, analysons ce problème, connu sous le nom de bin packing.

Déménager pour pas cher, un problème « en ligne »

Comme je veux enlever mes affaires l’une après l’autre des armoires ou des étagères pour les emballer immédiatement, je me trouve face à un problème « en ligne ». Un problème « en ligne » se distingue d’un problème « hors ligne » par les caractéristiques principales suivantes :

• Les données pertinentes (ici : la taille des divers objets) ne sont pas connues au départ, elles se dévoilent au fil du temps. La liste de ces tailles, dans l’ordre de leur apparition, est désignée ci-dessous par le symbole σ.
• Il n’y a pas d’informations disponibles sur les données futures (ici : les dimensions des objets qui n’ont pas encore été déplacés).
• La quantité des données à traiter (ici : le nombre d’objets à emballer) n’est pas connue d’avance.
• La demande courante nécessite un traitement immédiat (ici : les objets ne sont pas laissés provisoirement de côté avant d’être placés dans un carton).

Dans la réalité, je peux avoir à l’avance une idée du volume de certains objets. J’ai en effet vécu plusieurs années dans cet appartement, je sais donc ce qui se trouve sur les étagères et dans les armoires. Mais je propose de ne pas en tenir compte ici, et d’examiner le problème dans le cas général.

Voici comment représenter ma stratégie d’emballage par un algorithme en ligne, dont l’entrée est la liste des volumes des objets à emballer, et la sortie, le nombre de cartons de déménagement nécessaires.

Algorithme NextFit

1. Ouvre un carton.
2. Procède de la façon suivante pour chaque élément de la liste :
3.     S’il n’y a plus de place dans le carton en cours d’examen pour l’objet en question,
4.         ferme le carton, ouvres-en un nouveau
5.     Emballe l’objet dans le carton ouvert.

En réfléchissant un peu, je pourrais modifier ma stratégie de la façon suivante. Si je décide d’attendre la fin pour fermer définitivement les cartons, au moment d’emballer un objet, je pourrai commencer par vérifier s’il reste suffisamment de place dans les cartons déjà entamés. Cette procédure présente un avantage : si je dois entamer un nouveau carton pour un objet très volumineux, puis emballer une série d’objets plus petits, je pourrai placer ceux-ci dans un carton déjà entamé.

Cette deuxième stratégie se présente sous la forme de l’algorithme en ligne suivant.

Algorithme FirstFit

1. Procède de la façon suivante pour chaque élément de la liste :
2.     Passe en revue tous les cartons entamés et vérifie :
3.     S’il y a encore de la place dans le carton en cours pour l’objet en question,
4.         place-le à l’intérieur et
5.         continue avec l’objet suivant (passe à l’étape 2).
6.     Emballe l’objet dans un nouveau carton.

Analyse des algorithmes

Pour simplifier l’analyse et la comparaison du résultat de mes stratégies, j’ai simplifié le problème en partant du principe qu’un objet peut tenir dans un carton de déménagement si le volume encore libre dans ce carton est supérieur ou égal à celui de l’objet à emballer. Je ne tiens donc pas compte de la forme des objets, qui pourrait laisser des espaces vides dans les cartons en raison des « découpes ». Je choisis ensuite l’unité de volume de façon à ce que la capacité globale des cartons de déménagement soit égale à 1. La taille des objets à emballer est alors inférieure ou égale à 1.

Pour nous faire une idée de la validité du résultat de ces algorithmes en ligne, examinons quelques exemples. Sur l’applet ci-dessous, nous vous proposons de tester quatre exemples. Vous pouvez aussi lancer la simulation avec des objets aléatoires.

Pour accéder à l’applet Java, autorisez les applets du domaine https://interstices.info. Si votre navigateur n’accepte plus le plug-in Java, mais que Java est installé sur votre ordinateur, vous pouvez télécharger le fichier JNLP, enregistrez-le avant de l’ouvrir avec Java Web Start.

Si tous les objets sont de taille identique – comme dans l’exemple 1 – les deux algorithmes NextFit et FirstFit fournissent un résultat optimal.

Exemple 1 : σ = (1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4)
NextFit = FirstFit : 5 cartons

Pour l’exemple 2, NextFit et FirstFit fournissent encore tous les deux un résultat optimal.

Exemple 2 : σ = (1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8)
NextFit = FirstFit : 5 cartons

L’exemple 3 montre toutefois que l’ordre des objets est susceptible d’influencer le résultat – dans ce cas, NextFit donne de loin la plus mauvaise solution.

Exemple 3 : σ = (1/2, 1/8, 1/2, 1/8, 1/2, 1/8, 1/2, 1/8, 1/2, 1/8, 1/2, 1/8, 1/2, 1/8, 1/2, 1/8)
NextFit : 8 cartons	FirstFit : 5 cartons

Si on choisissait un nombre beaucoup plus petit que 1/8 dans l’exemple 3, c’est presque la moitié de chaque carton qui resterait vide avec l’algorithme NextFit. NextFit utilise, dans des cas extrêmes, pratiquement deux fois plus de cartons de déménagement qu’il n’en faudrait pour un emballage optimal.

L’algorithme FirstFit s’est avéré meilleur que l’autre dans l’exemple 3. Il existe cependant des cas où FirstFit est aussi loin de fournir la solution optimale, comme le montre l’exemple 4.

Exemple 4 : σ = (0.15, 0.15, 0.15, 0.15, 0.15, 0.15, 0.34, 0.34, 0.34, 0.34, 0.34, 0.34, 0.51, 0.51, 0.51, 0.51, 0.51, 0.51)
FirstFit : 10 cartons	Solution optimale : 6 cartons

On obtient ici un rapport de 10/6 pour FirstFit par comparaison avec l’emballage optimal, c’est-à-dire que FirstFit nécessite 1,67 fois plus de cartons de déménagement. On dit que le facteur de compétitivité de cet algorithme est ici de 1,67. En général, un algorithme en ligne a un facteur de compétitivité k si on n’a jamais besoin d’un nombre de cartons supérieur à k fois celui qu’il aurait fallu si l’on avait su ce que l’avenir nous réservait.

La question se pose maintenant de savoir si les exemples négatifs 3 et 4 représentent les pires cas possibles pour NextFit ou FirstFit, ou si la situation peut encore s’aggraver. Pour calculer le facteur de compétitivité de NextFit, nous partons du constat que le volume global des objets placés dans deux cartons contigus est supérieur à celui d’un seul carton (si ce n’était pas le cas, NextFit n’aurait pas réparti les objets dans deux cartons). Par conséquent, chaque carton est en moyenne plus qu’à moitié plein, son facteur de compétitivité ne peut donc pas être pire que 2. Il est en fait bien égal à 2.

L’algorithme en ligne NextFit a donc un facteur de compétitivité de 2. Comme cette preuve peut également s’appliquer à FirstFit, le facteur de compétitivité de cet algorithme est lui aussi au plus égal à 2. Une démonstration nettement plus compliquée, que nous ne présenterons pas ici, permet de prouver que FirstFit a un facteur de compétitivité de 1,7.

Ces algorithmes en ligne sont-ils bien adaptés au problème du bin packing ?

Nous connaissons maintenant les facteurs de compétitivité des algorithmes NextFit et FirstFit, nous savons donc qu’il existe des cas pour lesquels le résultat est en pratique plus mauvais que la solution optimale selon un facteur de 2 ou de 1,7. D’un côté, il s’agit d’un résultat intéressant, car nous savons que l’espace gaspillé dans les cartons de déménagement ne dépassera jamais ce facteur déterminé, mais d’un autre côté, ce résultat est un peu décevant, car la différence de prix entre un déménagement à 1 000 EUR et un à 2 000 EUR (ou 1 700 EUR) peut faire mal !

Pour déterminer maintenant si ces stratégies d’emballage sont effectivement bonnes ou mauvaises, il faut s’intéresser au meilleur algorithme en ligne qui s’applique à ce problème. Comme la liste des données d’entrée n’est pas connue d’avance, il pourrait bien s’avérer impossible de créer un algorithme en ligne qui donne un résultat optimal à tous les coups. On peut démontrer que cela est effectivement le cas. Il suffit de considérer qu’un algorithme en ligne dont le facteur de compétitivité est de c doit présenter le même facteur de compétitivité c pour chaque liste partielle. Prenons une liste de données d’entrée composée d’une série d’objets de taille légèrement inférieure à 1/2, suivie d’un nombre égal d’objets de taille légèrement supérieure à 1/2 (en s’assurant que la somme des deux tailles ne dépasse pas 1). Dans la solution optimale, chaque carton contiendra à la fois un des objets les plus petits et un des objets les plus gros. Mais le même algorithme en ligne ne peut pas fournir la solution optimale pour la liste partielle qui ne se compose que de la première moitié de la liste totale. En effet, on obtient alors la solution optimale en plaçant deux des objets de taille inférieure à 1/2 dans chaque carton. Comme on ne sait pas d’avance si des objets plus volumineux sont encore à venir, ni combien, aucun algorithme en ligne ne peut donner un résultat optimal dans les deux cas.

En poursuivant ce raisonnement, nous obtenons le résultat suivant :
Aucun algorithme en ligne pour le problème du bin packing ne peut avoir un facteur de compétitivité meilleur que 4/3.

Comme il n’est pas possible d’avoir un algorithme en ligne dont le facteur de compétitivité serait meilleur que 4/3, l’algorithme FirstFit, avec son facteur de compétitivité de 1,7, se présente maintenant sous un nouveau jour.

Qui vient m’aider à remplir mes cartons ?

Une application informatique du bin packing concerne la copie de fichiers sur des CD (dans le cadre d’une sauvegarde de données). Dans cet exemple, les stratégies décrites ci-dessus sont directement applicables. La forme des objets et leurs « découpes » éventuelles n’ont en effet pas de sens dans le cas de données numériques et les hypothèses simplificatrices que nous avons faites sont donc totalement justifiées.

Une première version de ce document est parue en allemand dans la série Algorithmus der Woche publiée à l’occasion de l’Année de l’informatique (Informatikjahr) 2006.
L’applet a été réalisée par Régis Monte pour Interstices.