8.9K 674 107

Đã đăng vào thg 1 19, 2022 9:34 SA 14 phút đọc

1.8K

Tham lam (Greedy Method)

I. Tổng quan

1. Giới thiệu phương pháp

Trong bài viết trước, tôi đã giới thiệu tới các bạn về giải thuật Nhánh và Cận để giải bài toán tối ưu (nhấn vào đây để đọc lại bài viết). Mặc dù phương pháp Nhánh và Cận đã cải tiến từ phương pháp Quay lui nhằm loại bỏ đi nhiều nhánh nghiệm không tốt, nhưng thực tế thì việc đánh giá các nghiệm mở rộng là rất khó, thậm chí không thể làm được. Hoặc nếu đã loại bỏ đi các cận thì số lượng phương án có thể sinh ra vẫn còn rất lớn, không thể duyệt hết được. Trong các bài toán như vậy, thì phương pháp Tham lam (Greedy Method) là một phương án rất được ưa chuộng.

Tư tưởng chung của phương pháp là chấp nhận tìm ra các nghiệm gần đúng với nghiệm tối ưu (nghĩa là có thể sai), rồi tìm cách xây dựng một hàm tính toán độ tối ưu cho phương án sao cho khả năng ra được nghiệm tối ưu là lớn nhất có thể. Ưu điểm của phương pháp này là độ phức tạp khá nhỏ, và nếu triển khai đúng cách có thể cho ra nghiệm tối ưu nhanh hơn nhiều so với Quay lui hay Nhánh và Cận. Thực tế, có nhiều thuật toán sử dụng chiến lược giải thuật này và vẫn cho được kết quả tối ưu, chẳng hạn như Giải thuật Prim hay Kruskal để tìm cây khung nhỏ nhất trên đồ thị.

2. Ý tưởng

Giả sử các bạn có thể biểu diễn nghiệm của bài toán dưới dạng một vector $X = (x_1, x_2, \dots, x_n)$ và mỗi thành phần $x_i$ chọn ra từ một tập $S_i$ các ứng cử viên. Vẫn tương tự như trong bài toán tối ưu, các nghiệm sẽ được xác định độ tốt bằng một hàm $f(X),$ và mục tiêu là cần đi tìm nghiệm có $f(X)$ tốt nhất (theo nghĩa lớn nhất hoặc nhỏ nhất).

Khác với các chiến lược trước đó, ở chiến lược Tham lam, chúng ta sẽ tìm cách tối ưu lựa chọn ở từng thành phần nghiệm. Giả sử đã xây dựng được $i$ thành phần của nghiệm là $x_1, x_2, \dots, x_i,$ thì khi xây dựng thành phần $x_{i + 1},$ ta hãy cố gắng chọn nó là ứng cử viên "tốt nhất" trong tập ứng cử viên $S_{i + 1}$ . Để đánh giá được độ tốt của các ứng cử viên thì các bạn cần xây dựng một hàm chọn để làm điều đó. Tiếp tục xây dựng như vậy cho tới khi tạo ra đủ $n$ thành phần của nghiệm.

Giải thuật có thể mô tả bằng mô hình tổng quát như sau:

void greedy_method()
{
    X = empty;
    i = 0;
    while ({X_chưa_có_đủ_n_thành_phần})
    {
        i = i + 1;
        {Xác_định_S[i]}

        // Chọn ứng cử viên tốt nhất cho thành phần thứ i.
        x[i] = select_best(S[i]);
    }
}

Thực tế, trong nhiều bài toán, nếu như các bạn xây dựng được một hàm chọn select_best() phù hợp, kết quả thu được sẽ là kết quả tối ưu, chẳng hạn như trong các giải thuật trên đồ thị. Cùng phân tích một số bài toán sau đây để hiểu rõ hơn về Greedy nhé!

II. Một số bài toán minh họa

1. Phân số Ai Cập (Egyptian Fraction)

Đề bài

Mỗi phân số dương đều có thể được biểu diễn dưới dạng tổng của các phân số đơn vị khác nhau (phân số đơn vị là phân số có tử số bằng $1,$ và mẫu số là một số nguyên dương). Cách biểu diễn phân số như vậy được gọi là biểu diễn theo Phân số Ai Cập, và mỗi phân số có rất nhiều cách biểu diễn như vậy. Cho trước một phân số $\frac{a}{b},$ hãy tìm biểu diễn phân số Ai Cập của nó với số lượng số hạng là ít nhất có thể?

Input:

Một dòng duy nhất chứa hai số nguyên dương $a, b$ .

Ràng buộc:

$1 \le a < b \le 1000$ .

Output:

In ra các phân số trong phân tích tìm được, mỗi phân số trên một dòng theo thứ tự giảm dần về giá trị.

Sample Input:

6 14

Sample Output:

1 3
1 11
1 231

Phân tích ý tưởng

Nghiệm của bài toán được biểu diễn dưới dạng một vector $X = (x_1, x_2, \dots, x_n)$ sao cho:

$\frac{a}{b} = \frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n}$

với $x_1 < x_2 < \cdots < x_n,$ và $n$ nhỏ nhất có thể.

Mỗi phân số dương có tử số nhỏ hơn mẫu số đều có thể được rút gọn về một phân số tối giản. Vì thế, ta có thể áp dụng giải thuật tham lam như sau:

Nếu $\frac{a}{b}$ có mẫu số chia hết cho tử số thì bài toán đã có lời giải, vì khi đó nó có thể viết dưới dạng $\frac{1}{b \ \div \ a}$ .
Với một phân số $\frac{a}{b} \ (1 < a < b),$ tìm phân số đơn vị lớn nhất không vượt quá $\frac{a}{b}$ bằng cách tính giá trị $x = \left \lceil{\frac{b}{a}} \right\rceil,$ phân số đơn vị tìm được sẽ là $\frac{1}{x}$ . Sở dĩ ta tìm phân số $\frac{1}{x}$ lớn nhất là để cho số lượng số hạng tạo ra sẽ nhỏ nhất có thể.
Tiếp tục lặp lại quá trình trên với hiệu $\frac{a}{b} - \frac{1}{x},$ cho tới khi phân tích xong.

Giải thuật có độ phức tạp không ổn định, tùy thuộc vào việc lựa chọn các phân số đơn vị, tuy nhiên vẫn sẽ chạy rất nhanh.

Cài đặt

Cài đặt dưới đây sử dụng mô hình đệ quy để liên tục phân tích $\frac{a}{b}$ thành tổng của các phân số đơn vị $\frac{1}{x}$ :

#include <bits/stdc++.h>

using namespace std;

void egyptian_representation(int a, int b)
{
    // Nếu a = 0 hoặc b = 0 thì đã phân tích xong.
    if (a == 0 || b == 0)
        return;

    // Nếu b chia hết cho a thì rút gọn luôn về phân số đơn vị.
    if (b % a == 0)
    {
        cout << 1 << ' ' << b / a;
        return;
    }
	
    // Tìm phân số đơn vị lớn nhất không vượt quá a / b.
    int x = b / a + 1;
    cout << 1 << ' ' << x << endl;
	
    // Tiếp tục phân tích hiệu a / b - 1 / x.
    egyptian(a * x - b, b * x);
}

main()
{
    int a, b;
    cin >> a >> b;
	
    egyptian_representation(a, b);
}

2. Lựa chọn công việc (Activity Seletion Problem)

Đề bài

Một nhà máy đang có $n$ công việc cần hoàn thành, công việc thứ $i$ phải bắt đầu tại thời điểm $a_i$ và kết thúc tại thời điểm $b_i$ . Tuy nhiên, do nhân lực có hạn nên nhà máy đó không thể thực hiện nhiều công việc một lúc, mà chỉ có thể thực hiện một công việc tại một thời điểm.

Hãy tìm cách lựa chọn các công việc mà nhà máy sẽ làm sao cho số công việc được hoàn thành là nhiều nhất có thể?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ - số lượng công việc.
Trên $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i, b_i$ là thời điểm bắt đầu và thời điểm kết thúc của công việc thứ $i$ .

Ràng buộc:

$1 \le n \le 10^6$ .
$0 \le a_i, b_i \le 10^6; \forall i: 1 \le i \le n$ .

Output:

Đưa ra một số nguyên duy nhất là số lượng công việc tối đa có thể hoàn thành.

Sample Input:

Sample Output:

Explanation:

Lựa chọn các công việc số $6,$ số $3,$ số $2$ và số $4$ .

Phân tích ý tưởng

Giả sử đã lựa chọn được $i$ công việc để thực hiện là $(x_1, x_2, \dots, x_i)$ . Khi lựa chọn công việc $x_{i + 1},$ muốn phương án có thể tối ưu nhất, thì ta sẽ phải lựa chọn công việc nào có thời gian bắt đầu lớn hơn hoặc bằng thời gian kết thúc của công việc $x_i,$ nhưng thời gian kết thúc của $x_{i + 1}$ lại phải là nhỏ nhất.

Từ nhận xét trên, ta rút ra ý tưởng tham lam như sau:

Đầu tiên, sắp xếp các công việc tăng dần theo thời gian kết thúc.
Lựa chọn công việc đầu tiên vào danh sách các công việc sẽ làm. Coi công việc gần nhất vừa được chọn là công việc thứ $j$ .
Duyệt qua các công việc từ vị trí $2$ tới vị trí $n,$ nếu công việc nào có thời gian bắt đầu $(a_i)$ lớn hơn hoặc bằng thời gian kết thúc của công việc gần nhất vừa chọn $(b_j)$ thì lựa chọn nó, rồi cập nhật lại $j = i$ . Do các công việc đã được sắp xếp tăng dần theo thời gian kết thúc, nên công việc được chọn sẽ luôn luôn có thời gian kết thúc nhỏ nhất.

Chứng minh tính tối ưu

Phương pháp làm trên mặc dù là Tham lam, nhưng nó lại luôn luôn cho ra kết quả tối ưu. Thật vậy, hãy giả sử $S = \{x_1, x_2, \dots, x_n\}$ là danh sách các công việc đã được sắp xếp tăng dần theo thời gian kết thúc, và tập $A \subseteq S$ là một phương án lựa chọn tối ưu nhưng công việc đầu tiên được lựa chọn trong tập $A$ không phải là $x_1$ (như vậy không phải là cách chọn Tham lam). Khi đó ta có:

Đặt $k$ là chỉ số của công việc đầu tiên được chọn trong tập $A$ (tức là chọn $x_k$ đầu tiên). Gọi $B = \left(A \setminus \{k\}\right) \cup \{x_1\};$ có nghĩa $B$ là một phương án lựa chọn Tham lam với $x_1$ là công việc đầu tiên.
Ta có $b_1 \le b_k$ (vì dãy các công việc đã sắp xếp tăng dần). Bởi vì các công việc được chọn trong $A$ là hoàn toàn không giao nhau, nên chắc chắn các công việc trong $B$ cũng sẽ không giao nhau, do đó $|B| = |A|,$ suy ra $|B|$ cũng là một phương án lựa chọn tối ưu.
Ta tiếp tục chứng minh nếu như phương án $B$ là một phương án tối ưu được chọn theo phương pháp Tham lam, thì $B' = B \setminus \{x_1\}$ sẽ là một phương án tối ưu cho tập các công việc còn lại: $S' = \{x_i \in S: b_i \ge a_1 \}$ . Thật vậy, nếu như $B'$ không phải một phương án tối ưu cho $S',$ nghĩa là ta có thể chọn ra một phương án $A'$ gồm nhiều công việc hơn $B'$ theo phương pháp Tham lam đối với tập $S'$ . Sau đó, thêm $x_1$ vào tập $A'$ sẽ tạo thành một tập $A$ tối ưu hơn tập $B$ ban đầu, điều này mâu thuẫn với giả thiết $B$ là một phương án tối ưu.

Vì thế, phương pháp Tham lam sẽ luôn luôn cho ra kết quả tối ưu đối với bài toán lựa chọ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à:

Sắp xếp lại các công việc: $O(n \times \log n)$ .
Duyệt chọn các công việc: $O(n)$ .
Độ phức tạp tổng quát: $O(n \times \log n)$ .

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

Cài đặt

Trong solution dưới đây sẽ sử dụng cấu trúc pair trong C++ STL để lưu trữ các công việc cho thuận tiện.

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e5 + 10;
int n;
pair < int, int > activity[maxn];

void enter()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> activity[i].first >> activity[i].second;
}

bool cmp(pair < int, int > a, pair < int, int > b)
{
    return a.second < b.second;
}

void solution()
{
    sort(activity + 1, activity + n + 1, cmp);

    int res = 1;
    int last_index = 1;
    for (int i = 2; i <= n; ++i)
        if (activity[i].first >= activity[last_index].second)
        {
            last_index = i;
            ++res;
        }

    cout << res;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    enter();
    solution();

    return 0;
}

3. Rút tiền cây ATM

Đề bài

Một khách hàng muốn rút số tiền $T$ từ một cây ATM bên đường. Bên trong cây ATM hiện đang có $n$ tờ tiền có mệnh giá $a_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:

Dòng đầu tiên chứa hai số nguyên dương $n$ và $T$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ - mệnh giá của các tờ tiền.

Ràng buộc:

$1 \le n, T \le 1000$ .
$1 \le a_i \le 1000; \forall i: 1 \le i \le n$ .

Output:

In ra số nguyên duy nhất là số tờ tiền tối thiểu cần sử dụng. Nếu không có phương án trả tiền thì in ra $-1$ .

Sample Input:

5 10
1 4 2 3 6

Sample Output:

Phân tích ý tưởng

Với giới hạn này, bài toán không thể giải quyết bằng giải pháp Quay lui hay Nhánh và Cận. Phương pháp tốt nhất sẽ là Quy hoạch động, tuy nhiên ở đây tôi sẽ phân tích một ý tưởng Tham lam đơn giản như sau:

Sắp xếp các tờ tiền theo mệnh giá giảm dần.
Tại mỗi bước lựa chọn, luôn luôn chọn tờ tiền có mệnh giá lớn nhất và không vượt quá số tiền còn lại phải trả.

Giải thuật trên sẽ tìm ra nghiệm rất nhanh, tuy nhiên không phải luôn luôn tối ưu và cũng có thể sẽ không tìm được nghiệm. Đó chính là nhược điểm của phương pháp Tham lam mà chúng ta buộc phải chấp nhận.

Độ phức tạp: $O(n \times \log n),$ đó cũng chính là độ phức tạp của thao tác sắp xếp.

Cài đặt

#include <bits/stdc++.h>

using namespace std;

main()
{
    int n, T;
    cin >> n >> T;

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

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

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

    // Tìm được nghiệm thì in ra số tờ tiền cần dùng.
    // Ngược lại in ra -1.
    if (T == 0)
        cout << res;
    else
        cout << -1;

    return 0;
}

Theo cách làm này, nếu như bộ dữ liệu vào là:

6 100
50 20 20 20 20 20

Thì kết quả in ra sẽ là:

-1

Dễ thấy kết quả này hoàn toàn sai, vì bài toán vẫn có nghiệm là $5$ .

III. Tài liệu tham khảo

I. Tổng quan

1. Giới thiệu phương pháp

2. Ý tưởng

II. Một số bài toán minh họa

1. Phân số Ai Cập (Egyptian Fraction)

Đề bài

Phân tích ý tưởng

Cài đặt

2. Lựa chọn công việc (Activity Seletion Problem)

Đề bài

Phân tích ý tưởng

Chứng minh tính tối ưu

Cài đặt

3. Rút tiền cây ATM

Đề bài

Phân tích ý tưởng

Cài đặt

III. Tài liệu tham khảo

Mục lục