Khóa học CTDL và GT

Bài 17.2. Bài toán lập lịch và thuật toán tham lam

Trong thế giới lập trình và tối ưu hóa tài nguyên, bài toán lập lịch (scheduling problem) là một lớp bài toán cực kỳ phổ biến. Tưởng tượng bạn có một tài nguyên duy nhất (chẳng hạn như một phòng họp, một máy chủ, hoặc thậm chí là chính thời gian của bạn) và một danh sách các công việc hoặc hoạt động cần được thực hiện. Mỗi hoạt động có một thời điểm bắt đầu và một thời điểm kết thúc. Vấn đề là: Làm thế nào để chọn ra được số lượng hoạt động nhiều nhất có thể thực hiện được trên tài nguyên đó, biết rằng hai hoạt động được chọn không được phép chồng lấn về thời gian?

Đây chính là Bài toán lựa chọn hoạt động (Activity Selection Problem) cổ điển, một ví dụ tuyệt vời để giới thiệu về thuật toán tham lam (Greedy Algorithm).

Bài toán Lựa chọn Hoạt động (Activity Selection Problem)

Chúng ta được cho một tập hợp $N$ hoạt động, ký hiệu là $S = {a_1, a_2, \dots, a_N}$. Mỗi hoạt động $a_i$ được xác định bởi một thời gian bắt đầu $s_i$ và một thời gian kết thúc $f_i$.

• Input: Tập hợp các hoạt động $S$, trong đó mỗi hoạt động $a_i$ có cặp thời gian $(s_i, f_i)$.
• Output: Một tập hợp con các hoạt động từ $S$ sao cho không có hai hoạt động nào trong tập con đó bị chồng lấn về thời gian, và số lượng hoạt động trong tập con này là lớn nhất có thể.

Hai hoạt động $a_i$ và $a_j$ được coi là không chồng lấn nếu khoảng thời gian $[s_i, f_i)$ và $[s_j, f_j)$ không giao nhau. Điều này có nghĩa là hoặc $f_i \le s_j$ hoặc $f_j \le s_i$. (Thông thường, chúng ta xem xét các khoảng thời gian nửa mở $[s_i, f_i)$, tức là hoạt động bắt đầu tại $s_i$ và kết thúc ngay trước $f_i$. Nếu một hoạt động kết thúc đúng lúc hoạt động khác bắt đầu, chúng không bị chồng lấn).

Nếu cố gắng liệt kê và kiểm tra tất cả các tập hợp con có thể có của $N$ hoạt động để tìm tập con hợp lệ lớn nhất, chúng ta sẽ phải đối mặt với $2^N$ khả năng – một con số khổng lồ và không khả thi ngay cả với giá trị $N$ tương đối nhỏ. Rõ ràng, cần một phương pháp hiệu quả hơn.

Sức mạnh của Thuật toán Tham lam

Thuật toán tham lam là một kỹ thuật thiết kế giải thuật mà ở mỗi bước, nó đưa ra lựa chọn tốt nhất tại thời điểm hiện tại (lựa chọn cục bộ tối ưu), với hy vọng rằng chuỗi các lựa chọn cục bộ tối ưu này sẽ dẫn đến giải pháp tổng thể tối ưu. Tuy nhiên, không phải bài toán nào cũng có thể giải được bằng thuật toán tham lam; việc chứng minh tính đúng đắn là cực kỳ quan trọng.

Đối với Bài toán lựa chọn hoạt động, trực giác tham lam nào có thể hiệu quả?

1. Chọn hoạt động ngắn nhất? Không hẳn. Hoạt động ngắn có thể ngăn cản việc chọn hai hoạt động dài hơn nhưng không chồng lấn.
2. Chọn hoạt động bắt đầu sớm nhất? Cũng không. Hoạt động bắt đầu sớm nhất có thể kéo dài rất lâu, loại bỏ khả năng chọn nhiều hoạt động khác.
3. Chọn hoạt động kết thúc sớm nhất? Đây rồi! Đây chính là lựa chọn tham lam dẫn đến giải pháp tối ưu.

