Thuật toán tham lam là gì?
Gọi là thuật toán tham lam nham 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 để ta tiến hành giải một bài toán 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 bạn chọn lựa tối ưu hóa bằng cách nào?
Giả sử bạn có một hàm cần để tối ưu hóa (hoặc cực đại hóa, hoặc cực tiểu hóa 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 bài toán
- 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à bạn 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.
C. 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, bạn có đúng T thời gian để làm một vài thứ thú vị và bạn 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ứ bạn 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ố 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 currungtime
- Công một tới số lượng công việc
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 :)
#CodeBattle2018
công nghệ thông tin
Cái này 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à ta 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 bạn 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ì các bạn cũng được 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 bạn cũng cứ chọn.
Minh Hưng
Cái này 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à ta 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 bạn 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ì các bạn cũng được 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 bạn cũng cứ chọn.
Linh Quang Nguyễn
cái này và cái vét cạn cứ na ná nhau ý :))))
Nguyễn Tiến Hoàng
Hay quá ad ơi, cho em hỏi thuật toán vét cạn là như thế nào ạ?