Nebulosa en Expansión: Problema en Autómatas Celulares o Teoría de Codificación

Primera publicación en Math Stackexchange. Recientemente se me planteó un desafío de programación informática matemáticamente intensivo que no sé cómo resolver. Para brindarle información sobre mi experiencia en matemáticas, soy un estudiante de último año de física y de ciencias de la computación en la universidad y recientemente completé un curso de álgebra lineal además de haber tomado calc 1, 2, cálculo multivariado y diff eq. Tengo una pequeña experiencia con matemáticas discretas y teoría de números de un curso de introducción a la informática. He aplicado cursos de álgebra lineal, matemáticas discretas y codificación algebraica programados para los próximos 6 meses, pero no estoy seguro si cubriré el material para resolver mi problema. Esperaría hasta después de tomar los cursos para ver si puedo aplicar algo nuevo, pero este problema me ha estado volviendo loco.

No estoy necesariamente buscando una solución, sino algunas áreas para investigar que pueden ayudarme a resolverlo. Si necesita más información o explicación, hágamelo saber. El problema es el siguiente:

A partir de los escaneos de la nebulosa, descubrió que es muy plana y está distribuida en distintos parches, por lo que puede modelarla como una cuadrícula 2D. Encuentra que la existencia actual de gas en una celda de la red está determinada exactamente por sus 4 celdas cercanas, específicamente, (1) esa celda, (2) la celda debajo de ella, (3) la celda a la derecha de ella, y (4) la celda de abajo ya la derecha de la misma. Si, en el estado actual, exactamente 1 de esas 4 celdas en el bloque 2x2 tiene gas, entonces también tendrá gas en el siguiente estado. De lo contrario, la celda estará vacía en el siguiente estado.

Por ejemplo, digamos que el estado anterior de la grilla (p) era:

.O..
..O.
...O
O...

Para ver cómo cambiará esta cuadrícula para convertirse en la cuadrícula actual (c) en el siguiente paso de tiempo, considere los bloques de celdas de 2x2 alrededor de cada celda. Del bloque 2x2 de [p[0][0], p[0][1], p[1][0], p[1][1]], solo p[0][1] tiene gas en lo que significa que este bloque 2x2 se convertiría en la celda c[0][0] con gas en el siguiente paso de tiempo:

.O -> O
..

Del mismo modo, en el siguiente bloque de 2x2 a la derecha que consta de [p[0][1], p[0][2], p[1][1], p[1][2]], dos de los que contienen las celdas tienen gas, por lo que en el siguiente estado de la red, c[0][1] NO tendrá gas:

O. -> .
.O

Siguiendo este patrón hasta su conclusión, a partir del estado anterior p, el estado actual de la grilla c será:

O.O
.O.
O.O

Tenga en cuenta que la salida resultante tendrá 1 fila y columna menos, ya que las celdas inferiores y más a la derecha no tienen una celda debajo y a la derecha de ellas, respectivamente.

Escriba una función answer(g)donde ghaya una matriz de matrices de booleanos que indiquen si hay gas en cada celda (el escaneo actual de la nebulosa) y devuelva un int con la cantidad de posibles estados previos que podrían haber resultado en esa cuadrícula después de 1 paso de tiempo . Por ejemplo, si a la función se le diera el estado actual canterior, se deduciría que los posibles estados anteriores eran p(dados arriba) así como sus reflejos horizontales y verticales, y devolvería 4. El ancho de la cuadrícula estará entre 3 y 50 inclusive, y la altura de la grilla estará entre 3 y 9 inclusive. La respuesta siempre será menos de mil millones (10^9).

Inputs:
(boolean) g = [
                [true, false, true],
                [false, true, false],
                [true, false, true]
              ]
Output:
(int) 4

Inputs:
(boolean) g = [
                [true, false, true, false, false, true, true, true],
                [true, false, true, false, false, false, true, false],
                [true, true, true, false, false, false, true, false],
                [true, false, true, false, false, false, true, false],
                [true, false, true, false, false, true, true, true]
              ]
Output:
(int) 254

Inputs:
(boolean) g = [
                [true, true, false, true, false, true, false, true, true, false],
                [true, true, false, false, false, false, true, true, true, false],
                [true, true, false, false, false, false, false, false, false, true],
                [false, true, false, false, false, false, true, true, false, false]
              ]
Output:
(int) 11567

He investigado la teoría de la codificación, pero no creo que esto entre en ninguna de esas categorías. He explorado opciones en procesamiento de imágenes con enmascaramiento de bits y autómatas celulares. Lo más cerca que he llegado a una solución es investigando los autómatas celulares 2D del vecindario de Margolus. Como esto no es reversible por definición, no he encontrado una solución ni un método general para encontrar una solución. Solo tengo curiosidad por dónde debo mirar. Sé que esto tiene que tener una respuesta derivada de un campo de las matemáticas, pero no se parece a nada de lo que sé actualmente.

