Trovare la strategia ottimale di piastrellatura utilizzando quadrati di dimensioni diverse

Question

Ho forme costruite su 8x8 quadrati. Ho bisogno di affiancarli utilizzando il minor numero di quadrati di dimensioni 8x8, 16x16, 32x32 e 64x64. Quattro quadrati 8x8 disposte a quadrato possono essere sostituiti da un singolo quadrato 16x16, es .:

Nei algoritmo può essere utilizzato per realizzare questo?

Answer 1

Ciò richiede una soluzione di programmazione dinamica. Immagino che abbiamo una matrice di boolean square[r][c] che è vera se (r, c) ha un quadrato 1x1 (ho semplificato la soluzione per lavorare con i quadrati 1x1, 2x2, 4x4 e 8x8 per renderlo più facile da seguire, ma è facile adattarsi). Riempilo con un muro di falsesentinel values nella riga superiore e nella colonna di sinistra.

Definire un array 2d count, dove count[r][c] si riferisce al numero di quadrati 1 x 1 nella regione sopra e alla sinistra di (r, c). Possiamo aggiungere utilizzando un algoritmo 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] 

I lavori di cui sopra con l'aggiunta di due regioni che già conosciamo la somma di, sottraendo l'area doppiamente contati e l'aggiunta nella nuova cella. Utilizzando la matrice count, possiamo testare se una regione quadrata è completamente coperta in quadrati 1x1 in tempo costante utilizzando un metodo simile:

// 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] 

Abbiamo poi creare un secondo 2d min_squares matrice, dove min_squares[r][c] si riferisce al numero minimo di quadrati necessari per coprire i quadrati 1x1 originali. Questi valori possono essere calcoli utilizzando un'altra 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) 

Per ricostruire le piastrelle necessaria per ottenere il minimo calcolato, usiamo un size_used[r][c] array ausiliario che utilizziamo per tenere traccia delle dimensioni del quadrato posto a (r, c). Da questo possiamo ricostruire ricorsivamente la piastrellatura:

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

Si potrebbe voler guardare Optimal way for partitioning a cell based shape into a minimal amount of rectangles - se ho capito correttamente, questo è lo stesso problema ma per i rettangoli invece di quadrati.