Tại sao việc chọn hoạt động kết thúc sớm nhất lại hiệu quả? Ý tưởng là: bằng cách chọn hoạt động kết thúc sớm nhất, chúng ta sẽ giải phóng tài nguyên sớm nhất có thể, để lại khoảng thời gian lớn nhất còn lại cho các hoạt động tiếp theo. Về mặt trực giác, điều này tối đa hóa cơ hội để chọn được nhiều hoạt động còn lại.

Chứng minh (hay ít nhất là giải thích mạnh mẽ) tính đúng đắn

Giả sử chúng ta có một tập hợp hoạt động $S$. Hãy sắp xếp các hoạt động theo thời gian kết thúc tăng dần. Gọi hoạt động kết thúc sớm nhất trong $S$ là $a_1$.

• Khẳng định Tham lam: Luôn có một giải pháp tối ưu cho $S$ mà chứa hoạt động $a_1$.

• Chứng minh (phác thảo): Giả sử có một giải pháp tối ưu $O$ cho $S$ mà không chứa $a_1$. Gọi hoạt động đầu tiên trong $O$ (hoạt động kết thúc sớm nhất trong $O$) là $a_k$. Vì $a_1$ là hoạt động kết thúc sớm nhất trong toàn bộ tập $S$, nên $f_1 \le f_k$.

  Bây giờ, hãy xét tập hợp $O' = O \setminus {a_k} \cup {a_1}$. Nghĩa là, chúng ta loại bỏ hoạt động $a_k$ khỏi giải pháp tối ưu $O$ và thay thế nó bằng hoạt động $a_1$.

  • $O'$ có phải là một tập hợp các hoạt động không chồng lấn không?
    • $a_1$ không chồng lấn với bất kỳ hoạt động nào trong $O \setminus {a_k}$? Vì $a_k$ là hoạt động kết thúc sớm nhất trong $O$, và $f_1 \le f_k$, hoạt động $a_1$ kết thúc không muộn hơn hoạt động $a_k$. Bất kỳ hoạt động nào khác $a_j$ trong $O \setminus {a_k}$ đều bắt đầu sau $a_k$ kết thúc (vì $a_j$ và $a_k$ không chồng lấn trong $O$). Tức là $s_j \ge f_k$. Vì $f_1 \le f_k \le s_j$, hoạt động $a_1$ chắc chắn không chồng lấn với bất kỳ hoạt động nào trong $O \setminus {a_k}$. Vậy, $O'$ là một tập hợp các hoạt động không chồng lấn.
  • Số lượng hoạt động trong $O'$ là $|O| - 1 + 1 = |O|$. Vì $O$ là giải pháp tối ưu, $|O|$ là số lượng hoạt động lớn nhất có thể. $O'$ có cùng số lượng hoạt động và là tập hợp hợp lệ, nên $O'$ cũng là một giải pháp tối ưu.

  Kết luận: Chúng ta đã chứng minh rằng nếu có một giải pháp tối ưu không chứa hoạt động kết thúc sớm nhất ($a_1$), chúng ta có thể xây dựng một giải pháp tối ưu khác có chứa $a_1$. Điều này củng cố ý tưởng rằng việc chọn hoạt động kết thúc sớm nhất tại mỗi bước là một lựa chọn an toàn và dẫn đến giải pháp tối ưu tổng thể.

Thuật toán Tham lam cho Bài toán Lựa chọn Hoạt động

Dựa trên nguyên tắc "chọn hoạt động kết thúc sớm nhất", thuật toán của chúng ta sẽ như sau:

1. Sắp xếp: Sắp xếp tất cả các hoạt động theo thời gian kết thúc tăng dần.
2. Chọn hoạt động đầu tiên: Chọn hoạt động đầu tiên trong danh sách đã sắp xếp (hoạt động này có thời gian kết thúc sớm nhất). Thêm hoạt động này vào tập kết quả.
3. Lặp và chọn tiếp: Duyệt qua các hoạt động còn lại trong danh sách đã sắp xếp. Đối với mỗi hoạt động, kiểm tra xem nó có bị chồng lấn với hoạt động đã chọn gần nhất hay không.
4. Tiêu chí chọn: Nếu một hoạt động không bị chồng lấn với hoạt động đã chọn gần nhất (tức là thời gian bắt đầu của hoạt động hiện tại lớn hơn hoặc bằng thời gian kết thúc của hoạt động đã chọn gần nhất), hãy chọn nó và thêm vào tập kết quả. Cập nhật hoạt động đã chọn gần nhất.
5. Kết thúc: Tiếp tục cho đến khi duyệt hết tất cả các hoạt động. Tập kết quả thu được là tập hợp các hoạt động không chồng lấn có số lượng lớn nhất.

Ví dụ minh họa

Hãy xem xét tập hợp các hoạt động sau với thời gian bắt đầu ($s_i$) và kết thúc ($f_i$):

Bước 1: Sắp xếp theo thời gian kết thúc tăng dần:

Sắp xếp lại cho đúng thứ tự kết thúc:

Okay, danh sách đã sắp xếp lại theo thời gian kết thúc: a(1,4), b(3,5), c(0,6), d(5,7), e(3,9), f(5,9), g(6,10), h(8,11), i(8,12), j(2,14), k(12,16).

Bước 2: Chọn hoạt động đầu tiên:

Chọn a (1,4). Tập kết quả = {a}. Thời gian kết thúc của hoạt động đã chọn gần nhất là 4.

Bước 3 & 4: Lặp và chọn tiếp:

• Xét b (3,5): Bắt đầu (3) không lớn hơn hoặc bằng kết thúc của a (4). Bỏ qua.
• Xét c (0,6): Bắt đầu (0) không lớn hơn hoặc bằng kết thúc của a (4). Bỏ qua.
• Xét d (5,7): Bắt đầu (5) lớn hơn hoặc bằng kết thúc của a (4). Chọn d. Tập kết quả = {a, d}. Thời gian kết thúc của hoạt động đã chọn gần nhất là 7.
• Xét e (3,9): Bắt đầu (3) không lớn hơn hoặc bằng kết thúc của d (7). Bỏ qua.
• Xét f (5,9): Bắt đầu (5) không lớn hơn hoặc bằng kết thúc của d (7). Bỏ qua.
• Xét g (6,10): Bắt đầu (6) không lớn hơn hoặc bằng kết thúc của d (7). Bỏ qua.
• Xét h (8,11): Bắt đầu (8) lớn hơn hoặc bằng kết thúc của d (7). Chọn h. Tập kết quả = {a, d, h}. Thời gian kết thúc của hoạt động đã chọn gần nhất là 11.
• Xét i (8,12): Bắt đầu (8) không lớn hơn hoặc bằng kết thúc của h (11). Bỏ qua.
• Xét j (2,14): Bắt đầu (2) không lớn hơn hoặc bằng kết thúc của h (11). Bỏ qua.
• Xét k (12,16): Bắt đầu (12) lớn hơn hoặc bằng kết thúc của h (11). Chọn k. Tập kết quả = {a, d, h, k}. Thời gian kết thúc của hoạt động đã chọn gần nhất là 16.

Bước 5: Kết thúc: Đã duyệt hết danh sách.

Kết quả thu được là tập hợp {a, d, h, k} với tổng cộng 4 hoạt động. Đây chính là số lượng hoạt động không chồng lấn lớn nhất có thể chọn từ tập ban đầu.

Triển khai bằng C++

Chúng ta sẽ cần một cấu trúc để lưu trữ thông tin về mỗi hoạt động, sau đó sử dụng std::sort với một hàm so sánh tùy chỉnh để sắp xếp các hoạt động theo thời gian kết thúc. Cuối cùng, chúng ta duyệt qua danh sách đã sắp xếp để áp dụng logic tham lam.

#include <iostream>
#include <vector>
#include <algorithm> // Để sử dụng std::sort

// Cấu trúc để biểu diễn một hoạt động
struct Activity {
    int start; // Thời gian bắt đầu
    int finish; // Thời gian kết thúc

