MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐÓNG THÙNG
Tổng quan các phương pháp giải bài toán đóng thùng
Bài toán đóng thùng là một bài toán tối ưu tổ hợp nổi tiếng với nhiều thuật toán để giải quyết, đặc biệt là các thuật toán xấp xỉ Nó đóng vai trò quan trọng trong nghiên cứu các thuật toán xấp xỉ, thường được chọn là một trong những bài toán đầu tiên để xây dựng và đánh giá hiệu năng của các thuật toán này Ví dụ, bài toán này được sử dụng để đánh giá hiệu quả của thuật toán xấp xỉ trong thời gian tính toán, xác định cận dưới cho hiệu năng của các thuật toán tĩnh (online algorithms), cũng như phân tích hiệu năng dựa trên xác suất thống kê.
Bài viết dưới đây sẽ trình bày một số thuật toán quan trọng để giải bài toán đóng thùng, từ đó giới thiệu các kết quả nghiên cứu hiện nay liên quan đến bài toán này.
Các phương pháp heuristic đơn giản
2.2.1 Các thuật toán trực tiếp
2.2.1.1 Khái niệm thuật toán trực tiếp
Thuật toán trực tiếp (on-line algorithm) là thuật toán thực hiện việc xếp đồ vật vào thùng chứa mà không có thông tin về các đồ vật sẽ xuất hiện sau đó Ràng buộc này thường gặp trong thực tế, chẳng hạn như trong lĩnh vực bán hàng, nơi người bán không biết yêu cầu của khách hàng tiếp theo.
Các thuật toán on-line ph bi n bao g m Next Fit, First Fit và Best Fit ổ ế ồ
Chương 2 MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐÓNG THÙNG
Mô tả quy tắc xếp các đồ vật của Next Fit (NF )
NF sẽ đặt đồ vật đang xét vào thùng đang mở, với điều kiện thùng đó còn đủ chỗ trống Nếu thùng không còn chỗ, NF sẽ đóng thùng lại và mở thùng mới để tiếp tục đặt đồ vật vào Quá trình này bắt đầu với đồ vật đầu tiên và kết thúc khi tất cả đồ vật đã được xếp vào thùng.
Next Fit được mô tả bằng đoạn mã sau: bin_index = 1; // chỉ số cho biết số lượng thùng đã sử dụng, item_index = 1; // chỉ số cho biết đang xét đến đồ vật thứ bao nhiêu.
Open B[bin_index]; // mở thùng đầu tiên để tiếp nhận đồ vật active_bin = B[bin_index];
// B[] là một mảng chứa các thùng được sử dụng trong thuật toán while (item_index K, suy ra M = 2K + 1 < 2.S + 1 ≤ N + 1, suy 2 ra M < 2 + 1 Nhưng vì N Mlà lẻ nên ta s có ẽ M 2.≤ N – 1 hay < 2 M N (2)
Từ (1) và (2) ta suy ra với mọi M thì M < 2.N, suy ra điều giả sử M ≥ 2 là không N đúng, từ đó ta có điều phải chứng minh
Bên cạnh Định lý 2.1 v a trình bày ừ ở trên, ta cũng có thể xây d ng mự ột danh sách các đồ vật L như sau:
N thùngOPT( ) = N + 1L NF( ) = 2L NHình 2 1 Ví dụ về bộ dữ liệu trong đó thuật toán NF hoạt động tồi nhất
L có tổng s 4N ph n tố ầ ử Trong trường h p này ta th y NF(L) = 2N và OPT(ợ ấ L) = N+1, suy ra 2
Mà theo như Định lý 2.1 thì NF(L) ≤ OPT L) 2 ( – 1 , t∀L ừ đây ta kết luận được R NF ∞ =2
Trong ví dụ trên, ta thấy rằng đồ thị có kích thước lớn nhất là bằng 1/2, từ đó suy ra R(∞ NF α) = 2 cho mọi α ≥ 1/2 Ngoài ra, D.S Johnson cũng chỉ ra rằng R(∞ NF α) = 1/(1-α) khi α < 1/2.
Mô tả quy tắc xếp đồ vật của First Fit (FF : )
Thuật toán First Fit (FF) xếp đồ vật vào thùng đầu tiên còn đủ chỗ Nếu không có thùng nào phù hợp, FF sẽ tạo thùng mới để chứa đồ vật Quá trình này tiếp tục cho đến khi tất cả đồ vật được xếp vào thùng Điều này cho thấy rằng FF không giới hạn số lượng thùng sử dụng và số thùng hoạt động là biến đổi Đoạn mã sau đây mô tả hoạt động của FF: `bin_index = 1; // số thùng đã sử dụng` và `item_index = 1; // số đồ vật đang xét`.
Open B[bin_index]; // mở thùng đầu tiên để tiếp nhận đồ vật
// B[] là một mảng chứa các thùng được sử dụng trong thuật toán while (item_index
