Bài toán xếp thùng
Khi chuyển nhà, bạn xếp đầy hết hộp này đến hộp khác và tự hỏi liệu một thứ tự khéo hơn có cần ít hộp hơn không. Đó chính là bài toán xếp thùng, và nó nổi tiếng là khó: ngay cả máy tính cũng chỉ tìm được số thùng ít nhất cho đầu vào lớn nhờ tìm kiếm khéo léo. Tuy vậy, các quy tắc đơn giản lại cho kết quả sát đến bất ngờ.
Bài toán
Cho các vật có kích thước và các thùng có cùng sức chứa, hãy đặt mỗi vật vào một thùng sao cho không thùng nào bị tràn, và dùng càng ít thùng càng tốt. Kích thước có thể là khối lượng, độ dài, thời lượng hay dung lượng tệp. Nghe như một câu đố cho buổi chiều mưa, nhưng bài toán này là NP-khó: chưa biết phương pháp nào tìm nhanh số thùng ít nhất cho mọi đầu vào.
Các quy tắc nhanh
Next fit xếp đầy một thùng cho đến khi vật tiếp theo không vừa, rồi bắt đầu thùng mới và không bao giờ quay lại. First fit giữ mọi thùng mở và đặt mỗi vật vào thùng đầu tiên còn chỗ. Best fit đặt mỗi vật vào thùng đầy nhất vẫn còn chỗ. Cả ba đều quyết định ngay, điều này hữu ích khi các vật đến lần lượt và phải được đặt ngay lập tức.
Sắp xếp trước
Vật lớn mới là vật khó, vì chúng cần nhiều chỗ trống. Sắp xếp các vật từ lớn đến nhỏ rồi dùng first fit hoặc best fit sẽ đưa vật lớn vào khi các thùng còn trống, và lấp chỗ hở bằng vật nhỏ. First fit decreasing không bao giờ dùng nhiều hơn 11/9 số thùng ít nhất, cộng một hằng số, so với 1,7 lần của first fit trên các vật chưa sắp xếp.
Một ví dụ
Lấy các thùng cỡ 10 và các vật 2, 3, 2, 1, 3, 4, 5, 6, 7 và 7, tổng cộng 40. First fit đặt 2, 3, 2 và 1 vào thùng thứ nhất, 3 và 4 vào thùng thứ hai, rồi 5, 6, 7 và 7 mỗi vật cần một thùng riêng: 6 thùng. Khi sắp xếp từ lớn đến nhỏ, first fit decreasing tạo ra 7 + 3, 7 + 3, 6 + 4 và 5 + 2 + 2 + 1: 4 thùng đầy, bằng đúng cận dưới 40 / 10 = 4.
Tìm số thùng ít nhất
Với ít vật, đáp án chính xác có thể tìm bằng quy hoạch động trên tập con: với mỗi tập vật, số thùng ít nhất và thùng cuối rỗng nhất chứa được nó được xây dựng từ các tập ít hơn một vật. Việc này mất khoảng 2ⁿ·n bước với n vật. Các trường hợp lớn hơn được giải bằng nhánh cận hoặc quy hoạch nguyên, và cận dưới cho biết một cách xếp có thể cách tối ưu bao xa.
Được dùng ở đâu
Xếp hàng lên xe tải và container, cắt ống hay cuộn giấy từ độ dài tiêu chuẩn sao cho ít hao hụt nhất (bài toán cắt vật liệu), phân bổ máy ảo lên máy chủ, và lưu tệp vào ổ đĩa đều là các bài toán xếp thùng. Trong hai và ba chiều, với hộp thay cho số, bài toán còn khó hơn nữa.
Câu hỏi thường gặp
Xếp thùng trực tuyến và ngoại tuyến khác nhau thế nào?
Trực tuyến, mỗi vật phải được đặt ngay khi đến mà không biết các vật còn lại; next fit, first fit và best fit hoạt động như vậy. Ngoại tuyến, mọi vật đều biết trước, nên có thể sắp xếp trước, như first fit decreasing làm.
First fit decreasing gần tối ưu đến mức nào?
Nó dùng nhiều nhất 11/9 số thùng ít nhất cộng 6/9 thùng, một cận mà György Dósa đã chứng minh là chặt vào năm 2007. Với đầu vào thông thường, nó thường tối ưu hoặc chỉ hơn một thùng.
Xếp thùng có giống bài toán cái túi không?
Chúng liên quan nhưng khác nhau. Bài toán cái túi xếp một túi với những vật giá trị nhất; xếp thùng đặt mọi vật vào càng ít túi càng tốt. Các bộ giải xếp thùng chính xác thường hoạt động bằng cách giải đi giải lại những bài toán giống bài toán cái túi.
Vì sao ứng dụng chỉ cho phép 12 vật?
Vì đáp án chính xác xét mọi tập vật, và 12 vật đã tạo ra 4.096 tập. Các quy tắc nhanh có thể xử lý hàng nghìn vật, nhưng hình vẽ và việc so sánh với đáp án chính xác thì không.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử xếp thùng