Bài 6 - Thuật toán tham lam trong cấu trúc dữ liệu & giải thuật

Thuật toán tham lam

Một thuật toán được thiết kế để đạt được giải pháp tối ưu cho một vấn đề nhất định. Theo cách tiếp cận thuật toán tham lam, các quyết định được đưa ra từ miền giải pháp đã cho. Vì tham lam, giải pháp gần nhất có vẻ cung cấp giải pháp tối ưu được chọn.

Các thuật toán tham lam cố gắng tìm một giải pháp tối ưu cục bộ, cuối cùng có thể dẫn đến các giải pháp tối ưu hóa toàn cầu. Tuy nhiên, nhìn chung các thuật toán tham lam không cung cấp các giải pháp tối ưu hóa toàn cầu.

Đếm tiền

Yêu cầu là hãy lựa chọn số lượng đồng tiền nhỏ nhất có thể sao cho tổng mệnh giá của các đồng tiền này bằng với một lượng tiền cho trước. Nếu chúng tôi được cung cấp các đồng xu 1, 2, 5 và 10 và chúng tôi được yêu cầu đếm $ 18 thì thủ tục tham lam sẽ là:

• Bước 1: Chọn đồng 10 xu, do đó sẽ còn 18 – 10 = 8 xu.
• Bước 2: Chọn đồng 5 xu, do đó sẽ còn là 3 xu.
• Bước 3: Chọn đồng 2 xu, còn lại là 1 xu.
• Bước 4: Cuối cùng chọn đồng 1 xu và giải xong bài toán.

Bạn thấy rằng cách làm trên là khá ổn, và số lượng đồng tiền cần phải lựa chọn là 4 đồng tiền. Nhưng nếu chúng ta thay đổi bài toán trên một chút thì cũng hướng tiếp cận như trên có thể sẽ không đem lại cùng kết quả tối ưu.

Chẳng hạn, một hệ thống tiền tệ khác có các đồng tiền có mệnh giá lần lượt là 1, 7 và 10 xu và lượng tiền cho trước ở đây thay đổi thành 15 xu thì theo giải thuật tham lam thì số đồng tiền cần chọn sẽ nhiều hơn 4. Với giải thuật tham lam thì: 10 + 1 + 1 +1 + 1 + 1, vậy tổng cộng là 6 đồng tiền. Trong khi cùng bài toán như trên có thể được xử lý bằng việc chỉ chọn 3 đồng tiền (7 + 7 +1).

Do đó chúng ta có thể kết luận rằng, giải thuật tham lam tìm kiếm giải pháp tôi ưu ở mỗi bước nhưng lại có thể thất bại trong việc tìm ra giải pháp tối ưu toàn cục.

Ví dụ áp dụng thuật toán tham lam

Có khá nhiều giải thuật nổi tiếng được thiết kế dựa trên tư tưởng của giải thuật tham lam. Dưới đây là một trong số các giải thuật này:

• Bài toán hành trình người bán hàng
• Giải thuật cây khung nhỏ nhất của Prim
• Giải thuật cây khung nhỏ nhất của Kruskal
• Giải thuật cây khung nhỏ nhất của Dijkstra
• Bài toán xếp lịch công việc
• Bài toán xếp ba lô
• ...

- Hiếu Kiều -