algorithm - conquer - ¿Generalizando el algoritmo para el mosaico de dominó?

divide and conquer algorithm

Question

En esta pregunta anterior, el OP hizo el siguiente problema:

Dada una cuadrícula rectangular donde algunos cuadrados están vacíos y otros están llenos, ¿cuál es el mayor número de dominós 2x1 que se pueden colocar en el mundo de modo que no se superpongan dos dominós y no haya dominó encima de un cuadrado lleno?

La respuesta (¡muy hermosa!) A este problema reconoció que esto es equivalente a encontrar una coincidencia máxima de dos partidos en un gráfico especialmente construido. En este gráfico, cada cuadrado vacío tiene un nodo que está vinculado a cada uno de sus vecinos por un borde. Cada dominó corresponde entonces a un borde en el gráfico, de modo que sus puntos finales no están cubiertos por ningún otro borde. En consecuencia, cualquier conjunto de bordes que no compartan un vértice (un emparejamiento) corresponde a una disposición de dominós, y viceversa.

Mi pregunta es una generalización de esta anterior:

Dada una cuadrícula rectangular donde algunos cuadrados están vacíos y otros rellenos, ¿cuál es el mayor número de dominós M x N (para un M y N dados) que se pueden colocar en el mundo de manera que no se superpongan dos dominós y no haya dominó encima de una plaza llena?

No puedo ver cómo convertir esto en un problema coincidente como se hizo en el caso anterior. Sin embargo, tampoco veo ninguna razón en particular por la que este problema sea inmediatamente NP-duro, por lo que puede haber una solución polinómica de tiempo para el problema.

¿Existe un algoritmo eficiente para resolver este problema? ¿O alguien tiene una reducción que muestre que este problema es NP-difícil?

¡Muchas gracias!

Answer 1

A Keith:

¡Gran trabajo y grandes explicaciones! Sin embargo, escribí un programa para encontrar el máximo de techos, y descubrió un defecto. ¡Ojalá esto se pueda arreglar! [Actualización: Keith solucionó el problema!]

Por favor revise este enlace: http://pastebin.com/bABQmfyX (sus dispositivos analizados, además de un código fuente de c ++ muy útil)

El problema es que el gadget a continuación se puede combinar con 6 dominós:

y*** ***z
* *
***
***
*x*

-Tom Sirgedas

Answer 2

Este problema es definitivamente NP-duro y puedo probarlo. Hay una reducción de 3-SAT a este problema. Específicamente, es una reducción de 3-SAT al subproblema de este problema en el que las fichas de dominó son 1x3. También puede haber otras reducciones para otros tamaños específicos, pero este definitivamente funciona.

Esencialmente, en esta reducción, vamos a utilizar las posiciones de dominó para codificar verdadero o falso. Específicamente, adoptaré la misma notación que la otra solución, es decir, usaré asteriscos para indicar espacios abiertos en la cuadrícula. También usaré conjuntos de tres letras mayúsculas para representar dominós y minúsculas para representar "señales" que son espacios que pueden o no llenarse dependiendo del estado del sistema.

Para integrar un problema de 3 SAT en este espacio, necesitaremos un conjunto de lo que llamaré gadgets que solo permiten ciertos estados. La mayoría de estos dispositivos tendrán un número fijo de dominó en ellos. La excepción serán los dispositivos que representan las cláusulas que tendrán un dominó adicional si la cláusula es verdadera (satisfecha) pero no cuando es falsa (insatisfecha). Podemos interconectar estos gadgets utilizando rutas. Juntos, esto nos permitirá construir un circuito de 3 SAT. Tendremos un número base de dominós ya que cada ruta y cada gadget tomarán una cantidad estándar de dominós, podemos agregarlos hasta obtener un número base k y luego cada cláusula puede tener un dominó adicional si es verdad, así que si todos las cláusulas pueden hacerse verdaderas (y, por lo tanto, la expresión satisfecha) y hay n cláusulas, entonces el número máximo de dominós será n + k. Si no, el número máximo será menor que n + k. Esta es la forma básica de la reducción. A continuación describiré los gadgets y daré ejemplos.

Similar a la otra respuesta, vamos a tener dos posiciones que codifican verdadero y falso para una variable dada. Entonces, comenzaré con una sola ficha que puede estar en dos lugares posibles.

****

Esto puede ser cubierto con un dominó como

AAA* or *AAA

Obviamente, esto no puede cubrirse con 2 dominós y cubrirlo con 0 dominó nunca sería lo máximo. Para mis propósitos, vamos a considerar una protuberancia para representar el valor "falso" y una falta de protuberancia para representar "verdadera". Entonces podemos ver que esta parte lleva dos señales:

x**y

Y en este caso, solo se cubrirá uno de x o y, por lo que podemos considerar que las señales son x y las lógicas no de x. Para nuestros propósitos, lo que está cubierto es falso, lo que no está cubierto es verdadero. A continuación, podemos transmitir señales simplemente a través de rectas curvas rectas. Si tenemos

x*****y

Volveremos a tener exactamente dos dominós y daremos como resultado que se cubran xo y, pero no ambos.

***y
*
*
x

Tendrá exactamente el mismo comportamiento. Por lo tanto, podemos usar esto para crear rutas largas y curvas en longitudes con incrementos de 3. Sin embargo, no todas las longitudes que queremos usar son incrementos de 3, por lo que necesitamos un gadget adicional para recorrer una distancia diferente. A esto lo llamo el artilugio del violinista y su único propósito es mover la señal a distancias ligeramente desiguales para que las cosas se conecten con éxito. Su entrada proviene de x y la salida va a y y simplemente transmite la misma señal. Se parece a esto:

 ***y
*
**x

Siempre contiene exactamente dos fichas de dominó y se rellena de una de las dos formas siguientes:

 BBB* ABBB
* A
AAA *AX

Sin embargo, si vamos a modelar 3-SAT, necesitamos más que esto. Específicamente, necesitamos alguna forma de modelar las cláusulas. Para hacer esto, tenemos un gadget donde se puede incluir un dominó adicional si la cláusula es verdadera. La cláusula será verdadera cuando una o más de sus entradas sean verdaderas. En este caso, eso significa que podemos empaquetar un dominó adicional cuando al menos una de las entradas no sobresale. Se verá así:

*x*y*
*
z

Si agregamos un camino adicional a cada uno para mayor claridad, entonces se ve así:

 * *
* *
* *
*****
*
****

Si x, y, y z son todos falsos, entonces todos tendrán salientes y se llenarán así:

 A B
C D
C D
*C*D*
*
EEEF

Donde el resto de las fichas de dominó A, B y F continúan por un camino en alguna parte. Si al menos una de las entradas es verdadera, entonces podemos empaquetar en un dominó adicional (G) así:

 C B A D A B
C D C D C D
C D or C D or C D
GGGD* *CGGG *CGD*
* * G
EEEF EEEF GEEE

Sin embargo, incluso si todas las entradas son verdaderas, no podemos empaquetar más de un dominó. Ese escenario se vería así:

 C D
C D
C D
*****
*
*EEE

Y como puede ver, solo podemos insertar exactamente un dominó adicional en el espacio vacío, no dos.

Ahora, si los términos nunca se repitieran, entonces habríamos terminado (o casi a punto). Sin embargo, se pueden repetir, así que a continuación, necesitamos un divisor de señal para que una variable pueda aparecer en múltiples términos. Para ello, utilizamos el siguiente gadget:

y*** ***z
* *
***
***
x

En este gadget x es la entrada y y y z son las salidas. En este gadget, siempre podemos empacar 5 dominós. Si x sobresale del embalaje, 5 dominós siempre requerirán cubrir y y z también. Si x no sobresale, entonces no se requiere cubrir yz. El embalaje donde x no sobresale se ve así:

yAAA BBBz
C D
CED
CED
E

Cuando x sobresale (usamos X para indicar el final del dominó que sobresale en el espacio x), el empaquetamiento máximo necesariamente cubre tanto y como z:

AAAC DBBB
C D
C*D
EEE
X

Tomaré un momento para señalar que sería posible empaquetar esto con cinco dominós cuando x no sobresalga de tal manera que y o z sobresalgan. Sin embargo, hacerlo resultaría en términos que podrían ser verdaderos (no sobresalientes) y volverse falsos (sobresalientes). Permitir que algunos de los términos (no las variables, sino los términos reales en las cláusulas) difieran en valor solo al convertirse en falso innecesariamente nunca resultará en la capacidad de satisfacer una expresión de lo contrario insatisfactoria. Si nuestra expresión 3-SAT fuera (x | y | z) & (! X | y |! Z), entonces permitir que tanto x como! X fuesen falsas solo haría las cosas más difíciles. Si permitiéramos que ambos extremos de algo fueran verdad, esto daría lugar a soluciones incorrectas, pero no hacemos esto en este esquema. Para encuadrarlo en términos de nuestro problema específico, sobresalir innecesariamente nunca resultará en que se puedan empaquetar más fichas de dominó más adelante en la línea.

Con las rutas y estos tres dispositivos, ahora podemos resolver el 3-SAT planar, que sería el subproblema del 3-SAT, donde si dibujamos un gráfico donde los términos y las cláusulas sean vértices y haya una ventaja entre cada término y cada Cláusula que contiene ese término, que la gráfica es plana. Creo que el 3-SAT planar es probablemente NP-duro porque el SAT 1-en-3 planar lo es, pero en caso de que no lo sea, podemos usar dispositivos para hacer un cruce de señal. Pero es realmente bastante complejo (si alguien ve una forma más simple, por favor, hágamelo saber), así que primero voy a hacer un ejemplo de resolución planar 3-SAT con este sistema.

