1. Giới thiệu

Tham lam (hay tham ăn) là một trong những phương pháp phổ biến nhất để thiết kế giải thuật. Nếu bạn đã đọc truyện dân gian thì sẽ có câu chuyện như thế này: trên một mâm cỗ có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước, ăn hết món đó ta sẽ chuyển sang món ngon thứ hai, và chuyển tiếp sang món thứ ba, … sau này học QHD thì hiểu rõ bản chất tham lam là 1 nhánh nhỏ của QHD.

Tóm lược về tiếp cận tham lam

▪ Tham lam là dạng đơn giản hóa của quay lui:

▪ Thay vì duyệt nhiều phương án (rẽ nhánh), ta chọn phương án tốt nhất để đi thẳng

▪ Không cần quay lui (vì không có nhánh khác để lựa chọn) ▪ Trong đa phần các bài toán lời giải tham lam có độ phức tạp tuyến tính hoặc bậc hai theo số lượng thành phần con (theo bậc của cấu hình A).

▪ Trong cuộc sống, chiến lược này giống như việc chỉ tính trước một nước và chọn nước đi đem lại nhiều lợi nhất

▪ Mô hình toán học thì tiếp cận tham lam là lựa chọn tối ưu cục bộ, như vậy những bài toán quy hoạch lồi thì tiếp cận này sẽ cho ra kết quả tối ưu

▪ Lớp các bài toán mà tiếp cận tham lam đem lại kết quả tối ưu gọi là “Greedoid”

▪ Nhiều thuật toán nổi tiếng thuộc lớp greedoid: Dijkstra, Prim, Kruskal, mã hóa huffman,...

▪ Tham lam hữu ích ngay cả khi thuật toán này không đem lại kết quả tối ưu.

▪ Thực tế thì người ta cũng không cần kết quả tối ưu mà chỉ cần những phương án đủ tốt, tiệm cận với tối ưu

▪ Sử dụng tham lam làm cận khi duyệt: thay vì duyệt bằng nhánh cận ngay từ đầu, ta có thể dùng tiếp cận tham lam để tìm ra một nghiệm đủ tốt, và sử dụng kết quả này làm cận trên cho việc tìm kiếm nghiệm tối ưu

Tham lam - Bài tập và lời giải