Thuật toán tham lam¶

Thuật toán tham lam (greedy algorithm) là một phương pháp phổ biến để giải quyết các bài toán tối ưu hóa (optimization problem). Ý tưởng cơ bản của nó là lựa chọn phương án có vẻ tốt nhất ở mỗi giai đoạn đưa ra quyết định, tức là đưa ra các quyết định tối ưu cục bộ (locally optimal decision) một cách tham lam với hy vọng có được lời giải tối ưu toàn cục (globally optimal solution). Thuật toán tham lam đơn giản, hiệu quả và được sử dụng rộng rãi trong nhiều bài toán thực tế.

Thuật toán tham lam và quy hoạch động (dynamic programming) đều thường được sử dụng để giải quyết các bài toán tối ưu hóa. Chúng có một số điểm tương đồng, chẳng hạn như đều dựa trên tính chất cấu trúc con tối ưu (optimal substructure property), nhưng cách thức hoạt động của chúng lại khác nhau.

Quy hoạch động xem xét tất cả các quyết định trước đó khi đưa ra quyết định hiện tại và sử dụng lời giải của các bài toán con (subproblem) trong quá khứ để xây dựng lời giải cho bài toán con hiện tại.
Thuật toán tham lam không xem xét các quyết định trong quá khứ, thay vào đó nó đưa ra các lựa chọn tham lam (greedy choice) hướng về phía trước, liên tục giảm quy mô bài toán cho đến khi bài toán được giải quyết.

Trước hết chúng ta sẽ tìm hiểu cách thức hoạt động của thuật toán tham lam thông qua bài toán ví dụ "đổi tiền xu". Bài toán này đã được giới thiệu trong chương "Bài toán cái túi hoàn toàn", vì vậy chắc hẳn bạn đã quen thuộc với nó.

Question

Cho \(n\) loại tiền xu, trong đó mệnh giá của loại thứ \(i\) là \(coins[i - 1]\), một số tiền mục tiêu \(amt\), và số lượng xu không giới hạn cho mỗi loại, hỏi số lượng đồng xu tối thiểu cần thiết để đổi được số tiền mục tiêu là bao nhiêu? Nếu không thể đổi được số tiền mục tiêu, trả về \(-1\).

Chiến lược tham lam cho bài toán này được thể hiện trong hình dưới đây. Cho một số tiền mục tiêu, chúng ta chọn một cách tham lam đồng xu có mệnh giá không vượt quá số tiền đó và gần với nó nhất, lặp lại bước này cho đến khi đổi đủ số tiền mục tiêu.

Mã nguồn triển khai như sau:

[file]{coin_change_greedy}-[class]{}-[func]{coin_change_greedy}

Bạn có thể sẽ phải thốt lên rằng, "Thật tinh gọn!" Thuật toán tham lam giải quyết bài toán đổi tiền xu chỉ trong khoảng mười dòng mã.

Ưu điểm và hạn chế của thuật toán tham lam¶

Thuật toán tham lam không chỉ dễ áp dụng, dễ triển khai mà thường còn rất hiệu quả. Trong đoạn mã trên, nếu mệnh giá tiền xu nhỏ nhất là \(\min(coins)\), vòng lặp lựa chọn tham lam chạy tối đa \(amt / \min(coins)\) lần, mang lại độ phức tạp thời gian là \(O(amt / \min(coins))\). Điều này thấp hơn một bậc độ lớn so với độ phức tạp thời gian của lời giải quy hoạch động là \(O(n \times amt)\).

Tuy nhiên, đối với một số tập mệnh giá tiền xu, thuật toán tham lam không thể tìm ra lời giải tối ưu. Hình dưới đây chỉ ra hai ví dụ.

Ví dụ đúng \(coins = [1, 5, 10, 20, 50, 100]\): Với tập tiền xu này, thuật toán tham lam có thể tìm được lời giải tối ưu cho bất kỳ giá trị \(amt\) nào.
Phản ví dụ \(coins = [1, 20, 50]\): Giả sử \(amt = 60\). Thuật toán tham lam chỉ có thể tìm thấy tổ hợp \(50 + 1 \times 10\), sử dụng tổng cộng \(11\) đồng xu, trong khi quy hoạch động có thể tìm ra lời giải tối ưu là \(20 + 20 + 20\) chỉ với \(3\) đồng xu.
Phản ví dụ \(coins = [1, 49, 50]\): Giả sử \(amt = 98\). Thuật toán tham lam chỉ có thể tìm thấy tổ hợp \(50 + 1 \times 48\), sử dụng tổng cộng \(49\) đồng xu, trong khi quy hoạch động có thể tìm ra lời giải tối ưu là \(49 + 49\) chỉ với \(2\) đồng xu.

