Thuật toán tham lam DSA
Thuật toán tham lam
Thuật toán tham lam quyết định phải làm gì trong mỗi bước, chỉ dựa trên tình huống hiện tại mà không cần suy nghĩ xem tổng thể vấn đề sẽ như thế nào.
Nói cách khác, thuật toán tham lam đưa ra lựa chọn tối ưu cục bộ trong mỗi bước, hy vọng cuối cùng sẽ tìm ra giải pháp tối ưu toàn cục.
Ví dụ, trong thuật toán Dijkstra , đỉnh tiếp theo được truy cập luôn là đỉnh chưa được truy cập tiếp theo với khoảng cách hiện tại ngắn nhất từ nguồn, khi nhìn từ nhóm các đỉnh được truy cập hiện tại.
Vì vậy, thuật toán của Dijkstra rất tham lam vì việc lựa chọn đỉnh nào sẽ truy cập tiếp theo chỉ dựa trên thông tin hiện có mà không xem xét vấn đề tổng thể hoặc lựa chọn này có thể ảnh hưởng như thế nào đến các quyết định trong tương lai hoặc con đường ngắn nhất cuối cùng.
Hai thuộc tính phải đúng đối với một bài toán để thuật toán tham lam hoạt động:
- Thuộc tính lựa chọn tham lam: Có nghĩa là vấn đề nằm ở chỗ có thể đạt được giải pháp (tối ưu toàn cục) bằng cách thực hiện các lựa chọn tham lam trong mỗi bước (lựa chọn tối ưu cục bộ).
- Cấu trúc con tối ưu: Có nghĩa là giải pháp tối ưu cho một vấn đề là tập hợp các giải pháp tối ưu cho các vấn đề phụ. Vì vậy, việc giải quyết các phần nhỏ hơn của vấn đề một cách cục bộ (bằng cách đưa ra những lựa chọn tham lam) sẽ góp phần tạo ra giải pháp tổng thể.
Các vấn đề chính trong hướng dẫn này, như sắp xếp một mảng hoặc tìm đường đi ngắn nhất trong biểu đồ, đều có các thuộc tính này và do đó những vấn đề đó có thể được giải quyết bằng các thuật toán tham lam như sắp xếp lựa chọn hoặc thuật toán Dijkstra.
Nhưng những bài toán như "Người bán hàng du lịch" hay "Bài toán về chiếc ba lô 0/1" không có những đặc tính này và do đó không thể sử dụng thuật toán tham lam để giải chúng. Những vấn đề này sẽ được thảo luận sâu hơn ở phần dưới.
Ngoài ra, ngay cả khi một vấn đề có thể được giải quyết bằng thuật toán tham lam thì vấn đề đó cũng có thể được giải quyết bằng thuật toán không tham lam.
Các thuật toán không tham lam
Dưới đây là các thuật toán không tham lam, nghĩa là chúng không chỉ dựa vào việc thực hiện các lựa chọn tối ưu cục bộ trong mỗi bước:
- Sắp xếp hợp nhất : Chia đi chia đôi mảng nhiều lần, sau đó hợp nhất các phần của mảng lại với nhau theo cách tạo ra một mảng được sắp xếp. Các hoạt động này không phải là một chuỗi các lựa chọn tối ưu cục bộ như các thuật toán tham lam.
- Sắp xếp nhanh : Lựa chọn phần tử trục, sắp xếp các phần tử xung quanh phần tử trục và các lệnh gọi đệ quy để thực hiện tương tự với bên trái và bên phải của phần tử trục - những hành động đó không dựa vào việc đưa ra các lựa chọn tham lam.
- Truyền tải BFS và DFS : Các thuật toán này duyệt qua biểu đồ mà không đưa ra lựa chọn cục bộ trong mỗi bước về cách tiếp tục truyền tải và vì vậy chúng không phải là thuật toán tham lam.
- Tìm số Fibonacci thứ n bằng cách sử dụng tính năng ghi nhớ: Thuật toán này thuộc một cách giải quyết vấn đề gọi là Lập trình động, giải quyết các vấn đề con chồng chéo, sau đó ghép chúng lại với nhau. Tính năng ghi nhớ được sử dụng trong mỗi bước để tối ưu hóa thuật toán tổng thể, có nghĩa là ở mỗi bước, thuật toán này không chỉ xem xét giải pháp tối ưu cục bộ là gì mà còn tính đến kết quả được tính toán trong bước này, có thể được sử dụng trong các bước sau.
Vấn đề về chiếc ba lô 0/1
Vấn đề về chiếc ba lô 0/1 không thể được giải quyết bằng thuật toán tham lam vì nó không đáp ứng thuộc tính lựa chọn tham lam và thuộc tính cấu trúc con tối ưu, như đã đề cập trước đó.
Bài toán ba lô 0/1 nói rằng bạn có một chiếc ba lô có giới hạn trọng lượng và bạn đang ở trong một căn phòng chứa đầy kho báu, mỗi kho báu có giá trị và trọng lượng.
Để giải quyết Vấn đề về chiếc ba lô 0/1, bạn phải tìm ra kho báu nào cần đóng gói để tối đa hóa tổng giá trị của kho báu bạn mang theo, đồng thời giữ ở mức dưới giới hạn trọng lượng của ba lô.
"0/1" có nghĩa là bạn có thể mang theo một món đồ hoặc không mang theo món đồ đó. Vì vậy, bạn không được phép chỉ lấy một phần của cái gì đó.
Vấn đề này không thể được giải quyết bằng thuật toán tham lam, bởi vì việc chọn mục có giá trị cao nhất, trọng lượng thấp nhất hoặc tỷ lệ giá trị trên trọng lượng cao nhất trong mỗi bước (giải pháp tối ưu cục bộ, tham lam), không đảm bảo giải pháp tối ưu (toàn cục). tối ưu).
Giả sử giới hạn ba lô của bạn là 10 kg và trước mặt bạn có ba báu vật sau:
| Treasure | Weight | Value |
|---|---|---|
| An old shield | 5 kg | $300 |
| A nicely painted clay pot | 4 kg | $500 |
| A metal horse figure | 7 kg | $600 |
Đưa ra lựa chọn tham lam bằng cách lấy thứ có giá trị nhất trước tiên, con ngựa trị giá 600 USD, có nghĩa là bạn không thể mang bất kỳ thứ gì khác mà không vượt quá giới hạn trọng lượng.
Vì vậy, bằng cách cố gắng giải quyết vấn đề này một cách tham lam, bạn sẽ có được một con ngựa kim loại trị giá 600 đô la.
Nhưng giải pháp tốt nhất trong trường hợp này là lấy chiếc khiên và chiếc bình, tối đa hóa tổng giá trị trong ba lô lên 800 USD, trong khi vẫn nằm trong giới hạn trọng lượng.
Còn việc luôn lấy kho báu có trọng lượng thấp nhất thì sao? Hay luôn lấy đi kho báu có tỷ lệ giá trị trên trọng lượng cao nhất?
Mặc dù việc tuân theo những nguyên tắc đó thực sự sẽ đưa chúng ta đến giải pháp tốt nhất trong trường hợp cụ thể này, nhưng chúng tôi không thể đảm bảo rằng những nguyên tắc đó sẽ có hiệu quả nếu các giá trị và trọng số trong ví dụ này bị thay đổi.
Điều này có nghĩa là Bài toán chiếc ba lô 0/1 không thể giải được bằng thuật toán tham lam.
Người bán hàng du lịch
Bài toán Người bán hàng du lịch là một bài toán nổi tiếng cũng không thể giải được bằng thuật toán tham lam, vì nó không đáp ứng thuộc tính lựa chọn tham lam và thuộc tính cấu trúc con tối ưu, như đã đề cập trước đó.
Bài toán Người bán hàng du lịch nói rằng bạn là nhân viên bán hàng ở một số thành phố hoặc thị trấn mà bạn phải ghé thăm để bán đồ của mình.
Quy tắc: Bạn phải ghé thăm mọi thành phố, nhưng chỉ một lần và kết thúc ở cùng thành phố mà bạn đã bắt đầu.
Mục tiêu: Tìm con đường ngắn nhất có thể.
Sử dụng thuật toán tham lam ở đây, bạn sẽ luôn đi đến thành phố chưa được ghé thăm tiếp theo gần thành phố bạn đang ở nhất. Nhưng trong hầu hết các trường hợp, điều này sẽ không đưa bạn đến giải pháp tối ưu với tổng đường đi ngắn nhất.
Mô phỏng bên dưới cho thấy nó trông như thế nào khi một thuật toán tham lam cố gắng giải quyết Bài toán người bán hàng du lịch.
Khi chạy mô phỏng, không phải lúc nào cũng rõ ràng rằng thuật toán có sai sót, nhưng bạn có thể nhận thấy đôi khi các đường thẳng cắt nhau, tạo ra tổng khoảng cách dài hơn, khi điều đó rõ ràng là không cần thiết.
Một thuật toán tham lam đang cố gắng giải quyết Bài toán người bán hàng du lịch.
Mặc dù việc áp dụng cách tiếp cận tham lam cho Bài toán người bán hàng du lịch đôi khi cho chúng ta một ước tính khá gần đúng về con đường ngắn nhất có thể, nhưng thuật toán tham lam sẽ không thể giải Bài toán người bán hàng du lịch nói chung.
Bài toán Người bán hàng du lịch không đáp ứng các thuộc tính cần thiết để có thể giải quyết bằng thuật toán tham lam.
Lưu ý: Thực tế không có thuật toán nào tìm ra con đường ngắn nhất trong Bài toán người bán hàng du lịch một cách hiệu quả. Chúng ta chỉ cần kiểm tra tất cả các tuyến đường có thể! Điều này mang lại cho chúng ta độ phức tạp về thời gian \(O(n!)\), có nghĩa là số lượng phép tính sẽ tăng lên khi số lượng thành phố (\(n\)) tăng lên.