¿Cómo se supone que se calcula el valor respuesta (g) ? Nos ha dicho cuál es la entrada, pero no lo que se supone que debe decirnos la salida. Las reglas para la evolución son un poco como el Juego de la vida de Conway, pero a primera vista parece que es más probable que esto se aborde mediante operaciones bit a bit en cadenas binarias.
Supongo que ese es realmente el corazón de mi problema. Tengo la tarea de diseñar la función. Casi todos los desafíos que me han planteado tienen que ver con la combinatoria con algunos problemas de diseño y una relación de recurrencia difícil. La salida es el número de posibles estados previos que conducirán al estado actual dado siguiendo la regla de vecindad dada. He añadido una edición. Parece que a la publicación original le faltaba parte de la pregunta que describe el significado de la salida y cómo debería ser una solución. Espero que esto ayude.
Llegué tarde a la fiesta por algunos años :) Este problema se puede resolver de varias maneras, que es lo que hice. Fundamentalmente, recomiendo escribir una solución de fuerza bruta. Luego optimizarlo. Y luego mire de cerca por qué el método de fuerza bruta no se completa en cuadrículas más grandes.

Respuestas (1)

esta es claramente una pregunta de autómata celular (CA). Tiene que ver con calcular el número de preimágenes de una cierta regla CA de tamaño 2x2 dentro de una matriz rectangular finita. Piense en cómo intentaría construir tales preimágenes. La entrada (configuración actual) es una matriz de tamaño NxM con valores 0 y 1 (verdadero y falso si lo prefiere). Entonces, las preimágenes (es decir, configuraciones de un paso de tiempo en el pasado) tienen un tamaño (N+1)x(M+1) también con valores 0 y 1. Ahora, ¿cuál es la regla local de evolución de una configuración a la siguiente? Tiene que ver con los valores de cuatro celdas adyacentes que determinan el nuevo valor de una celda. Intente hacer un pequeño ejemplo a mano, por ejemplo, dada la entrada 3x3 g de su publicación. ¿Puedes encontrar las cuatro configuraciones de preimagen paso a paso? Piense en lo que significa especificar algunas de las celdas en la preimagen (p. ej.

En general, encontrar preimágenes de CA (o incluso determinar su número) es un problema difícil, pero en el caso de configuraciones finitas y esta regla de evolución específica, una computadora puede manejarlas. Hay un algoritmo de fuerza bruta que debería funcionar bien para los tamaños de entrada especificados, pero también hay un algoritmo más inteligente/elaborado para ahorrar mucho tiempo, especialmente si su entrada es un rectángulo bastante largo pero angosto.

Espero que estos comentarios te den algunas ideas sobre cómo atacar el problema. Si necesitas más detalles, házmelo saber.

Bien, me expandí a lo largo de la fila superior de la matriz 3x3 dada y llegué a algunas conclusiones. Fila (1 0 1) da 8 preimágenes. (Traté de enumerarlas aquí pero no puedo formatearlas correctamente) Al expandir la siguiente fila, noté que las preimágenes correctas para la segunda fila tenían su fila superior en común con la fila inferior de las preimágenes de la primera fila. Se "superponen" Parece bastante desalentador escribir un algoritmo para encontrar las imágenes previas de una fila y luego continuar hacia abajo en la matriz manteniendo solo las imágenes previas que se "superponen".
Pero en esencia es la idea correcta.
Lo que hace que las cosas sean más tratables es que podría configurar algo que se llama matriz de transferencia. La idea es que dada una columna (toma el más corto de los dos lados del rectángulo) hay ciertas preimágenes posibles. Esos tienen la forma de un rectángulo de ancho 2 (es decir, dos columnas) y puede almacenar posibles preimágenes para una columna de imagen dada en una matriz. Ahora, para la siguiente columna, tomaría sus preimágenes y simplemente compararía cuáles son admisibles con las que produjo la columna anterior.
Dado que la altura de su rectángulo de entrada no es más de 9 celdas, esta matriz de preimágenes no tiene más de 512 entradas y el algoritmo para recorrer hasta 50 columnas debería ser lo suficientemente rápido para producir la respuesta deseada. (Hay más trucos para acelerar el cálculo, pero comience con algo simple, de fuerza bruta). Y todos los pasos (es decir, llenar la matriz, comparar superposiciones de columnas, etc.) se pueden realizar automáticamente usando subrutinas.
Bueno, ella no es bonita, pero tengo un programa que funciona para resolver los casos de prueba que me han dado al menos. Esperemos que se ejecute en un tiempo lo suficientemente decente para resolver casos más complejos. ¡Gracias por la inspiración y las ideas!
@MHS Hola, ¡el método de matriz de transferencia es una buena idea! Utilizo el método tomando cada columna de preimagen posible como un nodo para construir el gráfico. El resultado es que, cuando la cuadrícula contiene todos los "falsos" o todos los "verdaderos", el resultado de la matriz es igual a los recuentos previos al estado. Pero cuando la cuadrícula contiene tanto "falso" como "verdadero", el resultado de la matriz es más grande que los recuentos de estado previo reales, ya que hay muchos "caminos" con los mismos "recorridos" pero no comienzan desde la primera columna de preimagen ni terminan en el última columna de preimagen o rutas "internas". ¿Tendrías algunas sugerencias sobre esta condición? ¡Gracias!
Nebulosa en Expansión: Problema en Autómatas Celulares o Teoría de Codificación
RespuestasAquíPolítica de privacidad1y, 0v