Por lo tanto, un problema planar simple de 3 SAT sería (x | y | z) & (! X | y |! Z). Obviamente, esto es satisfactorio, usando cualquier asignación donde y es verdadero o varias otras asignaciones. Construiremos nuestro problema de dominó así:

 *******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
*
*
*
y

Tenga en cuenta que tuvimos que usar los violinistas en la parte superior para que las cosas se espaciaran correctamente o, de lo contrario, esto habría sido mucho menos complejo.

Sumando el total de dominós de los gadgets y rutas, tenemos 1 divisor (5 fichas de dominó), dos violinistas (2 fichas de dominó cada uno) y un total de 13 rutas regulares, para un total de 5 + 2 * 2 + 13 = 22 fichas de dominó garantizadas , incluso si las cláusulas no pueden ser satisfechas. Si pueden ser, entonces tendremos 2 dominós más que se pueden completar para un total de 24. Un embalaje óptimo con 24 dominós es el siguiente:

 QRRRSSS
Q T
Q T
OPPP *UT
O U
*ON UVVV
N W
N W
M IIIJJJK W
M H K X
M H K X
*zGH* LLLX*
G *
GEEE FFF*
B D
BCD
BCD
C
A
A
A

Este mosaico contiene 24 fichas de dominó, por lo que podemos saber que la expresión original es satisfactoria. En este caso, el mosaico corresponde a hacer y y x verdaderos y z falsos. Tenga en cuenta que este no es el único mosaico (y no la única asignación satisfactoria de valores booleanos), pero que no hay otro mosaico que incremente el número de mosaicos más allá de 24, por lo que es un mosaico máximo. (Si no quieres contar todas las fichas de dominó, puedes notar que usé todas las letras excepto Y y Z).

Si el mosaico máximo hubiera contenido 22 o 23 fichas de dominó, entonces sabríamos que una de las cláusulas no estaba satisfecha (GGG y / o dominó de LLL no podrían colocarse) y, por lo tanto, sabríamos que la expresión original no era satisfactorio

Para estar seguros de que podemos hacer esto incluso si el planar 3-SAT no es NP-duro, podemos crear un gadget que permita cruzar las rutas. Desafortunadamente, este gadget es un poco grande y complejo, pero es el más pequeño que pude averiguar. Primero describiré las piezas y luego todo el gadget.

Pieza 1: Punto de cruce. X e Y son las entradas. a, b, yc son las salidas. Deberán combinarse con otros dispositivos para retransmitir xey en el lado opuesto entre sí.

 ***c
*
***
* *
* *
* *
***
***
ax*yb

Este gadget siempre cabrá exactamente 7 dominós. Hay cuatro posibles combinaciones de entrada. Si ninguna de las entradas sobresale (ambas son verdaderas), ninguna salida sobresale y se llenará como (tt1) o (tt2) a continuación. Si solo la entrada x sobresale, entonces c solo sobresale como en (ft) a continuación. Si solo la entrada y sobresale, entonces la salida a o c sobresalirá como en (tf) a continuación. Y si las entradas xey son ambas, entonces la salida c sobresale como en (ff) a continuación.

 (tt) AAAc (ft) AAAc (tf) AAAc (ff) BAAA
* * * B
BBB BBB BBB CBD
C D C D C D C D
C D C D C D C D
C D C D C D E G
EEE EEE EEE EFG
FFF FFF FFF EFG
aGGGb aXGGG GGGYb aXFYb

No he incluido la posibilidad de que en los escenarios (ft) o (tf) c pueda cubrirse en lugar de a o b. Esto es posible dentro del alcance de este gadget, pero una vez combinado con otros gadgets para formar el crossover completo, si lo hiciera, nunca daría lugar a un mayor número de cláusulas que se cumplan para que podamos excluirlo. Con eso en mente, podemos observar que en este caso el valor de la entrada x es igual al valor de b & c y la entrada y es igual al valor de a & c (tenga en cuenta que esto sería lógico o más bien que lógico y si la protusión fuera considerada verdadera en lugar de falsa). Así que solo necesitamos dividir c y luego usar un dispositivo lógico y un dispositivo para conectar los valores de c con a y b respectivamente, y luego habremos completado con éxito nuestra cruz.

Lo lógico es nuestro gadget más simple hasta ahora y se parece a esto:

 ****
*
x*y

Es posible que tenga en cuenta que hay uno incrustado hacia la parte superior del gadget de punto de cruce. Este gadget siempre contendrá exactamente 2 dominós. Uno estará en la parte superior para servir como la salida. El otro sirve como un interruptor que estará orientado horizontalmente solo si tanto x como y son verdaderos (no sobresalientes) y verticalmente orientado de otra manera, como podemos ver en los siguientes diagramas:

 BBB* ABBB ABBB ABBB
