- Objet en cours de rangement
- Rentre
- Ne rentre pas
Problème de bin packing
Des cartons dans des camionnettes, des fichiers sur des disques, des tâches sur des machines : le problème de bin packing demande comment ranger une liste d'objets dans le moins possible de boîtes identiques. On ne connaît aucune méthode rapide qui trouve toujours le meilleur rangement, mais des règles simples s'en approchent. Choisissez une règle, suivez-la pas à pas et comparez avec la réponse exacte. Touchez un objet sur l'étagère, puis touchez une boîte pour l'y mettre : les boîtes vertes ont de la place pour lui, et Nouvelle boîte en ouvre une autre. Touchez un objet dans une boîte pour le ressortir. Rangez tous les objets dans le moins de boîtes possible ; la borne inférieure (le poids total divisé par la taille des boîtes, arrondi au-dessus) et le minimum possible montrent à quel point vous êtes proche du but, et Minimum de boîtes montre le meilleur rangement. Modifiez les poids des objets (en kilogrammes) et la taille des boîtes dans le panneau. La vue Pas à pas montre comment rangent les règles rapides : Next Fit, First Fit ou Best Fit, avec les objets dans l'ordre saisi ou triés du plus grand au plus petit, ou la réponse exacte trouvée par la programmation dynamique. Appuyez sur Lecture pour voir les objets entrer dans les boîtes, ou sur Étape et Retour pour avancer pas à pas, et faites glisser le curseur des étapes pour aller n'importe où. Quand la zone de jeu est sélectionnée, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Touchez un objet, puis une boîte où il reste de la place pour l'y mettre, ou Nouvelle boîte pour en ouvrir une autre.
- Essayez d'utiliser le moins de boîtes possible, ou appuyez sur Minimum de boîtes pour voir le meilleur rangement.
- Ouvrez la vue Pas à pas, choisissez une règle et appuyez sur Lecture pour voir chaque objet essayer les boîtes.
Les règles
Next Fit ne garde ouverte que la dernière boîte : un objet qui n'y rentre pas commence une nouvelle boîte. First Fit essaie les boîtes à partir de la première et prend la première où il reste de la place. Best Fit essaie toutes les boîtes et prend la plus pleine où il reste de la place, ce qui laisse le moins d'espace inutilisé. First Fit et Best Fit peuvent aussi trier d'abord les objets du plus grand au plus petit, ce qui donne First Fit Decreasing et Best Fit Decreasing.
La réponse exacte
La dernière règle n'est pas une règle approximative : elle trouve le plus petit nombre de boîtes par programmation dynamique sur les ensembles d'objets. Pour chaque ensemble d'objets, elle retient le plus petit nombre de boîtes qui les contiennent et, parmi les rangements avec ce nombre de boîtes, la plus petite charge dans la dernière boîte. Un ensemble grandit d'un objet à la fois, qui soit complète la dernière boîte, soit en ouvre une nouvelle. Avec n objets, il y a 2ⁿ ensembles, c'est pourquoi l'application accepte au plus 12 objets. La borne inférieure, c'est-à-dire la taille totale divisée par la taille des boîtes et arrondie au-dessus, montre à quel point un rangement est proche du meilleur.
Questions fréquemment posées
Quelle règle de bin packing est la meilleure ?
Parmi les règles rapides, First Fit Decreasing et Best Fit Decreasing sont les plus performantes : elles n'utilisent jamais plus de 11/9 du nombre minimal de boîtes, plus une petite constante. First Fit et Best Fit sur des objets non triés restent sous 1,7 fois le nombre minimal de boîtes, et Next Fit sous 2 fois.
Pourquoi le bin packing est-il difficile ?
Décider si les objets tiennent dans seulement deux boîtes, c'est déjà le problème de partition, qui est NP-complet. Donc, sauf si P = NP, aucune méthode ne trouve rapidement le plus petit nombre de boîtes pour toutes les entrées, et les méthodes exactes prennent un temps exponentiel dans le pire des cas.
Qu'est-ce que la borne inférieure ?
La taille totale des objets divisée par la taille des boîtes, arrondie au-dessus. Aucun rangement ne peut utiliser moins de boîtes, car les boîtes doivent contenir tous les objets. Souvent, le meilleur rangement l'atteint, mais pas toujours : trois objets de taille 6 avec des boîtes de 10 ont une borne inférieure de 2 et demandent 3 boîtes.
Est-ce de la programmation dynamique ?
La réponse exacte, oui : elle construit le meilleur rangement de chaque ensemble d'objets à partir des meilleurs rangements d'ensembles plus petits. Les règles rapides sont des méthodes gloutonnes, qui décident une fois pour toutes et ne reviennent jamais en arrière.
Des données sont-elles envoyées quelque part ?
Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur