Tham lam (Greedy Method)

Contents

1 Giới thiệu phương pháp
2 Ý tưởng
3 Phân số Ai Cập (Egyptian Fraction)

Giới thiệu phương pháp

Trong bài viết trước, đã giới thiệu về giải thuật Nhánh và Cận để giải bài toán tối ưu. 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.

Có thể bạn quan tâm

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.

Bạn đang xem: Tham lam (Greedy Method)

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ị.

Ý tưởng

Giả 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) và mỗi thành phần xi chọn ra từ một tập Si 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), và mục tiêu là cần đi tìm nghiệm có 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 i thành phần của nghiệm là x1,x2,…,xi, thì khi xây dựng thành phần xi+1, 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+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 đến khi tạo ra đủ n 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:

void greedy_method() {
    X = empty;
    i = 0;
    while ({X_chưa_có_đủ_n_thành_phần}) {
        i = i + 1;
        {Xác_định_S[i]} // Chọn ứng cử viên tốt nhất cho thành phần thứ i.
        x[i] = select_best(S[i]);
    }
}

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 select_best() 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é!

Đề bài

Xem thêm : Học phí mới nhất tại Đại học Kinh doanh và Công nghệ Hà Nội

Mỗ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 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ố 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:

Một dòng duy nhất chứa hai số nguyên dương a,b là tử số và mẫu số của phân số.

Ràng buộc:

1≤a

Output:

In ra các phân số trong phân tích tìm được, mỗi phân số trên một dòng theo thứ tự giảm dần về giá trị.

Sample Input:

6 14

Sample Output:

1 3
1 11
1 231

Phân tích ý tưởng

Nghiệm của bài toán được biểu diễn dưới dạng một vector X=(x1,x2,…,xn) sao cho:

a/b=1/x1+1/x2+⋯+1/xn

Xem thêm : Gợi ý 7 bài tập Scratch đơn giản dành cho trẻ

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:

Nếu a/b có mẫu số chia hết cho tử số thì bài toán đã có lời giải, vì khi đó nó có thể viết dưới dạng 1/b ÷ a (1/b ÷ a = 1/b * 1/a).
Với một phân số a/b (1x=⌈b/a⌉, phân số đơn vị tìm được sẽ là 1/x.
Tiếp tục lặp lại quá trình trên với hiệu a/b – 1/x, cho tới khi phân tích xong.

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.

Các bước trong thuật toán trên có độ phức tạp lần lượt là:

Sắp xếp lại các phân số: O(n×log⁡n)
Duyệt chọn các phân số: O(n)
Độ phức tạp tổng quát: O(n×log⁡n)

Vì vậy độ phức tạp tổng quát của giải thuật là O(n×log⁡n).

Cài đặt

Trong solution dưới đây sẽ sử dụng cấu trúc pair trong C++ STL để lưu trữ các công việc cho thuận tiện.

#include 
using namespace std;

main() {
    int n, T;
    cin >> n >> T;
    vector  a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    sort(a.begin() + 1, a.end(), greater ());

    int res = 0;
    for (int i = 1; i <= n; ++i)
        if (T >= a[i]) {
            T -= a[i];
            ++res;
        }

    // Tìm được nghiệm thì in ra số tờ tiền cần dùng.
    // Ngược lại in ra -1.
    if (T == 0)
        cout << res;
    else
        cout << -1;

    return 0;
}

Theo cách làm này, nếu như bộ dữ liệu vào là: