Encontrando la estrategia óptima de mosaico usando cuadrados de diferentes tamaños

Question

Tengo formas construidas con cuadrados de 8x8. Necesito colocarlos en mosaico usando la menor cantidad de cuadrados de tamaño 8x8, 16x16, 32x32 y 64x64. Cuatro cuadrados de 8x8 dispuestos en un cuadrado pueden ser reemplazados por un solo cuadrado de 16x16, por ejemplo .:

¿Qué algoritmo se puede utilizar para lograr esto?

Answer 1

Esto requiere una solución de programación dinámica. Asumiré que tenemos una matriz square[r][c] de booleanos, que es verdadera si (r, c) tiene un cuadrado de 1x1 (simplifiqué la solución para trabajar con cuadrados 1x1, 2x2, 4x4 y 8x8 para que sea más fácil de seguir, pero es fácil de adaptar) Rellene con una pared de falsesentinel values en la fila superior y columna izquierda.

Defina una matriz 2d count, donde count[r][c] se refiere a la cantidad de cuadrados 1x1 en la región arriba ya la izquierda de (r, c). Podemos sumarlos usando un algoritmo de DP:

count[0..n][0..m] = 0 
for i in 1..n: 
    for j in 1..m: 
    count[i][j] = count[i-1][j] + count[i][j-1] - 
     count[i-1][j-1] + square[i][j] 

Los trabajos anteriores de la suma de dos regiones que ya sabemos la suma de, restando el área contados doblemente y la adición de la nueva célula. Uso de la matriz count, podemos probar si una región cuadrada está totalmente cubierto en cuadrados de 1x1 en tiempo constante usando un método similar:

// p1 is the top-left coordinate, p2 the bottom-right 
function region_count(p1, p2): 
    return count[p1.r][p1.c] - count[p1.r][p2.c-1] - 
     count[p2.r-1][p1.c] + 2*count[p2.r-1][p2.c-1] 

entonces se crea una segunda min_squares matriz 2D, donde min_squares[r][c] se refiere al número mínimo de cuadrados requeridos para cubrir los cuadrados originales de 1x1. Estos valores pueden ser calcula utilizando otra dp:

min_squares = count 
for i in 1..n: 
    for j in 1..m: 
    for size in [2, 4, 8]: 
     if i >= size and j >= size and 
      region_count((i-size, j-size), (i, j)) == size*size: 
     min_squares[i][j] = min(min_squares[i][j], 
      min_squares[i-size-1][j] + 
      min_squares[i][j-size-1] - 
      min_squares[i-size-1][j-size-1] + 
      1) 

Con el fin de reconstruir el suelo de baldosas necesario para obtener el mínimo calculado, utilizamos un size_used[r][c] array auxiliar que utilizamos para realizar un seguimiento del tamaño de cuadrado colocado en (r, c). De esto podemos recursivamente reconstruir el mosaico:

function reconstruct(i, j): 
    if i < 0 or j < 0: 
    return 
    place square of size size_used[i][j] at (i-size_used[i][j]+1, j-size_used[i][j]+1) 
    reconstruct(i-size_used[i][j], j) 
    reconstruct(i, j-size_used[i][j]) 

Answer 2

Es posible que desee consultar Optimal way for partitioning a cell based shape into a minimal amount of rectangles - si entendí correctamente, este es el mismo problema, pero para rectángulos en lugar de cuadrados.