Problema de empaquetado de contenedores
La calculadora resuelve el problema del empaquetado de contenedores mediante diferentes algoritmos heurísticos. Creado a petición del usuario.
Esta calculadora trata sobre el problema de empaquetado de contenedores.
En otras palabras, hay un volumen fijo de contenedores y un conjunto de objetos de cualquier tamaño (por supuesto, el volumen de cada elemento individualmente menor que el volumen del contenedor). Se trata de empaquetar los objetos en el mínimo número de contenedores.
Hay otro ejemplo de la "vida": hay un conjunto de archivos (por ejemplo, películas) de diferentes tamaños. Se requiere copiar todas estas películas en el menor número de DVDs. Y así sucesivamente.
Se trata de un problema NP, lo que significa que para encontrar la solución óptima se necesita un listado completo. Sin embargo, existen algoritmos heurísticos para encontrar las soluciones adecuadas. Si tiene suerte, será óptima. :)
Aquí hay una calculadora y algoritmos descritos a continuación. Y por cierto, aunque en los datos por defecto algunas soluciones son las mismas, los algoritmos siguen siendo diferentes, y con otros datos serán diferencias notables.
Problema de empaquetado de contenedores
Conjunto de elementos para el empaquetado
| | | ||
|---|---|---|---|
Empecemos con el Algoritmo del Próximo Ajuste.
Algoritmo del Próximo Ajuste
En la mayoría de los casos, el algoritmo es muy aburrido y da los peores resultados de todos los algoritmos considerados.
La esencia del algoritmo es la siguiente:
- Tomar un nuevo elemento
- Tomar un nuevo contenedor.
- Poner el elemento en el contenedor.
- Tomar el siguiente elemento.
- Si el elemento cabe en el contenedor, vaya al paso 3. Si el elemento no cabe en el contenedor, vaya al paso 2.
Así que simplemente ponemos elementos en un contenedor, y si uno de ellos no cabe, tomamos un nuevo contenedor.
Es posible desarrollar un algoritmo mejor, pero este tiene un lado positivo: no requiere comprobar los contenedores anteriores. Puede ser útil si, por ejemplo, los contenedores nos llegan en una cinta transportadora.
Algoritmo del Primer Ajuste
La esencia del algoritmo es la siguiente:
- Tomar un nuevo elemento
- Tomar un nuevo contenedor.
- Poner el elemento en el contenedor.
- Tomar el siguiente elemento.
- Si el elemento cabe en un contenedor, vaya al paso 3. Si el elemento no cabe en el contenedor, compruebe los demás contenedores por orden. Si hay un contenedor con espacio suficiente, póngalo en el contenedor y vaya al paso 4. Si no, vaya al paso 2.
Es decir, poner un elemento en un contenedor, y si el elemento ya no cabe, tratar de encontrar un contenedor adecuado entre los ya parcialmente llenos. Si no encontramos un lugar, tomamos un nuevo contenedor.
Algoritmo del Peor Ajuste
La esencia del algoritmo es la siguiente:
- Tomar un nuevo elemento.
- Tomar un nuevo contenedor.
- Colocar el elemento en el contenedor.
- Tomar el siguiente elemento.
- Si el elemento cabe en un contenedor, vaya al paso 3. Si el elemento no cabe en un contenedor, tome un contenedor parcialmente lleno con el máximo espacio libre. Si el elemento cabe en un contenedor, ponga el elemento en el contenedor y vaya al paso 4. Si no, vaya al paso 2.
En resumen, se ponen los elementos en el contenedor, y si el elemento ya no cabe, se intenta ponerlo en el contenedor menos lleno. Si esto falla, tomamos un nuevo contenedor.
Algoritmo del Mejor Ajuste
La esencia del algoritmo es la siguiente:
- Tomar un nuevo elemento
- Tomar un nuevo contenedor.
- Poner el elemento en el contenedor.
- Tomar el siguiente elemento.
- Si el elemento cabe en un contenedor, vaya al paso 3. Si el elemento no cabe en un contenedor, tome un contenedor parcialmente lleno con un espacio mínimo pero en el que quepa el elemento. Si existe tal contenedor, vaya al paso 3. En caso contrario, vaya al paso 2.
En resumen, poner elementos en el contenedor, y si el elemento ya no es intermedio, trate de ponerlo en un contenedor lleno, pero donde todavía haya espacio suficiente para este elemento. Si falla, tomamos un nuevo contenedor.
Además, debo mencionar una variante con preclasificación decreciente - Primer Ajuste Decreciente, Mejor Ajuste Decreciente, etc. Es lo mismo, pero se eligen los elementos para empezar por el más grande. Por lo tanto, he revisado 8 algoritmos, pero la calculadora solo utiliza 4 - todos ellos son de preordenación porque proporcionan los mejores resultados.
Comentarios