Tìm chiến lược ốp lát tối ưu bằng cách sử dụng các ô vuông có kích thước khác nhau

Question

Tôi có hình dạng được xây dựng từ hình vuông 8x8. Tôi cần phải gạch chúng bằng cách sử dụng số lượng nhỏ nhất của hình vuông kích thước 8x8, 16x16, 32x32 và 64x64. Bốn ô vuông 8x8 bố trí trong một hình vuông có thể được thay thế bằng một hình vuông 16x16 duy nhất, ví dụ .:

thuật toán gì có thể được sử dụng để đạt được điều này?

Answer 1

Điều này kêu gọi giải pháp lập trình động. Tôi giả định rằng chúng ta có một dải boolean square[r][c] là đúng nếu (r, c) có hình vuông 1x1 (tôi đã đơn giản hóa giải pháp để làm việc với các ô 1x1, 2x2, 4x4 và 8x8 để dễ dàng theo dõi hơn, nhưng dễ dàng điều chỉnh). Dán nó bằng một bức tường của falsesentinel values trên hàng trên cùng và cột bên trái.

Xác định mảng 2d count, trong đó count[r][c] là số lượng ô 1x1 trong vùng phía trên và bên trái của (r, c). Chúng ta có thể thêm chúng bằng cách sử dụng một thuật toán 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] 

Các công trình trên bằng cách cộng hai khu vực chúng ta đã biết tổng, trừ diện tích gấp đôi-đếm và thêm vào trong các tế bào mới. Sử dụng mảng count, chúng ta có thể kiểm tra nếu một khu vực hình vuông là hoàn toàn bao phủ trong hình vuông 1x1 trong thời gian liên tục sử dụng một phương pháp tương tự:

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

Sau đó chúng tôi tạo ra một 2ngày min_squares mảng thứ hai, nơi min_squares[r][c] đề cập đến số lượng tối thiểu của hình vuông được yêu cầu để bao gồm hình vuông 1x1 ban đầu. Những giá trị này có thể tính toán của sử dụng dp khác:

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) 

Để tái tạo lại ốp lát cần thiết để có được tối thiểu tính toán, chúng tôi sử dụng một size_used[r][c] mảng phụ trợ mà chúng tôi sử dụng để theo dõi các kích thước của hình vuông đặt ở (r, c). Từ đó, chúng tôi có thể tái tạo lại cấu trúc lát gạch một cách đệ quy:

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

Bạn có thể muốn xem Optimal way for partitioning a cell based shape into a minimal amount of rectangles - nếu tôi hiểu chính xác, đây là vấn đề tương tự nhưng đối với hình chữ nhật thay vì hình vuông.