Thuật toán để tìm số hình chữ nhật tối thiểu bao gồm các phần tử nhất định trong mảng 2d

Question

Đơn giản, tôi phải giải quyết vấn đề sau:

Bạn có mảng 2 chiều có 0 và 1. Tìm số lượng hình chữ nhật tối thiểu sao cho chúng bao trùm tất cả 1s. Hình chữ nhật không được chồng lên nhau.

Chữ ký chức năng có thể trông giống như: List<Rectangle> FindCoveringRectangles(bool[,] array)

Tôi đã có một giải pháp đó là "đủ tốt", nhưng không phải lúc nào tìm ra số lượng tối thiểu của hình chữ nhật. Tôi muốn biết nếu có một số thuật toán nổi tiếng và hiệu quả có thể được áp dụng để giải quyết vấn đề này?

Ví dụ:

Một mảng đầu vào của:

.......... 
.1.....11. 
.......11. 
...111.... 
...111.... 
...111.... 
....1111.. 
....1111.. 
......11.. 
.......... 

(0s thay thế bằng dấu chấm cho dễ đọc)

Có thể dẫn đến việc hình chữ nhật sau:

(2,2,2,2), 
(2,8,3,9), 
(4,4,6,6), 
(7,5,8,8), 
(9,7,9,8) 

(top , trái, dưới, phải), 1 dựa trên

Có thể có nhiều hơn một giải pháp, nhưng một là đủ.

Answer 1

Đây là vấn đề phù hợp của một loại, có thể dễ dàng hiển thị NP-hard. Tuy nhiên có vẻ như thực sự là một giải pháp rất nhanh!

Sử dụng lấp đầy bfs, bạn có thể tìm thấy từng thành phần được kết nối, O(n). Do đó, chúng ta có thể giả định rằng chúng ta chỉ cần điền vào một vùng được kết nối.

Nếu khu vực này không có lỗ hổng trong nó, bạn có thể sử dụng các thuật toán được mô tả trong this paper (hoặc here on google scholar.)

Một O (n log log n) thuật toán được đề xuất cho hình chữ nhật tối thiểu phân vùng một đa giác tuyến tính đơn giản. Đối với bất kỳ đa giác tuyến tính tuyến tính P đơn giản nào, một cặp có thể nhìn thấy đỉnh là một đỉnh và một cạnh có thể được kết nối bởi một đoạn thẳng đứng hoặc nằm ngang nằm hoàn toàn bên trong P. Nó được chỉ ra rằng, nếu các cặp có thể nhìn thấy đỉnh , kết hợp tối đa và tập hợp độc lập tối đa của biểu đồ hai chân bắt nguồn từ các hợp âm của một đa giác tuyến tính đơn giản có thể được tìm thấy trong thời gian tuyến tính mà không cần xây dựng biểu đồ hai chân. Sử dụng thuật toán này, bài toán phân vùng tối thiểu cho các đa giác trực giao lồi và các đa giác tuyến tính lồi thẳng đứng (theo chiều ngang) có thể được giải quyết trong thời gian O (n)

Một số giấy tờ được đề cập cũng bao gồm trường hợp có lỗ . Những chạy trong O (n^(3/2) logn) mặc dù, nhưng họ vẫn đường may khá tốt.

Ngoài ra, một điều bạn có thể làm là giải quyết vấn đề mà không cần lỗ, giải quyết vấn đề cho mỗi lỗ, và sau đó trừ đi. Điều này có thể không đưa ra một giải pháp tối ưu mặc dù, nhưng sẽ giữ cho thời gian chạy.

Bạn cũng có thể thử và tách hình dạng trong các phần tôpô khác nhau của nó, nhưng điều đó có khả năng sẽ chạy theo cấp số nhân trong số lỗ.

Thứ ba, bạn có thể thử điều chỉnh thuật toán được đề xuất cho trường hợp tổng quát hơn, nhưng có thể khó.