Xếp chồng hình chữ nhật để chiếm ít không gian nhất có thể

Question

Tôi có một chương trình sẽ tính toán diện tích tối thiểu được chụp bằng các hình chữ nhật phù hợp với nhau.

Nhập: Hình chữ nhật có chiều cao và chiều rộng khác nhau.
Kết quả: Một hình chữ nhật chứa tất cả các hình chữ nhật này.
Quy tắc: Không thể xoay hoặc cuộn các hình chữ nhật xung quanh và chúng không thể trùng lặp.

Tôi hiểu rằng điều này có liên quan hoặc có thể được xác định là sự cố đóng gói thùng rác (NP-hard). Tuy nhiên các thuật toán tôi tìm thấy cho những người thường đặt một giới hạn về chiều rộng ví dụ. Tôi không có giới hạn như vậy, mục tiêu duy nhất là để có được khu vực kết quả càng nhỏ càng tốt.

Bất kỳ con trỏ nào về thuật toán nào phù hợp để có giải pháp tốt?

Answer 1

http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf

Rõ ràng vấn đề này là khó hơn bạn tưởng lúc đầu. Đó là một thuật toán thú vị, vì trước tiên nó đoán một giải pháp và sau đó cải thiện nó, vì vậy nếu bạn không muốn đợi giải pháp tối ưu, bạn có thể chạy nó cho một số lần lặp để có được một giải pháp gần đúng (dài hơn bạn chạy nó, tốt hơn gần đúng).

Answer 2

Tôi bắt đầu bằng cách lướt qua http://mathworld.wolfram.com - chúng thật tuyệt vời cho những nội dung như thế này.

Thứ hai, tôi có thể hình dung một thuật toán dopey sẽ đặt hộp dài nhất (trong kích thước X) ở phía dưới, sau đó là cao nhất (trong kích thước Y) trên đầu nó ở bên này hoặc bên kia. Sau đó tiếp tục xếp chúng trong thời trang "cầu thang bước" này đi từ phải sang phải lên trên (ví dụ đi ngay cho đến khi bạn không thể, sau đó đi lên, v.v.).

Điều đó có lẽ không lý tưởng và có thể cung cấp cho bạn kết quả kém, nhưng đó là những gì nảy sinh trước tiên.

Answer 3

Tôi khuyên bạn nên bắt đầu với một cách tiếp cận tham lam đơn giản và xem liệu điều đó có đủ tốt cho nhu cầu của bạn hay không. Nếu đầu vào của bạn là hành vi tốt hoặc nhỏ, đó có thể là tất cả những gì bạn cần - và sự phức tạp sẽ tăng lên nhanh chóng khi bạn cố gắng làm điều gì đó tinh vi hơn.

Ví dụ: sắp xếp các hình chữ nhật theo kích thước, lớn nhất trước tiên. Thêm một hình chữ nhật tại một thời điểm, cố gắng mỗi vị trí có thể cho hình chữ nhật mới. Chọn vị trí dẫn đến hộp giới hạn nhỏ nhất.

Một cách tiếp cận tham lam khác là chọn hình chữ nhật bắt đầu, sau đó liên tục thêm hình chữ nhật, kết quả là sắp xếp dày đặc nhất (trong đó mật độ được xác định là phần trăm diện tích của ô bao quanh).