Để giải quyết bài toán này bạn cần phải phần tích đầu vào của bạn. Trong bài toán nầy, đầu vào của bạn có những tính chất sau: Số nguyên N cho số các công việc bạn muốn hoàn thành Danh sách P: Thứ tự ưu tiên (hoặc trọng lượng công việc) Danh sách T: Thời gian yêu cầu để hoàn thành nhiệm vụ Để hiểu điều kiện để tối ưu hóa, bạn phải xác định tổng thời gian yêu cầu để hoàn thành mỗi nhiệm vụ: Đó là bởi vì công việc thứ j phải chờ cho tới khi nhiệm vụ thứ (j-1) được hoàn thành sau đó yêu cầu T[j] thời gian để hoàn thành Cho ví dụ, nếu T={1,2,3} , thời gian hoàn thành sẽ là: Bạn rõ ràng mong muốn thời gian hoàn thành càng sớm càng tốt. Nhưng điều đó không hề đơn giản Trong một dãy đã cho, các công việc xếp hàng ngay từ đầu có thời gian hoàn thành ngắn hơn và công việc xếp hàng ở cuối có thời gian hoàn thành lâu hơn. Con đường tối ưu để hoàn thành nhiệm vụ là gì? Điều này phụ thuộc vào hàm đối tượng Trong khi có nhiều hàm đối tượng cho bài toán Lập lịch, hàm đối tượng F của bạn là tổng trọng lượng của thời gian hoàn thành Hàm này phải nhỏ nhất Các trường hợp đặc biệt: Nhìn vào các trường hợp đặc biệt sẽ giúp bạn có một giải thuật tham lam tự nhiên, và thu hẹp còn một số trường hợp Có hai trường hợp sau: 11. Nếu thời gian yêu cầu để hoàn thành các nhiệm vụ khác nhau là giống nhau, tức là T[i]=T[j] với mọi 1<=i,j<=N, nhưng chúng có thứ tự ưu tiên khác nhau 2. Nếu thứ tự ưu tiên của các công việc là giống nhau, tức là p[i]=p[j] với mọi 1<=i,j<=n nhưng chúng có thời gian hoàn thành khác nhau Nếu thời gian yêu càu hoàn thành các công việc khác nhau là giống nhau, thì khi đó bạn sẽ ưu tiên nhiệm vụ nào có mức ưu tiên lớn hơn Trường hợp 1 Xét hàm đối tượng mà bạn cần tối thiếu hóa Giả sử thời gian yêu cầu để hoành thành nhiệm vụ này là t. T[i]= t với mọi 1<=ip[j] nhưng t[i]>t[j] Bạn nên lựa chọn cái nào đầu tiên? Bạn có thể tổng hợp 2 tham số này (thời gian và thứ tự ưu tiên) trong một điểm số đơn giản thỏa mãn nếu bạn sắp xếp công việc từ điểm cao tới điểm thấp, bạn sẽ luôn nhận được một lời giải tối ưu? Nhớ 2 nguyên tắc sau:
Bạn có thê sử dụng hàm toán học, lấy 2 số (thứ tự ưu tiên và thời gian yêu cầu) như input và trả về một số đơn giản (điểm số) như ouput trong khi có 2 tính chất này (Có vô số hàm như vậy) Ta lấy ví dj hai hàm đơn giản có tính chất như vậy: Giải thuật 1. Thứ tự các công việc giảm dần theo giá trị của (p[i]-t[i]) Giải thuật 2. Thứ tự các công việc giảm dần theo giá trị của (p[i]/t[i]) Để đơn giản ta giả sử rằng không có mối ràng buộc Bây giờ bạn có hai giải thuật và tối thiểu một trong số chúng là sai. Ta tìm cách loại bỏ một thuậtoán sai T={5,2} và P={3,1} Theo giải thuật 1 p[1]-t[1] (p[2]/t[2]), do đó, nhiệm vụ đầu tiên là nên làm đầu tiên, và hàm đối tượng sẽ là Giải thuật 1 sẽ không cho bạn câu trả lời tối ưu, do đó, giải thuật 1 sẽ không đúng Lưu ý rằng: Giải thuật tham lam thường không chính xác. Bởi vị giải thuật 1 không chính xác, điều đó không có nghĩa rằng giải thuật 2 không hoàn toàn chính xác. Tuy nhiên, đối với giải thuật 2 này được chứng minh đúng đắn. Một thuật toán được thiết kế để đạt được giải pháp tối ưu cho một vấn đề nhất định. Theo cách tiếp cận thuật toán tham lam, các quyết định được đưa ra từ miền giải pháp đã cho. Vì tham lam, giải pháp gần nhất có vẻ cung cấp giải pháp tối ưu được chọn. Các thuật toán tham lam cố gắng tìm một giải pháp tối ưu cục bộ, cuối cùng có thể dẫn đến các giải pháp tối ưu hóa toàn cầu. Tuy nhiên, nhìn chung các thuật toán tham lam không cung cấp các giải pháp tối ưu hóa toàn cầu. Đếm tiềnYêu cầu là hãy lựa chọn số lượng đồng tiền nhỏ nhất có thể sao cho tổng mệnh giá của các đồng tiền này bằng với một lượng tiền cho trước. Nếu chúng tôi được cung cấp các đồng xu 1, 2, 5 và 10 và chúng tôi được yêu cầu đếm $ 18 thì thủ tục tham lam sẽ là:
Bạn thấy rằng cách làm trên là khá ổn, và số lượng đồng tiền cần phải lựa chọn là 4 đồng tiền. Nhưng nếu chúng ta thay đổi bài toán trên một chút thì cũng hướng tiếp cận như trên có thể sẽ không đem lại cùng kết quả tối ưu. Chẳng hạn, một hệ thống tiền tệ khác có các đồng tiền có mệnh giá lần lượt là 1, 7 và 10 xu và lượng tiền cho trước ở đây thay đổi thành 15 xu thì theo giải thuật tham lam thì số đồng tiền cần chọn sẽ nhiều hơn 4. Với giải thuật tham lam thì: 10 + 1 + 1 +1 + 1 + 1, vậy tổng cộng là 6 đồng tiền. Trong khi cùng bài toán như trên có thể được xử lý bằng việc chỉ chọn 3 đồng tiền (7 + 7 +1). Do đó chúng ta có thể kết luận rằng, giải thuật tham lam tìm kiếm giải pháp tôi ưu ở mỗi bước nhưng lại có thể thất bại trong việc tìm ra giải pháp tối ưu toàn cục. Có khá nhiều giải thuật nổi tiếng được thiết kế dựa trên tư tưởng của giải thuật tham lam. Dưới đây là một trong số các giải thuật này: |
