Giới thiệu về thuật toán tham lam – Greedy Algorithm (Phần 2)

Ví dụ về thuật toán tham lam_ Bài toán đếm số đồng tiền

Yêu cầu

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 tiền đồng có các mệnh giá lần lượt là 1, 2, 5, và 10 xu và lượng tiền cho trước là 18 xu thì giải thuật tham lam thực hiện như sau:

  • 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 giải thuật 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ô

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *