Algoritmos para mochila de dos y tres dimensiones

8

Sé que los problemas de la mochila 2D y 3D son NPC, pero ¿hay alguna forma de resolverlos en un tiempo razonable si las instancias no son muy complicadas? ¿Funcionaría la programación dinámica?

Por mochila 2D (3D) quiero decir que tengo un cuadrado (cubo) y una lista de objetos, todos los datos están en centímetros y tienen como máximo 20 m.

algorithms complexity-theory np-complete computational-geometry knapsack-problems Anónimo
fuente
1
¿Qué formas tienen tus objetos? Qué tan grande es el área circundante; tiene tamaño limitado?
Raphael
¿Está buscando un solucionador exacto o son suficientes las heurísticas?
stefan
1
¿Podrías ser más específico? ¿Qué son los "tamaños" y qué es m ? ¿Cuál es exactamente su aporte, cuáles son exactamente sus limitaciones y qué es exactamente lo que está tratando de optimizar?
JeffE
1
Además, ¿qué has probado ya?
JeffE
44
El problema del que estás hablando generalmente no se conoce como un problema de mochila; Por lo general, se conoce con el nombre de problema de empaquetado y debería poder encontrar mucha más información al respecto con ese nombre.
Steven Stadnicki

Respuestas:

1

Knapsack puede ser resuelto por programación dinámica en pseudo-polinomio tiempo con el número de objetos y el tamaño de la mochila. Por lo tanto, siempre que su contenedor sea pequeño (numéricamente), puede resolver el problema de manera eficiente. Tenga en cuenta que puede ajustar cambiando la resolución; no es necesario medir un contenedor de envío por µm, pero los medidores probablemente sean gruesos (dependiendo de sus objetos).O(nW)nWW

La mochila también se puede aproximar arbitrariamente bien en tiempo polinómico (ver esquemas de aproximación de tiempo polinómico ).

Sin embargo, la mochila solo considera los números adecuados en otro número; No le importa la geometría. Si necesita "rompecabezas", necesita otro problema; considerando Tetris, esto es probablemente mucho más difícil que la mochila .

Rafael
fuente
0

GREEDY siempre encontrará una solución razonable, pero no necesariamente la óptima. Simplemente coloque el objeto más grande que quepa cada vez en la mochila. Detente cuando no quepan más objetos.

salsaman
fuente
No, eso no es verdad. Tenga en cuenta que en el problema Mochila, los objetos también tienen valores. Llenar con avidez por tamaño puede dar una solución arbitrariamente mala.
Raphael
@Raphael: Bueno, no es arbitrariamente malo, pero no consideraría la solución codiciosa como una solución razonable . El enfoque codicioso empeora para los análogos dimensionales superiores.
A.Schulz
@ A.Schulz En realidad sí arbitrariamente malo! Se puede demostrar fácilmente que la heurística codiciosa de la mochila, que usa tamaño o bang-for-buck, no tiene ninguna garantía de aproximación finita a OPT.
Aaron
Gente ... por favor, dejen de decir "¡Bueno, no sé sobre eso! Pero ..." antes de hacer su % # $ ( tarea en él!
MickLH