Dado un subconjunto contiguo de un tablero de ajedrez (o, más generalmente, una cuadrícula rectangular 2d), ¿cómo puedo determinar algorítmicamente un conjunto mínimo de rectángulos que cubran el área?
En este ejemplo, el "subconjunto contiguo" es el área negra, y me interesan los tres rectángulos rojos. No debería haber ningún solapamiento entre los rectángulos. El tamaño relativo de los rectángulos no es demasiado importante; sería una ventaja que los tamaños no fueran demasiado diferentes.
Si el problema es tan pequeño, puedes utilizar la búsqueda por fuerza bruta: listar todos los rectángulos contenidos en el área, enumerar todos los conjuntos de rectángulos, mantener los que dividen el área, y seleccionar el mejor.
Para reducir el número de candidatos puede organizar conjuntos de rectángulos no superpuestos en un árbol (la raíz es el conjunto vacío, cada nivel añade un rectángulo las particiones están entre las hojas). En su implementación, no es necesario almacenar el árbol, sólo tienes que explorarlo.
Si el problema es mayor, en lugar de todos los rectángulos puedes utilizar los rectángulos máximos, sus intersecciones y diferencias.
Si una solución aproximada es aceptable se puede empezar con una partición en rectángulos (por ejemplo, todos los $1\times1$ rectángulos), hacer crecer esos rectángulos tanto como sea posible (en direcciones aleatorias), elimínalos o córtalos (al azar) para tener una partición. Iterar muchas veces y quedarse con la mejor solución. Creo que un algoritmo similar se utiliza para simplificar las expresiones booleanas (pero se permiten solapamientos).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
