SGCG

Volver arriba

Jugando con autómatas celulares (3)

2013-08-19

Hace varios artículos, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Ayer creamos un sencillo autómata de ejemplo. El código era específico de este autómata, pero podemos ir creando funciones más generales con las que trabajar. Empezaremos con una función que servirá para generar reglas.

Reglas deterministas vistas como consultas en tablas

Podemos modelar una regla determinista mediante una consulta en una tabla. A cada posible conjunto de vecinos —clave en la tabla— le corresponde un estado para la próxima generación —valor en la tabla—. Podemos hacer una función llamada deterministic-rule que acepta como entrada una tabla de correspondencias entre vecindarios y estados futuros y devuelve una función regla utilizable por apply-rule que internamente consulta la tabla de correspondencias.

En Scheme R5RS, las tablas asociativas son listas con una estructura especial. Estas listas son conocidas como association lists o alists. Los elementos de las listas asociativas son a su vez pares cuyo primer elemento (el car) es la clave. El valor está de alguna manera accesible a través del cdr del par, bien directamente con un par estilo (clave . valor), bien con una lista propia (clave valor). Nosotros vamos a usar este segundo esquema, que consume un poquito más de memoria, pero queda más compacto por escrito. Para pedir la entrada correspondiente a una clave, usamos la función assoc; esta función devuelve la celda completa cuyo car guarda la clave y cuyo cdr guarda de alguna manera el valor. La búsqueda de la entrada es lineal, así que puede ser lenta en tablas muy grandes; Scheme R5RS es minimalista y si quisiéramos tablas asociativas más rápidas (hechas con árboles o con tablas hash), tendríamos que hacérnoslas nosotros mismos, usar bibliotecas externas o usar extensiones propias de nuestra implementación de Scheme. Si nos conformamos con las listas, que no funcionan mal en tablas pequeñitas, la solución es así:
(define (deterministic-rule table) (lambda (neighbours) (cadr (assoc neighbours table))))

Las tablas asociativas de Python se llaman diccionarios. Entramos en un diccionario con una clave y volvemos con el valor correspondiente. La clave puede ser muchas cosas, pero las listas no son bienvenidas en principio. Podemos usar tuplas, que son como listas no mutables. El código de Python es el siguiente:
def deterministic_rule(table): return lambda neighbourhood: table[tuple(neighbourhood)]

La regla 90 del artículo anterior quedaría escrita de esta manera:
(define rule-90 (deterministic-rule '(((0 0) 0) ((0 1) 1) ((1 0) 1) ((1 1) 0))))
Es así en Python:
rule_90 = deterministic_rule({(0, 0): 0, (0, 1): 1, (1, 0): 1, (1, 1): 0})
Esto no es especialmente más corto que lo que teníamos antes, pero es prometedor, ya que podemos construir una regla a partir de una sencilla estructura de datos. La notación de esta estructura de datos es como un diminuto lenguaje especializado para construir reglas deterministas. Si tenemos que construir muchas reglas o generarlas dinámicamente, el mínimo esfuerzo que hemos hecho se vuelve muy rentable.

Otros artículos de la serie

• Introducción.
• Pequeño autómata de demostración.
• Funciones para sacar por pantalla las listas de celdas.
• Funciones auxiliares útiles.
• Más funciones auxiliares útiles.
• Funciones para trabajar con mallas cartesianas.
• Extracción de vecinos en mallas cartesianas cíclicas.
• Funciones para crear autómatas unidimensionales elementales.
• Funciones para crear generaciones sucesivas cómodamente.
• Prueba con varios autómatas elementales.
• Funciones para imprimir autómatas bidimensionales cartesianos.
• Juego de la vida de Conway.
• Funciones para trabajar con autómatas no deterministas.
• Autómata no determinista: modelo del incendio forestal.
• Autómatas de segundo orden.
• Mejora del rendimiento mediante memoización.
• Más pequeñas modificaciones para acelerar notablemente el código.
• Salida de imágenes.

Categorías: Informática

Artículos publicados el mismo mes

Permalink: https://sgcg.es/articulos/2013/08/19/jugando-con-automatas-celulares-3/

Volver arriba