    // Thêm tên hoặc id hoạt động để dễ theo dõi kết quả (tùy chọn)
    char name;
};

// Hàm so sánh tùy chỉnh để sắp xếp vector các Activity
// Sắp xếp theo thời gian kết thúc tăng dần
bool compareActivities(const Activity& a, const Activity& b) {
    return a.finish < b.finish;
}

// Hàm thực hiện thuật toán tham lam cho bài toán lựa chọn hoạt động
void solveActivitySelection(std::vector<Activity>& activities) {
    // Bước 1: Sắp xếp các hoạt động theo thời gian kết thúc tăng dần
    // std::sort(activities.begin(), activities.end(), compareActivities);
    // Hoặc dùng lambda expression cho tiện lợi:
    std::sort(activities.begin(), activities.end(), 
              [](const Activity& a, const Activity& b) {
                return a.finish < b.finish;
              });


    std::cout << "Danh sách hoạt động đã sắp xếp theo thời gian kết thúc:" << std::endl;
    for (const auto& act : activities) {
        std::cout << act.name << "(" << act.start << ", " << act.finish << ") ";
    }
    std::cout << std::endl << std::endl;

    std::cout << "Các hoạt động được chọn:" << std::endl;

    // Bước 2: Chọn hoạt động đầu tiên (hoạt động kết thúc sớm nhất)
    // activities không rỗng vì ta đã kiểm tra ở main
    std::cout << activities[0].name << "(" << activities[0].start << ", " << activities[0].finish << ") ";

    // Biến lưu thời gian kết thúc của hoạt động được chọn gần nhất
    int last_finish_time = activities[0].finish;

    // Bước 3 & 4: Lặp qua các hoạt động còn lại và chọn
    for (size_t i = 1; i < activities.size(); ++i) {
        // Nếu thời gian bắt đầu của hoạt động hiện tại
        // lớn hơn hoặc bằng thời gian kết thúc của hoạt động đã chọn gần nhất
        if (activities[i].start >= last_finish_time) {
            std::cout << activities[i].name << "(" << activities[i].start << ", " << activities[i].finish << ") ";

            // Cập nhật thời gian kết thúc của hoạt động đã chọn gần nhất
            last_finish_time = activities[i].finish;
        }
    }
    std::cout << std::endl;
}

int main() {
    // Dữ liệu ví dụ từ bảng trên
    std::vector<Activity> activities = {
        {1, 4, 'a'}, {3, 5, 'b'}, {0, 6, 'c'}, {5, 7, 'd'},
        {3, 9, 'e'}, {5, 9, 'f'}, {6, 10, 'g'}, {8, 11, 'h'},
        {8, 12, 'i'}, {2, 14, 'j'}, {12, 16, 'k'}
    };

    if (activities.empty()) {
        std::cout << "Không có hoạt động nào để lập lịch." << std::endl;
        return 0;
    }

    solveActivitySelection(activities);

    // Ví dụ khác để kiểm tra
    std::cout << "\n--- Ví dụ khác ---" << std::endl;
     std::vector<Activity> activities2 = {
        {7, 9, 'A'}, {0, 10, 'B'}, {4, 8, 'C'}, {1, 3, 'D'}, {10, 12, 'E'}
    };
     if (activities2.empty()) {
        std::cout << "Không có hoạt động nào để lập lịch." << std::endl;
    } else {
        solveActivitySelection(activities2);
    }


    return 0;
}

Giải thích code C++:

1. struct Activity: Chúng ta định nghĩa một cấu trúc đơn giản để lưu trữ thời gian bắt đầu (start), thời gian kết thúc (finish) của mỗi hoạt động và một ký tự name để dễ dàng nhận diện hoạt động trong output.
2. compareActivities function (hoặc lambda): Đây là một hàm/biểu thức so sánh được sử dụng bởi std::sort. Nó nhận hai đối tượng Activity và trả về true nếu hoạt động thứ nhất có thời gian kết thúc sớm hơn hoạt động thứ hai. Điều này đảm bảo std::sort sẽ sắp xếp vector activities theo thứ tự tăng dần của thời gian kết thúc.
3. solveActivitySelection function:
   • Nó nhận một vector các Activity làm đầu vào (truyền bằng tham chiếu để có thể sắp xếp trực tiếp trên vector gốc nếu cần, dù ở đây không ảnh hưởng đến tính đúng đắn).
   • std::sort(activities.begin(), activities.end(), ...): Dòng này thực hiện việc sắp xếp vector activities dựa trên tiêu chí kết thúc sớm nhất sử dụng hàm so sánh đã định nghĩa.
   • Sau khi sắp xếp, hoạt động tại activities[0] là hoạt động kết thúc sớm nhất trong toàn bộ tập hợp. Chúng ta chọn nó và in ra.
   • last_finish_time được khởi tạo bằng thời gian kết thúc của hoạt động đầu tiên được chọn. Biến này sẽ theo dõi thời gian kết thúc của hoạt động được chọn gần nhất tính đến thời điểm hiện tại.
   • Vòng lặp for (size_t i = 1; i < activities.size(); ++i): Bắt đầu duyệt từ hoạt động thứ hai trong danh sách đã sắp xếp (vì hoạt động đầu tiên đã được chọn).
   • if (activities[i].start >= last_finish_time): Đây là điều kiện cốt lõi của thuật toán tham lam. Nó kiểm tra xem hoạt động hiện tại (activities[i]) có bắt đầu sau hoặc đúng vào lúc hoạt động đã chọn gần nhất kết thúc hay không. Nếu có, hai hoạt động này không chồng lấn.
   • Nếu điều kiện đúng, chúng ta chọn hoạt động hiện tại, in nó ra, và cập nhật last_finish_time bằng thời gian kết thúc của hoạt động vừa mới được chọn.
   • Nếu điều kiện sai (hoạt động hiện tại bắt đầu trước khi hoạt động đã chọn gần nhất kết thúc), chúng ta bỏ qua hoạt động hiện tại và tiếp tục vòng lặp.
4. main function:
   • Tạo một vector activities với dữ liệu ví dụ.
   • Kiểm tra xem vector có rỗng không (để tránh lỗi truy cập index 0).
   • Gọi hàm solveActivitySelection để chạy thuật toán và in kết quả.
   • Thêm một ví dụ khác (activities2) để minh họa thêm.

Output dự kiến từ code

Với ví dụ đầu tiên:

Danh sách hoạt động đã sắp xếp theo thời gian kết thúc:
a(1, 4) b(3, 5) c(0, 6) d(5, 7) e(3, 9) f(5, 9) g(6, 10) h(8, 11) i(8, 12) j(2, 14) k(12, 16) 

Các hoạt động được chọn:
a(1, 4) d(5, 7) h(8, 11) k(12, 16)

Output này khớp chính xác với quá trình làm tay của chúng ta.

Với ví dụ thứ hai: {A(7,9), B(0,10), C(4,8), D(1,3), E(10,12)} Sắp xếp theo thời gian kết thúc: {D(1,3), C(4,8), A(7,9), B(0,10), E(10,12)}

1. Chọn D(1,3). last_finish_time = 3.
2. Xét C(4,8): Bắt đầu (4) >= last_finish_time (3). Chọn C. last_finish_time = 8.
3. Xét A(7,9): Bắt đầu (7) < last_finish_time (8). Bỏ qua.
4. Xét B(0,10): Bắt đầu (0) < last_finish_time (8). Bỏ qua.
5. Xét E(10,12): Bắt đầu (10) >= last_finish_time (8). Chọn E. last_finish_time = 12.

Output dự kiến:

--- Ví dụ khác ---
Danh sách hoạt động đã sắp xếp theo thời gian kết thúc:
D(1, 3) C(4, 8) A(7, 9) B(0, 10) E(10, 12) 

Các hoạt động được chọn:
D(1, 3) C(4, 8) E(10, 12)

(Lưu ý: Output có thể khác nếu có hoạt động có cùng thời gian kết thúc và bắt đầu, tùy thuộc vào thứ tự ban đầu hoặc cách sắp xếp xử lý các trường hợp bằng nhau. Nhưng số lượng hoạt động được chọn vẫn là tối đa).