Nói cách khác, đối với bài toán đổi tiền xu, thuật toán tham lam không thể đảm bảo thu được lời giải tối ưu toàn cục và thậm chí có thể tạo ra kết quả rất tệ. Bài toán này được giải quyết tốt hơn bằng quy hoạch động.

Nói chung, thuật toán tham lam có thể áp dụng trong hai trường hợp sau.

Lời giải tối ưu được đảm bảo: Trong trường hợp này, thuật toán tham lam thường là lựa chọn tốt nhất vì chúng có xu hướng hiệu quả hơn so với quay lui và quy hoạch động.
Có thể tìm thấy lời giải xấp xỉ tối ưu: Thuật toán tham lam cũng rất hữu ích trong trường hợp này. Đối với nhiều bài toán phức tạp, việc tìm lời giải tối ưu toàn cục là cực kỳ khó khăn, do đó việc tìm kiếm hiệu quả một lời giải cận tối ưu (suboptimal solution) đã là một kết quả rất tốt.

Đặc điểm của thuật toán tham lam¶

Vậy câu hỏi đặt ra là: loại bài toán nào phù hợp để giải bằng thuật toán tham lam? Hay nói cách khác, dưới điều kiện nào thì thuật toán tham lam đảm bảo tìm được lời giải tối ưu?

So với quy hoạch động, các điều kiện để sử dụng thuật toán tham lam khắt khe hơn, chủ yếu tập trung vào hai tính chất của bài toán.

Tính chất lựa chọn tham lam (greedy choice property): Chỉ khi các lựa chọn tối ưu cục bộ luôn có thể dẫn đến lời giải tối ưu toàn cục thì thuật toán tham lam mới đảm bảo đạt được lời giải tối ưu.
Cấu trúc con tối ưu (optimal substructure): Lời giải tối ưu cho bài toán gốc chứa các lời giải tối ưu cho các bài toán con.

Cấu trúc con tối ưu đã được giới thiệu trong chương "Quy hoạch động", vì vậy chúng ta sẽ không trình bày chi tiết ở đây. Đáng chú ý là cấu trúc con tối ưu của một số bài toán không quá rõ ràng, nhưng chúng vẫn có thể được giải quyết bằng thuật toán tham lam.

Chúng ta chủ yếu khám phá các phương pháp để xác định tính chất lựa chọn tham lam. Mặc dù mô tả của nó có vẻ tương đối đơn giản, nhưng trên thực tế, đối với nhiều bài toán, việc chứng minh tính chất lựa chọn tham lam là không hề dễ dàng.

Ví dụ, trong bài toán đổi tiền xu, mặc dù chúng ta có thể dễ dàng đưa ra các phản ví dụ để bác bỏ tính chất lựa chọn tham lam, nhưng việc chứng minh nó đúng lại khó hơn nhiều. Nếu được hỏi, dưới điều kiện nào thì một tập tiền xu có thể được giải bằng thuật toán tham lam? Chúng ta thường chỉ có thể dựa vào trực giác hoặc các ví dụ để đưa ra câu trả lời mơ hồ, và rất khó để cung cấp một chứng minh toán học chặt chẽ.

Quote

Có một bài báo trình bày một thuật toán \(O(n^3)\) để xác định xem một tập tiền xu có thể được giải tối ưu bằng thuật toán tham lam đối với bất kỳ số tiền nào hay không.

Pearson, D. A polynomial-time algorithm for the change-making problem[J]. Operations Research Letters, 2005, 33(3): 231-234.

Các bước giải quyết bài toán bằng thuật toán tham lam¶

Quy trình chung để giải quyết các bài toán tham lam có thể chia thành ba bước sau.

Phân tích bài toán: Sắp xếp và hiểu các đặc điểm của bài toán, bao gồm định nghĩa trạng thái, mục tiêu tối ưu hóa và các ràng buộc. Bước này cũng xuất hiện trong quay lui và quy hoạch động.
Xác định chiến lược tham lam: Quyết định cách đưa ra lựa chọn tham lam ở mỗi bước. Chiến lược này sẽ giảm quy mô bài toán theo từng bước và cuối cùng giải quyết toàn bộ bài toán.
Chứng minh tính đúng đắn: Thường cần phải chứng minh rằng bài toán có cả tính chất lựa chọn tham lam và cấu trúc con tối ưu. Bước này có thể yêu cầu các công cụ toán học như quy nạp hoặc chứng minh bằng phản chứng.

Xác định chiến lược tham lam là bước cốt lõi trong việc giải quyết các bài toán như vậy, nhưng nó có thể không dễ dàng trong thực tế, chủ yếu vì những lý do sau.

Chiến lược tham lam rất khác nhau giữa các bài toán. Đối với nhiều bài toán, chiến lược tham lam khá trực quan và có thể suy ra thông qua lập luận sơ bộ và thử nghiệm. Tuy nhiên, đối với một số bài toán phức tạp, chiến lược tham lam có thể bị che giấu sâu sắc, thử thách mạnh mẽ kinh nghiệm giải quyết vấn đề và năng lực thuật toán của lập trình viên.
Một số chiến lược tham lam có tính lừa dối cao. Chúng ta có thể tự tin thiết kế một chiến lược tham lam, viết mã nguồn giải quyết và gửi đi, để rồi nhận thấy một số ca kiểm thử (test case) thất bại. Điều này là do chiến lược tham lam được thiết kế chỉ "đúng một phần", như ví dụ về bài toán đổi tiền xu đã thảo luận ở trên.

Để đảm bảo tính đúng đắn, chúng ta nên đưa ra một chứng minh toán học chặt chẽ cho chiến lược tham lam, thường sử dụng chứng minh phản chứng hoặc quy nạp toán học.

Tuy nhiên, các chứng minh tính đúng đắn cũng có thể khó khăn. Nếu không có hướng đi rõ ràng, chúng ta thường sử dụng phương pháp gỡ lỗi dựa trên các ca kiểm thử, sửa đổi và xác thực chiến lược tham lam từng bước.

Các bài toán điển hình giải bằng thuật toán tham lam¶

Thuật toán tham lam thường được áp dụng cho các bài toán tối ưu hóa thỏa mãn tính chất lựa chọn tham lam và cấu trúc con tối ưu. Dưới đây là một số bài toán thuật toán tham lam điển hình.

Bài toán đổi tiền xu: Với một số tổ hợp tiền xu nhất định, thuật toán tham lam luôn có thể đạt được lời giải tối ưu.
Bài toán lập lịch khoảng (interval scheduling problem): Giả sử bạn có một số nhiệm vụ, mỗi nhiệm vụ diễn ra trong một khoảng thời gian và mục tiêu của bạn là hoàn thành nhiều nhiệm vụ nhất có thể. Nếu bạn luôn chọn nhiệm vụ kết thúc sớm nhất, thì thuật toán tham lam có thể đạt được lời giải tối ưu.
Bài toán cái túi phân số (fractional knapsack problem): Cho một tập hợp các vật phẩm và một sức chứa của cái túi, mục tiêu của bạn là chọn một tập hợp các vật phẩm sao cho tổng trọng lượng không vượt quá sức chứa và tổng giá trị là lớn nhất. Nếu bạn luôn chọn vật phẩm có tỷ lệ giá trị trên trọng lượng (giá trị / trọng lượng) cao nhất, thì thuật toán tham lam có thể đạt được lời giải tối ưu trong một số trường hợp.
Bài toán mua bán cổ phiếu: Cho một tập hợp lịch sử giá cổ phiếu, bạn có thể thực hiện nhiều giao dịch, nhưng nếu bạn đã nắm giữ cổ phiếu, bạn không thể mua lại trước khi bán và mục tiêu là đạt được lợi nhuận tối đa.
Mã hóa Huffman (Huffman coding): Mã hóa Huffman là một thuật toán tham lam được sử dụng để nén dữ liệu không mất dữ liệu (lossless). Bằng cách xây dựng cây Huffman và luôn hợp nhất hai nút có tần suất thấp nhất, cây Huffman thu được sẽ có độ dài đường đi có trọng số tối thiểu (độ dài mã hóa).
Thuật toán Dijkstra (Dijkstra's algorithm): Đây là một thuật toán tham lam để giải quyết bài toán đường đi ngắn nhất từ một đỉnh nguồn cho trước đến tất cả các đỉnh khác.