1. Khái niệm Giải thuật tham lam
Giải thuật tham lam hay chính xác hơn là một kĩ thuật (technique) tương tự quy hoạch động hay chia để trị cũng là những kĩ thuật luôn chọn quyết định tốt nhất ở thời điểm hiện tại hay lựa chọn tối ưu cục bộ và hy vọng rằng quyết định đó sẽ dẫn tới giải pháp tối ưu toàn cục của bài toán.
Giải thuật tham lam không dựa vào quyết định của bài toán trước đó để đưa ra quyết định mà tại mỗi bước nó tự ra quyết định tối ưu cục bộ và quyết định này sẽ quyết định đường đi của mọi bước tiếp theo, quyết định này cũng không thể quay lại hay phục hồi.
Tại sao lại gọi là giải thuật tham lam? 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, …
2. Ưu nhược điểm của giải thuật tham lam
Khi bạn cần lựa chọn (hay thiết kế) một giải thuật tham lam để thực hiện giải một số bài toán của mình, hãy xem xét rằng giải thuật tham lam có phù hợp với bài toán được đưa ra hay không? Việc xem xét này, có thể thông qua các ưu nhược điểm của giải thuật tham lam so với các yêu cầu mà bài toán cần đưa ra.
2.1 Ưu điểm của giải thuật tham lam
- Giải thuật tham lam là phương pháp dễ nhất trong việc tiếp cận và thiết kế các giải thuật dành cho cấu trúc đồ thị và NP-đầy đủ mặc dù giải thuật tham lam sẽ không đảm bảo tìm ra được lời giải tối ưu tuy nhiên nó vẫn ước lượng và đưa ra lời giải tương đối chính xác
- Một giải thuật tham lam sẽ có độ phức tạp “rõ ràng” – điều này giúp ta có thể xem xét độ phù hợp của giải thuật khi cần sử dụng cho một bài toán.
- Nếu như giải thuật tham lam được chứng minh rằng có thể tìm ra một kết quả tối ưu toàn cục cho một lớp bài toán nào đó. Khi đó thuật toán sẽ được chọn vì tốc độ chạy nhanh hơn.
2.2 Nhược điểm của giải thuật tham lam
- Rất khó để hiểu hay chứng minh 1 lời giải tham lam là kết quả tối ưu ngay kể cả khi nó đưa ra lời giải tối ưu.
- Hầu hết các giải thuật tham lam là không chính xác.
3. Giải thuật tham lam và giải thuật quy hoạch động
Đầu tiên, chúng ta sẽ bàn luận về giải thuật tham lam. Giải thuật tham lam sẽ đưa ra quyết định sớm và thay đổi đường đi thuật toán theo quyết định đó, và không bao giờ xét lại các quyết định cũ. Điều này gây ra việc khi sử dụng giải thuật tham lam trong nhiều bài toán sẽ không đưa ra được kết quả chính xác nhất.
Tiếp theo, cùng bàn luận về giải thuật quy hoạch động. Giải thuật quy hoạch động luôn duyệt hết và đảm bảo tìm thấy lời giải, với quy hoạch động mọi quyết định đều phải dựa vào quyết định của bài toán con đã được giải ở bước trước đó và có thể xét lại đường đi của bước trước hướng tới lời giải
Nhận xét: Khi so sánh giả thuật tham lam và giải thuật quy hoạch động ta nhận thấy được sự đối nghịch hoàn toàn giữa hai giải thuật này, vì thế mà việc thiết kế giải thuật của hai giải thuật hay độ phức tạp của hai giải thuật cũng có sự khác biệt rõ rệt.
4. Ứng dụng của giải thuật tham lam
Giải thuật tham lam được sử dụng và xử lý một số bài toán trong máy tính. Như đã đề cập ở trên, giải thuật này sẽ thường được sử dụng trong các cấu trúc đồ thị, chi tiết hơn thì giải thuật tham làm được áp dụng vào các thuật toán bên dưới đâ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 trồng cây
- Bài toán ATM withdrawal
- Bài toán cái túi