Phân tích độ phức tạp

• Độ phức tạp về thời gian:

  • Bước tốn thời gian nhất trong thuật toán là sắp xếp các hoạt động. Nếu có $N$ hoạt động, việc sắp xếp mất thời gian $O(N \log N)$.
  • Việc duyệt qua danh sách đã sắp xếp và chọn các hoạt động chỉ mất $O(N)$ thời gian.
  • Vậy, độ phức tạp thời gian tổng thể của thuật toán tham lam này là $O(N \log N)$, bị chi phối bởi bước sắp xếp.

• Độ phức tạp về không gian:

  • Nếu không tính không gian lưu trữ input ban đầu, thuật toán chỉ cần một vài biến phụ để theo dõi thời gian kết thúc (last_finish_time) và tập kết quả (lưu trữ các hoạt động được chọn, tối đa $N$ hoạt động).
  • std::sort có thể yêu cầu không gian phụ thuộc vào cài đặt (thường là $O(\log N)$ hoặc $O(N)$ trong trường hợp xấu nhất).
  • Tổng thể, độ phức tạp không gian thường được coi là $O(N)$ để lưu trữ kết quả hoặc có thể là $O(\log N)$ hoặc $O(N)$ tùy thuộc vào cài đặt sắp xếp.

Đây là một giải thuật rất hiệu quả so với phương pháp thử tất cả các tập con ($O(2^N)$).

Bài tập ví dụ:

[Tham Lam].Coin Change.

Tại ngân hàng có các mệnh giá bằng 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000. Tổng số tiền cần đổi có giá trị bằng N. Hãy xác định xem có ít nhất bao nhiêu tờ tiền sau khi đổi tiền?

Input Format

Dòng đầu tiên là số lượng bộ test T (T ≤ 50). Mỗi test gồm 1 số nguyên N (1 ≤ N ≤ 10^9).

Constraints

.

Output Format

Với mỗi test, in ra đáp án trên một dòng.

Ví dụ:

Dữ liệu vào

2
70
121

Dữ liệu ra

2
3

Đây là hướng dẫn giải bài [Tham Lam].Coin Change sử dụng thuật toán Tham lam (Greedy):

1. Nhận diện bài toán: Đây là bài toán đổi tiền kinh điển, và với các mệnh giá tiền tiêu chuẩn như 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, thuật toán tham lam luôn cho kết quả tối ưu (số lượng tờ tiền ít nhất).
2. Ý tưởng tham lam: Luôn ưu tiên sử dụng các tờ tiền có mệnh giá lớn nhất có thể để đổi số tiền còn lại.
3. Các bước thực hiện:
   • Lưu trữ các mệnh giá tiền vào một mảng hoặc vector, sắp xếp theo thứ tự giảm dần (từ lớn đến nhỏ).
   • Khởi tạo biến đếm tổng số tờ tiền về 0.
   • Lặp qua từng mệnh giá trong danh sách đã sắp xếp (từ lớn đến nhỏ).
   • Với mỗi mệnh giá, tính số lượng tờ tiền có mệnh giá đó cần dùng bằng cách lấy tổng số tiền còn lại chia nguyên cho mệnh giá hiện tại.
   • Cộng số lượng này vào biến đếm tổng số tờ tiền.
   • Cập nhật lại tổng số tiền còn lại bằng cách lấy tổng số tiền ban đầu chia lấy dư cho mệnh giá hiện tại.
   • Lặp lại cho đến khi xử lý hết tất cả các mệnh giá hoặc tổng số tiền còn lại bằng 0.
4. Kết quả: Biến đếm tổng số tờ tiền chính là số lượng tờ tiền ít nhất cần đổi.
5. Xử lý Input/Output: Đọc số lượng bộ test T, sau đó lặp T lần. Trong mỗi lần lặp, đọc N, thực hiện các bước trên và in kết quả ra một dòng.

Làm thêm nhiều bài tập miễn phí tại đây