* A A A
AAA XAy xAY XAY

Por lo tanto, podemos completar el cruce dividiendo c y luego agregando dos de estas puertas, una para a & c y otra para b & c. Ponerlo todo junto también requiere agregar algunos gadgets de fiddler y se ve así:

 ******* ****
* * * *
* *** *
*** *** ***
* * *
**** * ****
* * *
* **** *
*** * ***
* *** *
**** * * ****
y * * * * x
* * * * * *
* **** *** **** *
*** *** ***
**********x*y*************

No voy a completar ejemplos de eso. Tendrá que hacerlo usted mismo si desea verlo en acción. Así que, ¡hurra! Ahora podemos hacer arbitrario 3-SAT. Debo tomarme un momento para notar que hacer esto será una transformación de tiempo polinomial porque incluso en el peor de los casos, podemos hacer una cuadrícula grande con todas las variables y sus opuestos en la parte superior y todos los términos del lado y hacer O (n ^ 2) cruces. Por lo tanto, existe un algoritmo simple, de tiempo polinomial para establecer todo esto, y el tamaño máximo del problema transformado es polinomial en el tamaño del problema de entrada. QED.

Nota de edición: Siguiendo el excelente trabajo de Tom Sirgedas para encontrar un error en el dispositivo de división, he hecho algunos cambios en la respuesta. Esencialmente, mi antiguo splitter se veía así y podría estar lleno de 6 cuando x no sobresale (en lugar de los 5 que había pretendido) así:

y*** ***z AAAC DBBB
* * C D
*** C*D
*** EEE
*x* FFF

Así que lo revisé eliminando los dos espacios a cada lado de x. Esto elimina el empaque de seis dominó y al mismo tiempo permite un empaque de 5 dominios en el que y y z se descubren cuando se descubre x.

Answer 3

Las baldosas 1x3 son difíciles por reducción de 3SAT monotono cúbico planar Uno en tres . Tenemos que construir algunos "circuitos" para codificar la fórmula.

"Puertas":

X********Y

Hace que exactamente uno de X e Y se cubra externamente. Se utiliza para vincular una variable y su negación.

Y***
*
*
ooo ****
* * * *
* * * *
X **** Z

No obliga a ninguno o todos los X e Y y Z a cubrirse externamente. Se utiliza para copiar X o destruir tres copias de la misma cosa. Los alambres se pueden conformar de forma más o menos arbitraria utilizando piezas de longitud 3 L.

*******************
* * *
* * *
X Y Z

Obliga exactamente a uno de X e Y y Z a cubrirse externamente. Una para cada cláusula.

Answer 4

Lo primero que haría sería hacer un tercer estado: "vacío, pero inalcanzable". Puede probar fácilmente que cada baldosa es inalcanzable en el tiempo l * w * m * n (donde l es la longitud del mundo, w es la anchura del mundo, y myn son las dimensiones de la baldosa). Esto reducirá su espacio de modo que se pueda acceder a cualquier ficha vacía. Tenga en cuenta que puede tener islas de azulejos alcanzables. El ejemplo más simple de esto es que el mundo está reducido a la mitad. Esto se presta a un esfuerzo recursivo en el que cada isla de accesibilidad se trata como un mundo en sí mismo.

Ahora que estamos tratando con una isla (que puede ser cuadrada o no), esencialmente tiene un caso especial del problema de la mochila 2D, que se sabe que es NP-duro ( citation en el trabajo anterior). El suyo aumenta la complejidad del problema al agregar posiciones fijas en la mochila que siempre se llenaron, pero reduce la complejidad (ligeramente) al hacer que todos los paquetes tengan el mismo tamaño.

Answer 5

Realmente una buena pregunta. Este problema es equivalente a encontrar el tamaño del conjunto independiente máximo (o el tamaño máximo de la camarilla) en un gráfico especial: los vértices serían todas las posiciones posibles del rectángulo MxN y los bordes conectarán las dos posiciones si chocan. Luego, al encontrar el tamaño del conjunto independiente máximo se obtiene el resultado. O viceversa, podríamos definir el borde como la conexión de dos posiciones que no chocan, entonces buscaríamos el tamaño máximo de camarilla. De todos modos, ninguno de los gráficos es libre de garras ni perfecto, por lo que no podemos usar soluciones polinomiales para encontrar el conjunto / clique independiente máximo.

Por lo tanto, podríamos intentar convertir el problema del conjunto máximo independiente a este problema de mosaico, pero no pude encontrar una manera de convertir el gráfico general a este, porque no se puede convertir, por ejemplo, el subgrafo K _1,5 inducido a los azulejos.