La ronda de prueba de Google Hash Code 2015 ( enunciado del problema ) preguntó sobre el siguiente problema:
- entrada: una cuadrícula con algunos cuadrados marcados, un umbral , un área máximaT ∈ N A ∈ N
- salida: la mayor área total posible de un conjunto de rectángulos disjuntos con coordenadas enteras en tal que cada rectángulo incluye al menos cuadrados marcados y cada rectángulo tiene un área de, como máximo, .T A
En la terminología de Google, la cuadrícula es una pizza, los cuadrados marcados son jamón y los rectángulos disjuntos son rebanadas.
Podemos reformular claramente este problema a un problema de decisión al agregar una entrada adicional y dejar que la respuesta sea "¿hay un conjunto de rectángulos disjuntos que satisfagan las condiciones cuya área total es al menos cuadrados". n
Mi pregunta: si bien el problema de Google pedía a los candidatos que encontraran una solución "lo mejor posible" para el problema de cálculo en una instancia específica, creo que es probable que el problema general (en su formulación de la decisión) sea NP completo. Sin embargo, no puedo encontrar una reducción para mostrar la dureza NP. (La membresía NP es inmediata). ¿Cómo demostrar que este problema es NP-duro?
Siguen algunos ejemplos para ayudar a visualizar el problema. Considere la cuadrícula de por , con cuadrados marcados , y , representada gráficamente con para indicar cuadrados marcados:4 { 0 , 1 , 2 , 3 } × { 0 , 1 , 2 , 3 } ( 1 , 1 ) ( 0 , 2 ) ( 2 , 2 )X
..X.
.X..
..X.
....
Establezca (rectángulos de como máximo cuadrados) y (al menos un cuadrado marcado por rectángulo), una solución óptima (que cubre toda la cuadrícula) es tomar los siguientes rectángulos:6 T = 1
aaAa
bBcc
bbCc
bbcc
En la siguiente cuadrícula, con y :T = 2
XXX
.X.
...
No se puede hacer mejor que cubrir solo tres cuadrados:
AAA
.X.
...
o
XBX
.B.
.b.
(recuerde que los rectángulos en la partición no pueden superponerse).
Con otras personas analizando esta pregunta, probamos reducciones del empaque de contenedores, cubriendo problemas, 3-SAT y ciclos hamiltonianos, y no logramos que uno funcionara.