Algoritmo de empaque de bandejas 3D

Estoy buscando una implementación determinista para cualquier algoritmo de empaque de bandejas 3d, es decir, para empaquetar muchos cuboides pequeños y diferentes dentro de uno o muchos más grandes. La solución puede variar de la óptima.Algoritmo de empaque de bandejas 3D

Debe escribirse en C, C++, Java, C#, IronPython, IronRuby o en cualquier otro idioma desde el que se pueda acceder desde el código .Net.

Encontré este algoritmo C http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c, pero no gira los cuboides para encontrar el mejor ajuste. Estoy de acuerdo con no rotarlos al revés, pero la rotación horizontal debería ser posible.

Fuente

2009-10-13 Mouk

@Mouk: ¿Es esta tarea? – Asaph

Usted afirma que está buscando un algoritmo, pero luego enumera los lenguajes de programación. ¿Estás buscando un algoritmo genérico o una implementación? –

¿Desea la solución óptima, o una que sea bastante buena? ¿Son los cuboides todos iguales? Cuando dices rotación, ¿te refieres a 90 grados o a cualquier ángulo? – Beta

He escrito un algoritmo aproximado para el caso que describe, es decir, recuadros rectangulares en 3D, con rotación ortogonal, en C++. puede encontrar los resultados y el algoritmo en el documento publicado: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

Fuente

2010-04-19 14:55:29 user320450

¿La aplicación fuente o C++ está disponible en línea en cualquier lugar? –

Esto es bueno para una solución simple pero realmente no funciona tan bien. Para cualquiera que desee una explicación y ayuda para escribir uno, sugiero este libro: Knapsack Problems, por Martello y Toth, ISBN: 0471924202 – ars265

Este problema es NP-hard. Su mejor apuesta es un algoritmo de aproximación (hasta que una persona genio resuelva cualquier problema de NP, o un tipo muy afortunado tropiece con una solución.) Desafortunadamente, no conozco ningún algoritmo de aproximación conocido para este problema.

Fuente

2009-10-16 22:51:16 ldog

Resolver un problema NP-complete en tiempo polinomial aún no le dará una solución de polinomio para problemas NP-duros :) –

Convertí wknechtel/3d-bin-pack código C para javascript. Puede ser fácilmente puerto a C#.

https://github.com/keremdemirer/3dbinpackingjs

Puede ejecutar ejemplos de cálculo de index.html archivo y revisar el informe generado. El archivo pack1.js contiene la aplicación y el algoritmo. No estoy seguro de cómo funciona el algoritmo, pero los resultados son satisfactorios para los cálculos de embalaje.

Fuente

2016-02-27 23:10:46

Algoritmo de empaque de bandejas 3D

Respuesta

Cuestiones relacionadas