Box-in-a-Box-in-a-Boxing óptimo

Question

Inspirados por esta estrechamente relacionados con el problema, supongamos que tengo $n$ cuboide cuadros, todos con arbitrarias (posiblemente al azar) dimensiones finitas.

Para cualquiera de los dos cuadros, $B_1$ con dimensiones de $w_1,h_1,d_1$, e $B_2$ con dimensiones de $w_2,h_2,d_2$, suponemos que a $B_1$ puede caber dentro de $B_2$ fib $w_1 \leq w_2$$h_1 \leq h_2$$d_1 \leq d_2$. (Suponga que la orientación de cada caja se fija de modo que no hay rotaciones están permitidos.)

Llamamos a una serie de cajas embaladas uno dentro de otro (dentro de otro...), un "grupo". Nuestro objetivo es llevar nuestra serie de $n$ cajas en el menor número de grupos posible.

Mis preguntas son las siguientes:

1. Es este un problema conocido o una variante de un problema conocido, y si es así, cómo se llama?

2. ¿Existe (con prueba) un algoritmo polinomial en $n$ para la determinación de un grupo con un mínimo de embalaje de las cajas? Si no, ¿existe una prueba (asumiendo $P \neq NP$) que este tipo de algoritmo es posible?

Vale la pena señalar que el problema original se basa en el "libro de apilamiento" en dos dimensiones en lugar de tres, por lo tanto si la respuesta depende del número de dimensiones de la $\geq 2$, te agradecería un heads-up.

Muchas gracias.

Answer 1

Esto se puede hacer en el polinomio de tiempo para cualquier dimensión.

Asumir WLOG las cajas son distintos. Forma de un gráfico de la "encaja dentro" de la relación. Este es un gráfico acíclico dirigido. Cada grupo es un camino en este gráfico, y queremos partición de los vértices en tan pocos caminos como sea posible. Este es exactamente el problema de la ruta mínima de la cubierta en el gráfico acíclico dirigido. La página de la Wikipedia da una reducción Máxima Coincidente, que es el polinomio de tiempo.

Un pequeño tecnicismo es que una ruta de acceso de la cubierta puede tener las rutas de la reutilización de los vértices y no ser una partición, pero eso es fácil de solucionar, mediante la eliminación de vértices repetidos de todos, pero una ruta de acceso gracias al hecho de que el gráfico representa una relación transitiva.

Answer 2

Resulta que varios emprendedores señores discutiendo el problema original encontrado un modo demostrable óptimo $\mathcal{O}\left( n^2\right)$ algoritmo, que puede ser generalizado para el $p$-dimensional caso, $p \geq 3$ a través de Dilworth del teorema. Por lo tanto, este resuelve la pregunta 2.

La pregunta acerca de si esta caja-problema de agrupamiento o de otros similares a él tiene un nombre oficial todavía está abierta.