Gọi là thuật toán tham lam nhưng thực chất tham lam không được gọi là thuật toán, mà nó là một kỹ thuật, một phương pháp để tiến hành giải một vấn đề trong lập trình.
Vậy thì thuật toán tham lam là gì?
Một thuật toán tham lam, như tên gọi cua nó, đó là luôn luôn làm một sự lựa chọn tốt nhất tại thời điểm hiện tại. Điều này có nghĩa rằng, sự lựa chọn tốt nhất ở mỗi bước sẽ dẫn tới lời giải tối ưu nhất
Vậy chọn lựa tối ưu hóa bằng cách nào?
Giả sử ông có một hàm cần tối ưu hóa (hoặc cực đại, hoặc cực tiểu hàm đó). Một thuật toán tham lam sẽ thực hiện các lựa chọn tham lam ở mỗi bước để đảm bảo rằng hàm đã cho là tối ưu. Thuật toán tham lam chỉ có một lần tính toán lời giải tối ưu với mục đích nó không bao giờ trở lại và đảo ngược quyết định.
Thuật toán tham lam có một vài sự thuận lợi và không thuận lợi:
- Khá dễ để tiến hành một thuật toán tham lam cho một project
- Phân tích thời gian chạy của thuật toán tham lam sẽ dễ dàng hơn kỹ thuật khác (như Chia để trị). Với kỹ thuật chia để trị, không rõ ràng liệu kỹ thuật này là nhanh hay chậm. Lý do là ở mỗi mức của đệ quy kích thước nhỏ hơn và số lượng của bài toán con lớn hơn.
- Khó khăn của tham lam là rất vất vả để hiểu chính xác vấn đề. Thậm chí với giải thuật chính xác rồi, cũng rất khó khăn để chứng minh tại sao nó đúng. Chứng minh một giải thuật tham lam là đúng có cảm giác là cả một nghệ thuật hơn là một khoa học, vì nó đòi hỏi rất nhiều sự sáng tạo
Lưu ý: Hầu như các giải thuật tham lam đều không chính xác. Một ví dụ sẽ được mô tả trong bài báo sau đây.
Tạo ra một Giải thuật tham lam như thế nào?
Bài toán: Là một người bận rộn, ông có đúng T thời gian để làm một vài thứ thú vị và ông muốn làm nhiều thứ nhất có thể.
Cho một mảng A gồm các số có kiểu int, trong đó mỗi phần tử biểu thị thời gian hoàn thiện thứ đó. Hãy tính toán số thứ ông có thể làm với thời gian giới hạn
Đây là một bài toán tham lam đơn giản. Ở mỗi bước, ta phải chọn lựa tham lam bằng cách chọn các công việc có thời gian hoàn thành ít nhất. ở đây ta có hai biến là thời gian hiện tại (currentTime) và số lượng công việc (numberOfThings). Để hàm thành, ta phải:
- Sắp xếp mảng A theo chiều không giảm
- Chọn lựa mỗi công việc để làm
- Cộng thời gian để hoàn thành vào biến currentTime
- +1 một tới numberOfThings
- Lặp lại điều này trong khi biến currentTime nhỏ hơn hoặc bằng T, vậy là xong.
Phần 2: Giải thuật
Cái thuật toán là phương pháp lấy tư tưởng từ cuộc sống. Khi gặp một tình huống quá phức tạp, hoặc một vấn đề mà chưa có lời giải hoàn chỉnh, thì thấy cái gì tốt nhất, mà khả thi ở thời điểm hiện tại thì làm. Cứ thực hiện đi đã rồi sẽ tiếp tục tối ưu sau.
Nghĩ nhiều quá, phức tạp quá, triển khai chậm có khi lại không thành công.
Hơn nữa mọi việc để hướng tới sự hoàn hảo đều tốn rất nhiều công sức, đặc biệt ở những phần trăm cuối. Nhưng để đạt được 80% thành công thì lại không quá khó. Nó tương tự như việc ông muốn trở thành người xuất sắc nhất lớp, hoặc đạt giải nhất cuộc thi thì phải nỗ lực rất lớn. Còn để học khá, vào top đầu thì lại tương đối đơn giản.
Trong các cuộc thi học sinh giỏi, trong khoảng thời gian rất ngắn chưa thể nghĩ được lời giải chính xác thì khuyên hãy áp dụng phương pháp tham lam, để ghi thêm ít điểm. Ví dụ thi trắc nghiệm mà không bị trừ điểm nếu chọn sai thì bất cứ câu nào không làm được thì cứ random chọn bừa đi. Biết đâu trúng Vietlott.
Xem chi tiết
