Trong bài viết trước, tôi đã giới thiệu tới các bạn về giải thuật Nhánh và Cận để giải bài toán tối ưu (nhấn vào đây để đọc lại bài viết). Mặc dù phương pháp Nhánh và Cận đã cải tiến từ phương pháp Quay lui nhằm loại bỏ đi nhiều nhánh nghiệm không tốt, nhưng thực tế thì việc đánh giá các nghiệm mở rộng là rất khó, thậm chí không thể làm được. Hoặc nếu đã loại bỏ đi các cận thì số lượng phương án có thể sinh ra vẫn còn rất lớn, không thể duyệt hết được. Trong các bài toán như vậy, thì phương pháp Tham lam (Greedy Method) là một phương án rất được ưa chuộng. Show Tư tưởng chung của phương pháp là chấp nhận tìm ra các nghiệm gần đúng với nghiệm tối ưu (nghĩa là có thể sai), rồi tìm cách xây dựng một hàm tính toán độ tối ưu cho phương án sao cho khả năng ra được nghiệm tối ưu là lớn nhất có thể. Ưu điểm của phương pháp này là độ phức tạp khá nhỏ, và nếu triển khai đúng cách có thể cho ra nghiệm tối ưu nhanh hơn nhiều so với Quay lui hay Nhánh và Cận. Thực tế, có nhiều thuật toán sử dụng chiến lược giải thuật này và vẫn cho được kết quả tối ưu, chẳng hạn như Giải thuật Prim hay Kruskal để tìm cây khung nhỏ nhất trên đồ thị. 2. Ý tưởngGiả sử các bạn có thể biểu diễn nghiệm của bài toán dưới dạng một vector X=(x1,x2,…,xn)X = (x_1, x_2, \dots, x_n) và mỗi thành phần xix_i chọn ra từ một tập SiS_i các ứng cử viên. Vẫn tương tự như trong bài toán tối ưu, các nghiệm sẽ được xác định độ tốt bằng một hàm f(X),f(X), và mục tiêu là cần đi tìm nghiệm có f(X)f(X) tốt nhất (theo nghĩa lớn nhất hoặc nhỏ nhất). Khác với các chiến lược trước đó, ở chiến lược Tham lam, chúng ta sẽ tìm cách tối ưu lựa chọn ở từng thành phần nghiệm. Giả sử đã xây dựng được ii thành phần của nghiệm là x1,x2,…,xi,x_1, x_2, \dots, x_i, thì khi xây dựng thành phần xi+1,x_{i + 1}, ta hãy cố gắng chọn nó là ứng cử viên "tốt nhất" trong tập ứng cử viên Si+1S_{i + 1}. Để đánh giá được độ tốt của các ứng cử viên thì các bạn cần xây dựng một hàm chọn để làm điều đó. Tiếp tục xây dựng như vậy cho tới khi tạo ra đủ nn thành phần của nghiệm. Giải thuật có thể mô tả bằng mô hình tổng quát như sau:
Thực tế, trong nhiều bài toán, nếu như các bạn xây dựng được một hàm chọn
2 phù hợp, kết quả thu được sẽ là kết quả tối ưu, chẳng hạn như trong các giải thuật trên đồ thị. Cùng phân tích một số bài toán sau đây để hiểu rõ hơn về Greedy nhé! II. Một số bài toán minh họa1. Phân số Ai Cập (Egyptian Fraction)Đề bàiMỗi phân số dương đều có thể được biểu diễn dưới dạng tổng của các phân số đơn vị khác nhau (phân số đơn vị là phân số có tử số bằng 1,1, và mẫu số là một số nguyên dương). Cách biểu diễn phân số như vậy được gọi là biểu diễn theo Phân số Ai Cập, và mỗi phân số có rất nhiều cách biểu diễn như vậy. Cho trước một phân số ab,\frac{a}{b}, hãy tìm biểu diễn phân số Ai Cập của nó với số lượng số hạng là ít nhất có thể? Input:
Ràng buộc:
Output:
Sample Input:
Sample Output:
Phân tích ý tưởngNghiệm của bài toán được biểu diễn dưới dạng một vector X=(x1,x2,…,xn)X = (x_1, x_2, \dots, x_n) sao cho: ab=1x1+1x2+⋯+1xn\frac{a}{b} = \frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n} với x1<x2<⋯<xn,x_1 < x_2 < \cdots < x_n, và nn nhỏ nhất có thể. Mỗi phân số dương có tử số nhỏ hơn mẫu số đều có thể được rút gọn về một phân số tối giản. Vì thế, ta có thể áp dụng giải thuật tham lam như sau:
Giải thuật có độ phức tạp không ổn định, tùy thuộc vào việc lựa chọn các phân số đơn vị, tuy nhiên vẫn sẽ chạy rất nhanh. Cài đặtCài đặt dưới đây sử dụng mô hình đệ quy để liên tục phân tích ab\frac{a}{b} thành tổng của các phân số đơn vị 1x\frac{1}{x}:
2. Lựa chọn công việc (Activity Seletion Problem)Đề bàiMột nhà máy đang có nn công việc cần hoàn thành, công việc thứ ii phải bắt đầu tại thời điểm aia_i và kết thúc tại thời điểm bib_i. Tuy nhiên, do nhân lực có hạn nên nhà máy đó không thể thực hiện nhiều công việc một lúc, mà chỉ có thể thực hiện một công việc tại một thời điểm. Hãy tìm cách lựa chọn các công việc mà nhà máy sẽ làm sao cho số công việc được hoàn thành là nhiều nhất có thể? Input:
Ràng buộc:
Output:
Sample Input:
Sample Output:
Explanation: Lựa chọn các công việc số 6,6, số 3,3, số 22 và số 44. Phân tích ý tưởngGiả sử đã lựa chọn được ii công việc để thực hiện là (x1,x2,…,xi)(x_1, x_2, \dots, x_i). Khi lựa chọn công việc xi+1,x_{i + 1}, muốn phương án có thể tối ưu nhất, thì ta sẽ phải lựa chọn công việc nào có thời gian bắt đầu lớn hơn hoặc bằng thời gian kết thúc của công việc xi,x_i, nhưng thời gian kết thúc của xi+1x_{i + 1} lại phải là nhỏ nhất. Từ nhận xét trên, ta rút ra ý tưởng tham lam như sau:
Chứng minh tính tối ưuPhương pháp làm trên mặc dù là Tham lam, nhưng nó lại luôn luôn cho ra kết quả tối ưu. Thật vậy, hãy giả sử S={x1,x2,…,xn}S = \{x_1, x_2, \dots, x_n\} là danh sách các công việc đã được sắp xếp tăng dần theo thời gian kết thúc, và tập A⊆SA \subseteq S là một phương án lựa chọn tối ưu nhưng công việc đầu tiên được lựa chọn trong tập AA không phải là x1x_1 (như vậy không phải là cách chọn Tham lam). Khi đó ta có:
Vì thế, phương pháp Tham lam sẽ luôn luôn cho ra kết quả tối ưu đối với bài toán lựa chọn công việc. Các bước trong thuật toán trên có độ phức tạp lần lượt là:
Vì vậy độ phức tạp tổng quát của giải thuật là O(n×logn)O(n \times \log n). Cài đặtTrong solution dưới đây sẽ sử dụng cấu trúc
3 trong C++ STL để lưu trữ các công việc cho thuận tiện.
3. Rút tiền cây ATMĐề bàiMột khách hàng muốn rút số tiền TT từ một cây ATM bên đường. Bên trong cây ATM hiện đang có nn tờ tiền có mệnh giá a1,a2,…,ana_1, a_2,…, a_n. Hãy tìm một cách trả tiền của máy ATM cho khách hàng? Input:
Ràng buộc:
Output:
Sample Input:
Sample Output:
Phân tích ý tưởngVới giới hạn này, bài toán không thể giải quyết bằng giải pháp Quay lui hay Nhánh và Cận. Phương pháp tốt nhất sẽ là Quy hoạch động, tuy nhiên ở đây tôi sẽ phân tích một ý tưởng Tham lam đơn giản như sau:
Giải thuật trên sẽ tìm ra nghiệm rất nhanh, tuy nhiên không phải luôn luôn tối ưu và cũng có thể sẽ không tìm được nghiệm. Đó chính là nhược điểm của phương pháp Tham lam mà chúng ta buộc phải chấp nhận. |