Rejilla cubierta por rectángulos

Tenemos una cuadrícula . Tenemos una colección de rectángulos en esta rejilla, cada rectángulo se puede representar como un -by- binario matriz . Queremos cubrir la cuadrícula con esos rectángulos. $N_1 \times N_2$ $N_1$ $N_2$ $R$

¿La versión de decisión de este conjunto cubre el problema NP-completo?

Entrada: Colección de rectángulos en la cuadrícula (tamaño de entrada: ) y $\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ $N_1N_2L$ $K \in \mathbb{N}^+$
Salida: Subconjunto con y contienen para cada celda al menos un rectángulo que lo cubre. $\mathcal{S}\subset\mathcal{C}$ $|\mathcal{S}|\leq K$ $\mathcal{S}$

Descubrí que el caso 1D ( ) se puede resolver en tiempo polinómico mediante programación dinámica: cualquier cobertura óptima será la unión de $N_2=1$

Una cobertura óptima para algunos subproblemas de cubrir las primeras celdas . $N_1-n_1$
un rectángulo 1D, es decir, un intervalo, que cubre las celdas restantes . $n_1$

Sin embargo, no creo que DP pueda funcionar para el problema 2D: para el problema 1D, tiene un subproblema para resolver, pero para el 2D tiene subproblemas (número de celosía Nordeste caminos en la cuadrícula). $N_1$ $\binom{N_1+N_2}{N_2}$

Creo que el problema podría ser NP, pero no estoy seguro (aunque parece más difícil que P), y no he logrado encontrar una reducción polinómica de un problema NP completo (3-SAT, cubierta de vértice, ...)

Cualquier ayuda o sugerencia es bienvenida.

complexity-theory np-complete set-cover Yann
fuente

Sugerencia: busque una reducción de Vertex Cover, en la que creamos unaporcuadrícula de bloques, cada uno de los cuales es un bloque de 3 por 3 de elementos de matriz. Cada fila de bloques corresponde a un borde y contendrá 2 bloques especialmente diseñados que corresponden a sus vértices de punto final. Para cada vértice habrá una altura-, rectángulo ancho-1 que pasa a través de la columna central de la columna de bloques de 3 por 3 correspondientes a ese vértice. ¿Cómo puede forzar que el total de cualquier cobertura válida de vértices cueste exactamente ? (Necesitará otros rectángulos).

| E |

$|E|$

| V |

$|V|$

3 | E |

$3|E|$

k

$k$

| E | (| V | + 3) + k

$|E|(|V|+3)+k$

j_random_hacker

Creo que este es probablemente un ejercicio de tarea, por lo que soy un poco reacio a decir mucho más que eso por ahora. La fórmula del costo que di tiene algunas pistas. Tenga en cuenta que puede forzar al menos 1 de varios rectángulos convirtiéndolos en los únicos rectángulos que cubren algún elemento de la matriz (el caso especial de 1 rectángulo también es útil). FWIW, también intenté usar un-por-primero la cuadrícula, donde elegir un vértice correspondería a "tachar" una fila y la columna correspondiente, pero no pudo encontrar la manera de forzar la -ésima columna a ser elegida cuando se elige la -ésima fila o viceversa.

| V |

$|V|$

| V |

$|V|$

i

$i$

i

$i$

j_random_hacker

Tuve el mismo problema con-por-cuadrícula. Creo que veo qué tipo de solución tiene en mente (aunque no tengo exactamente la misma fórmula de costo), vea mi edición. Por cierto, no es un ejercicio de tarea. Es un problema combinatorio que apareció en un problema de ingeniería de la vida real. Lo resolvemos con MIP, pero quería estar seguro de que el problema era NP (y no tenía solución polinómica). En cualquier caso, si confirma que la solución es válida, puede poner su sugerencia como respuesta y la validaré (ya que encontré la solución con su ayuda).

| V |

$|V|$

| V |

$|V|$

Yann

Sí, esa es casi exactamente la reducción que tenía en mente. :) Hice sus rectángulos "tipo 4" un poco más largos en un extremo: donde los suyos ocupan 2 celdas dentro de un bloque, el mío ocupa los 3. En lugar de rectángulos especiales "tipo 3" para los bloques finales, utilizo toda la fila superior, solo como rectángulos de "tipo 2" para . Finalmente tengo un rectángulo que ocupa las celdas centro-izquierda e inferior-izquierda dentro de cada bloque final izquierdo (volteado horizontalmente para cada bloque final derecho). Por lo tanto, puede cubrir las 2 filas inferiores de todos los bloques, incluidos y entre los bloques finales, utilizando un patrón o .

a < j < b

$a < j < b$ |==|

j_random_hacker

Me gusta tu-por-idea de reducción Con esto, a diferencia del-por-reducción, puede haber soluciones de costo mínimo que no corresponden a las cubiertas de vértices, pero todas esas soluciones pueden convertirse en soluciones de costo igual (mínimo) utilizando el mismo argumento que en su último punto, así que esto no es un problema para la reducción :)

| E |

$|E|$

3 | V |

$3|V|$

3 | E |

$3|E|$

3 | V |

$3|V|$

j_random_hacker

Gracias a la sugerencia de j_random_hacker, he encontrado una solución para reducir la cubierta de vértices al problema de la cuadrícula:

Hacemos un -por- cuadrícula de bloques de 3 por 3, es decir, un -por- cuadrícula, con vértices ordenados como columnas y bordes ordenados como filas . Construiremos rectángulos en esta cuadrícula (el dibujo a continuación ayudará mucho a comprender los diferentes rectángulos utilizados) $|E|$ $|V|$ $3|E|$ $3|V|$ $\{v_1,\dots,v_{N_1}\}$ $\{e_1,\dots,e_{N_2}\}$

$|V|$

$(e_i,v_j)$ $e_i=(v_a,v_b)$

$j<a$ $b<j$
$j=a$ $j=b$
$a<j<b$

$|E||V|$

$(e_i,v_a)$ $(e_i,v_b)$

$(e_i,v_a)$ $(e_i,v_b)$

$2|E|$

Ahora, para cada borde construimos rectángulos de tipo 4, entre los bloques finales, tenemos dos rectángulos para la segunda fila:

Uno va desde el cuadrado central del primer bloque al cuadrado central izquierdo del segundo bloque.
Uno va desde el cuadrado central derecho del primer bloque al cuadrado central del segundo bloque.
Y los mismos dos rectángulos para la tercera fila.

$4|E|$

Entonces, para cubrir la grilla:

$|E|(|V|+2)$ $|V|+4|E|$

Para cubrir, para un borde dado, la parte entre los bloques finales del borde aún no cubiertos (segunda y tercera filas de la fila de bloques), podemos usar:

Los cuatro rectángulos de tipo 4.
un rectángulo de tipo 1 y dos rectángulos de tipo 4.

Tenga en cuenta que, en cualquier caso, necesitamos al menos dos rectángulos de tipo 4.

$|E|(|V|+4) + k$

$|E|(|V|+2)$
$|E|(|V|+4) + k$ $|E|(|V|+4) + k$

$|E|(|V|+6) + |V|$ $9|V||E|$

$|E|$ $3|V|$ $|V|+4|E|$ $3|E|+k$

Yann
fuente

Rejilla cubierta por rectángulos

Respuestas: