Problème de bin packing
Le calculateur résout le problème de bin packing (conditionnement de bacs) selon différents algorithmes heuristiques.
Ce calculateur concerne les problèmes de bin packing (ou de conditionnement de bacs).
En d'autres mots, il y a des conteneurs de volume fixe et un ensemble d'objets de toute taille (bien sûr, le volume de chaque élément pris individuellement est plus petit que le volume du conteneur). Il faut conditionner les éléments dans le nombre minimal de conteneurs.
Il y e un autre exemple "vivant" - il y a un ensemble de fichiers (ex. films) de différentes tailles. Il est nécessaire de copier tous ces films sur le moins de DVD possibles. Et ainsi de suite.
Il y a un problème NP, ce qui signifie trouver la solution optimale pour une liste complète. Cependant, il y a des algorithmes heuristiques pour trouver les solutions appropriées. Si vous êtes chanceux, elle sera optimale :)
Voici le calculateur et les algorithmes sont décrits en-dessous. D'ailleurs, bien que les données par défaut et certaines solutions soient identiques, les algorithmes sont tous différents et avec d'autres données les différences seront notables.
Problème de bin packing
Ensemble d'éléments à conditionner
| | | ||
|---|---|---|---|
Commençons par l'algorithme du prochain ajustement.
Algorithme du prochain ajustement
Dans la plupart des cas, l'algorithme est très ennuyeux et donne les pires résultats de tous les algorithmes considérés.
L'essence de l'algorithme est comme suit :
- Prendre un nouvel élément.
- Prendre un nouveau conteneur.
- Mettre l'élément dans le conteneur.
- Prendre l'élément suivant.
- Si l'élément tient dans un conteneur, aller à l'étape 3. Si l'élement ne tient pas dans le conteneur, aller à l'étape 2.
Ainsi, nous mettons simplement les éléments sans ménagement dans un conteneur, si l'un d'eux ne tient pas, nous prenons un nouveau conteneur.
Il est possible de développer un meilleur algorithme, mais celui-ci a un avantage, il ne nécessite pas de vérifier les conteneurs précédents. Il peut être utile si, par exemple, les conteneurs nous arrivent sur un tapis roulant.
Algorithme du premier ajustement
L'essence de l'algorithme est comme suit :
- Prendre un nouvel élément.
- Prendre un nouveau conteneur.
- Mettre l'élément dans le conteneur.
- Prendre l'élément suivant.
- Si l'élément tient dans un conteneur, aller à l'étape 3. Si l'élément ne tient pas dans le conteneur, vérifier les autres conteneurs dans l'ordre. Si un conteneur a suffisamment de place, le mettre dans le conteneur et aller à l'étape 4, sinon aller à l'étape 2.
Soit, mettre un élément dans un conteneur et si l'élément ne tient plus, essayer de trouver un conteneur adapté parmi ceux partiellement remplis. Si nous ne pouvons pas trouver de place, nous prenons un nouveau conteneur.
Algorithme du pire ajustement
L'essence de l'algorithme est comme suit :
- Prendre un nouvel élément.
- Prendre un nouveau conteneur.
- Mettre l'élément dans le conteneur.
- Prendre l'élément suivant.
- Si l'élement tient dans un conteneur, aller à l'étape 3. Si l'élément ne tient pas dans un conteneur, prendre un conteneur partiellement rempli avec le maximum d'espace libre. Si l'élément tient dans un conteneur, le mettre dans le conteneur et aller à l'étape 4, sinon aller à l'étape 2
Pour résumer, mettre les éléments dans le conteneur et si l'élément ne tient plus, essayer de le mettre dans le conteneur le moins rempli. Si cela échoue, nous prenons un nouveau conteneur.
Algorithme du meilleur ajustement
L'essence de l'algorithme est comme suit :
- Prendre un nouvel élément.
- Prendre un nouveau conteneur.
- Mettre l'élément dans le conteneur.
- Prendre l'élément suivant.
- Si l'élement tient dans un conteneur, aller à l'étape 3. Si l'élément ne tient pas dans un conteneur, prendre un conteneur partiellement rempli avec le minium d'espace libre mais dans lequel l'élément tient toujours. S'il existe un tel conteneur, aller à l'étape 3, sinon aller à l'étape 2
Pour résumer, mettre les éléments dans le conteneur et si l'élement ne s'intercale plus, essayer de le mettre dans le conteneur le plus rempli ayant toujours assez d'espace pour cet élément. Si ceci échoue, nous prenons un nouveau conteneur.
Je dois également mentionner une variante avec un tri décroissant préalable - Premier ajustement décroissant, Meilleur ajustement décroissant, etc. Ceux sont les mêmes, mais les éléments sont choisis afin de commencer par le plus grand. Ainsi, j'ai revu 8 algorithmes, mais le calculateur n'en utilise que 4 - ils sont tous triés préalablement, car ils fournissent les meilleurs résultats.
commentaires