Thuật toán tham lam (Greedy Algorithm)
1. Tổng quan
A. Định nghĩa
Thuật toán tham lam (Greedy Algorithm) là chiến lược giải quyết vấn đề nhằm đạt tới lời giải tối ưu toàn cục (global optimum) bằng cách, tại mỗi bước, đưa ra lựa chọn tối ưu cục bộ (local optimum) trông có vẻ tốt nhất ở thời điểm đó và không bao giờ thu hồi quyết định đã đưa ra; nó chỉ bảo đảm câu trả lời đúng cho những bài toán mà tính chất lựa chọn tham lam (greedy choice property) (một lựa chọn có thể dẫn tới tối ưu toàn cục) và cấu trúc con tối ưu (optimal substructure) đều thỏa mãn.
Thuật toán tham lam hình thức hóa trực giác cực kỳ đơn giản là "lấy thứ có lợi nhất ngay bây giờ và không ngoái lại." Hành vi thường nhật là lấy đồng xu mệnh giá lớn nhất trước khi thối tiền là ví dụ điển hình: không cần xét mọi tổ hợp, con người biết qua kinh nghiệm rằng dùng đồng xu lớn trước thì số lượng xu giảm. Như vậy, vì chiến lược tham lam "quyết định dựa trên cái tốt nhất trước mắt mà không nhìn toàn cục" nên nó cài đặt gọn gàng và thường kết thúc trong thời gian đa thức (thường là O(n log n)), nhanh hơn áp đảo so với vét cạn hay quy hoạch động. Chính tốc độ này làm thuật toán tham lam hấp dẫn, nhưng đồng thời luôn kèm theo bài toán tính hợp lệ "liệu chuỗi các tối ưu cục bộ có thực sự là tối ưu toàn cục hay không."
Giá trị và rủi ro của thuật toán tham lam là hai mặt của một đồng xu. Với những bài toán thỏa mãn một số điều kiện nhất định (cây khung nhỏ nhất, mã hóa Huffman, ba lô phân số, lập lịch công việc, v.v.) thì tham lam cho ra lời giải tối ưu có thể chứng minh được, nhưng khi điều kiện bị phá vỡ thì nó cho ra câu trả lời có vẻ hợp lý nhưng sai rõ ràng. Do đó, năng lực cốt lõi của Kỹ sư chuyên nghiệp khi xử lý thuật toán tham lam nằm ở phán đoán thiết kế: "trước hết xác định bài toán có giải được bằng tham lam hay không, nếu có thì lập luận tính hợp lệ của lựa chọn tham lam, nếu không thì chuyển sang quy hoạch động hoặc vét cạn."
B. Bối cảnh ra đời và sự cần thiết
Nhiều bài toán tối ưu có số lời giải khả thi bùng nổ theo cấp số mũ với kích thước đầu vào. Ví dụ, xử lý n công việc theo thứ tự nào, đặt món nào trong n món vào ba lô, mỗi bài có số trường hợp cỡ n!·2ⁿ, nên vét cạn (brute force) liệt kê mọi trường hợp trở nên bất khả thi trên thực tế ngay khi n lớn lên chút ít. Quy hoạch động (DP) kìm hãm sự bùng nổ này về thời gian đa thức bằng cách lưu các bài toán con trùng lặp, nhưng khi không gian trạng thái lớn thì bộ nhớ và thời gian vẫn là gánh nặng. Tại điểm này nảy sinh nhu cầu về "lối tắt đến câu trả lời đúng mà không xét mọi trường hợp," và khi bài toán có cấu trúc đặc thù thì thuật toán tham lam cung cấp lối tắt đó.
Điều quan trọng ở đây là, trong khi vét cạn và DP là chiến lược thụ động "bằng cách nào đó quét qua mọi khả năng," thì tham lam là chiến lược chủ động "hiểu cấu trúc bài toán và ngay từ đầu không hề ngó tới phần lớn các khả năng." Sự khác biệt này vượt quá việc tăng tốc đơn thuần: nó còn có nghĩa tham lam chỉ thành lập khi ta có cái nhìn thấu suốt vào trật tự nội tại của bài toán (độ ưu tiên có thể sắp xếp, phần tử có thể hoán đổi, cấu trúc matroid). Thiết kế một thuật toán tham lam vì thế chính là công việc phát hiện "tính chất nào của bài toán này làm cho tìm kiếm vét cạn trở nên không cần thiết," và đây là lĩnh vực thử thách trực tiếp nhất năng lực phân tích bài toán của người thiết kế thuật toán.
Hơn nữa, nhiều hệ thống thực tế đòi hỏi lời giải "không hoàn hảo nhưng nhanh và đủ tốt" dưới tính thời gian thực và ràng buộc tài nguyên. Bộ định tuyến mạng phải cập nhật tuyến ở cấp mili-giây, bộ lập lịch hệ điều hành phải chọn ngay tiến trình chạy kế tiếp tại mỗi thời khắc, và bộ nén dữ liệu phải sinh mã khi đi qua luồng. Trong các môi trường như vậy, chiến lược tham lam ra quyết định cục bộ tức thời trên thông tin đến phù hợp hơn về mặt cấu trúc so với DP vốn tính lại toàn bộ. Xa hơn, với những bài toán NP-khó (NP-hard) không giải tối ưu được trong thời gian đa thức (phủ tập hợp, người bán hàng rong, v.v.), tham lam dù không tối ưu vẫn cung cấp lời giải thực dụng với tỷ lệ xấp xỉ được bảo đảm (approximation ratio), nối liền lý thuyết và thực hành. Như vậy, thuật toán tham lam đứng trên hai nhu cầu kép: "bộ tối ưu hóa nhanh bảo đảm tính đúng đắn có điều kiện" và "bộ xấp xỉ đáng tin cậy cho các bài toán khó."
2. Nguyên lý hoạt động và điều kiện tính hợp lệ của thuật toán tham lam
Hai điều kiện cốt lõi để thuật toán tham lam hoạt động đúng là tính chất lựa chọn tham lam và cấu trúc con tối ưu. Chỉ khi cả hai đều thỏa mãn thì bước nhảy "một chuỗi các tối ưu cục bộ là tối ưu toàn cục" mới được biện minh.
flowchart TB
PROB["Bài toán tối ưu"] --> Q1{"Tính chất lựa chọn tham lam thỏa?"}
Q1 -->|"Không"| DPFULL["Chuyển sang DP / vét cạn"]
Q1 -->|"Có"| Q2{"Cấu trúc con tối ưu thỏa?"}
Q2 -->|"Không"| DPFULL
Q2 -->|"Có"| GREEDY["Áp dụng thuật toán tham lam (bảo đảm tối ưu)"]
GREEDY --> PROOF["Chứng minh tính hợp lệ: lập luận hoán đổi / matroid"]
Tính chất lựa chọn tham lam là tính chất rằng "ít nhất một tối ưu toàn cục có thể được xây dựng sao cho bao hàm lựa chọn tham lam ở mỗi bước." Tức là cái tối ưu cục bộ lấy ngay bây giờ phải có khả năng trở thành một phần của tối ưu cuối cùng. Kỹ thuật chuẩn để chứng minh điều này một cách chặt chẽ là lập luận hoán đổi (exchange argument). Giả định một tối ưu bất kỳ, nếu phần tử mà tham lam chọn vắng mặt trong lời giải đó, ta chứng tỏ rằng hoán đổi nó với phần tử khác không làm lời giải xấu đi, qua đó chứng minh rằng một tối ưu bao hàm lựa chọn tham lam nhất định tồn tại. Chẳng hạn, trong bài toán chọn hoạt động, lý do tham lam "chọn trước hoạt động kết thúc sớm nhất" là đúng vì thay hoạt động đầu tiên của bất kỳ tối ưu nào bằng hoạt động tham lam kết thúc sớm hơn không làm giảm các hoạt động chọn được về sau. Lập luận hoán đổi là công cụ phổ quát nhất để xử lý tính hợp lệ của thuật toán tham lam nên nhất thiết phải thông thạo.
Nhìn lập luận hoán đổi cụ thể hơn một chút, bộ khung của nó là chứng tỏ rằng "nếu lời giải tham lam và lời giải tối ưu khác nhau, thì biến đổi lời giải tối ưu dần dần về phía lời giải tham lam không làm chất lượng suy giảm." Nếu lựa chọn đầu tiên khác nhau, thay lựa chọn đầu của tối ưu bằng lựa chọn đầu của tham lam, xác nhận nó vẫn tối ưu, rồi lặp lại quá trình này cho lựa chọn thứ hai, thứ ba. Khi đã thay hết mọi lựa chọn thì tối ưu trở nên hoàn toàn trùng với lời giải tham lam, nên cuối cùng đi đến kết luận "lời giải tham lam cũng tối ưu." Chứng minh rằng phép thay thế quy nạp này không làm hại chất lượng ở bất kỳ bước nào là cốt lõi của lập luận hoán đổi, và chỉ khi chứng minh đó khả thi thì mới có thể yên tâm chọn dùng tham lam.
Cấu trúc con tối ưu là tính chất rằng "lời giải tối ưu của bài toán được cấu thành từ lời giải tối ưu của các bài toán con," nghĩa là sau khi tham lam chốt một phần tử thì bài toán con còn lại cũng phải giải được tối ưu bằng chính chiến lược tham lam ấy. Quy hoạch động cũng chia sẻ tính chất này; khác biệt quyết định giữa hai kỹ thuật nằm ở cách giải các bài toán con. Quy hoạch động tìm và so sánh/kết hợp lời giải của nhiều bài toán con, còn tham lam "thu hẹp bài toán con về chỉ một bằng một lựa chọn tham lam" và chỉ đi theo một nhánh đó xuống. Chính cái "thu lựa chọn về một và không ngoái lại" này làm tham lam nhanh hơn DP, nhưng nó cũng gánh rủi ro rằng nếu lựa chọn sai thì toàn bộ sẽ chệch hướng.
flowchart LR
S0["Toàn bộ bài toán"] --> C1["Lựa chọn tham lam 1 (tối ưu cục bộ)"]
C1 --> S1["Bài toán con đã thu hẹp"]
S1 --> C2["Lựa chọn tham lam 2"]
C2 --> S2["Bài toán con nhỏ hơn"]
S2 --> DOTS["..."]
DOTS --> SOL["Tối ưu toàn cục"]
C1 -. "không ngoái lại (irrevocable)" .-> C1
Một phản ví dụ tiêu biểu nơi tính hợp lệ không được bảo đảm là bài toán thối tiền. Nếu mệnh giá xu tạo thành hệ chuẩn tắc (canonical) như {1, 5, 10, 25}, thì tham lam "lớn trước" bảo đảm số xu tối thiểu, nhưng trong hệ {1, 4, 6}, khi thối 8, tham lam lấy 6+1+1=3 xu trong khi tối ưu là 4+4=2. Việc tính hợp lệ của tham lam sụp đổ khi điều kiện đầu vào (hệ xu) của cùng một bài toán thay đổi cho thấy rõ rằng phải kiểm chứng tính hợp lệ trước khi dùng thuật toán tham lam. Áp dụng tham lam vì nó "trông có vẻ đúng theo trực giác" mà không kiểm chứng là một lỗi thiết kế điển hình.
Bài học từ phản ví dụ này không đơn thuần là "tham lam đôi khi sai," mà nó bộc lộ một giới hạn cấu trúc tổng quát hơn gọi là cái bẫy tối ưu cục bộ (local optimum trap). Vì tham lam chỉ đuổi theo lợi ích trước mắt mà không thấy làn sóng mà lựa chọn hiện tại sẽ gây ra cho tương lai, nên về nguyên lý nó không thể tìm kiếm con đường "chịu thiệt nhỏ bây giờ để được lợi lớn về sau." Trong hệ {1, 4, 6}, khoảnh khắc lấy 6 thì 2 còn lại chỉ có thể lấp bằng 1+1 — đó chính là cái bẫy này. Trái với quy hoạch động vốn lưu và so sánh mọi lựa chọn để nắm bắt những "lợi ích bị trì hoãn" như vậy, tham lam vứt bỏ nhánh đó hoàn toàn. Do đó, kiểm chứng tính hợp lệ của tham lam về bản chất là công việc chứng tỏ rằng "bài toán này không tồn tại cái bẫy tối ưu cục bộ," và lập luận hoán đổi chính là công cụ chứng minh sự vắng mặt đó.
3. Quy trình thiết kế và các thuật toán tiêu biểu
Với bài toán được trang bị hai điều kiện trên, việc thiết kế thuật toán tham lam nhìn chung tuân theo một quy trình chung. Trước hết định nghĩa đối tượng tối ưu (hàm mục tiêu), rồi định ra tiêu chí lựa chọn tham lam (khóa sắp xếp) cho mỗi bước, tích lũy lời giải trong khi kiểm tra lựa chọn không vi phạm ràng buộc, và cuối cùng chứng minh tính hợp lệ qua lập luận hoán đổi hoặc tương tự. Vì nhiều thuật toán tham lam có dạng "sắp xếp theo một tiêu chí nhất định rồi duyệt từ đầu," nên chi phí chủ đạo thường là O(n log n) của phép sắp xếp (xem [[sorting-algorithms]]).
Bước sáng tạo và khó nhất trong quy trình này là định ra tiêu chí lựa chọn tham lam. Các bước còn lại (kiểm tra ràng buộc, tích lũy lời giải) là máy móc, nhưng "lấy tiêu chí nào để chọn cái tốt nhất" khác nhau theo từng bài toán và nếu chọn sai thì dẫn thẳng tới câu trả lời sai. Vì thế người thiết kế lão luyện dựng lên vài tiêu chí ứng viên hợp lý rồi tích cực săn tìm các phản ví dụ nhỏ đối với mỗi tiêu chí để sàng loại, và chỉ thiết lập tính hợp lệ qua lập luận hoán đổi đối với những tiêu chí không sinh phản ví dụ. Lưu đồ dưới đây minh họa quy trình chung này.
flowchart TB
START["Định nghĩa bài toán · hàm mục tiêu"] --> SORT["Sắp xếp ứng viên theo tiêu chí tham lam"]
SORT --> LOOP{"Còn ứng viên?"}
LOOP -->|"Có"| PICK["Chọn ứng viên tốt nhất theo tiêu chí"]
PICK --> FEASIBLE{"Không vi phạm ràng buộc?"}
FEASIBLE -->|"Có"| ADD["Thêm vào tập lời giải"]
FEASIBLE -->|"Không"| SKIP["Bỏ qua"]
ADD --> LOOP
SKIP --> LOOP
LOOP -->|"Không"| PROOF["Trả lời giải sau khi kiểm tính hợp lệ"]
A. Chọn hoạt động và lập lịch công việc
Bài toán chọn hoạt động (activity selection) là bài toán chọn số lượng hoạt động không chồng lấn lẫn nhau nhiều nhất từ một tập hoạt động có thời điểm bắt đầu và kết thúc cho trước. Tiêu chí tham lam là "chọn trước hoạt động kết thúc sớm nhất," rồi lặp lại chọn hoạt động kế tiếp không chồng lấn hoạt động đã chọn. Tiêu chí này đúng vì hoạt động kết thúc càng sớm thì thời gian còn lại về sau càng nhiều và dư địa để nhồi thêm hoạt động càng lớn. Ví dụ, nếu một phòng họp có mười một yêu cầu (1–4), (3–5), (0–6), (5–7), (3–9), (5–9), (6–10), (8–11), (8–12), (2–14), (12–16), thì tham lam theo thời điểm kết thúc phân bổ bốn hoạt động (1–4)→(5–7)→(8–11)→(12–16), đạt tối ưu. Thú vị là các tiêu chí hợp lý khác như "hoạt động ngắn nhất trước" hay "hoạt động bắt đầu sớm nhất trước" có phản ví dụ và không bảo đảm tối ưu, một bài học quan trọng cho thấy chọn tiêu chí tham lam nào sẽ chi phối tính hợp lệ. Nguyên lý này áp dụng rộng rãi cho các bài toán thực tế nhồi tối đa các công việc không chồng lấn vào một tài nguyên duy nhất: lập lịch CPU, đặt phòng học và thiết bị, bố trí khe quảng cáo. Cũng cần biết rằng trong một biến thể nơi mỗi hoạt động mang một giá trị (weight) và phải "tối đa hóa tổng giá trị, chứ không phải số lượng," thì tham lam theo thời điểm kết thúc đơn giản không còn bảo đảm tối ưu và chuyển thành bài toán quy hoạch động gọi là lập lịch khoảng có trọng số (weighted interval scheduling). Điều này bộc lộ rằng tiền đề ngầm "mọi hoạt động có giá trị bằng nhau" đã chống đỡ tính hợp lệ của tham lam, tái khẳng định bài học lặp đi lặp lại rằng khi tiền đề thay đổi thì kỹ thuật cũng phải thay đổi.
B. Bài toán ba lô phân số
Ba lô phân số (fractional knapsack) là bài toán đặt các món vào ba lô dung lượng W để tối đa hóa tổng giá trị, trong đó các món có thể chia nhỏ. Tiêu chí tham lam là "nhồi từ món có giá trị trên một đơn vị khối lượng (giá trị/khối lượng) cao nhất, và với món cuối thì chia nhỏ để vừa dung lượng còn lại." Ví dụ, với ba lô dung lượng 50kg và ba món (giá trị 60, khối lượng 10), (giá trị 100, khối lượng 20), (giá trị 120, khối lượng 30), giá trị đơn vị lần lượt là 6, 5, 4, nên nhồi nguyên món 1 (10kg·60)→món 2 (20kg·100) và món 3 cho 20kg còn lại (2/3), thu giá trị 60+100+80=240. Vì có thể chia nhỏ nên thứ tự theo giá trị đơn vị chính là thứ tự tối ưu, nên tham lam cho ra đúng tối ưu.
Tuy nhiên, khi điều kiện đổi thành ba lô 0/1 nơi không thể chia nhỏ món, thì cùng tham lam ấy không bảo đảm tối ưu. Trong một cấu hình như dung lượng 10kg với (giá trị 60, khối lượng 10), (giá trị 70, khối lượng 10)..., "chỉ lấy một theo thứ tự giá trị đơn vị" có thể bỏ lỡ một tổ hợp có giá trị lớn hơn. Ba lô 0/1 phải cân nhắc các tổ hợp "lấy/không lấy" nên tính chất lựa chọn tham lam bị phá vỡ, và phải giải bằng quy hoạch động (hoặc nhánh cận). Sự tương phản gay gắt này giữa ba lô phân số và 0/1 là một ví dụ tiêu biểu thường dùng trong bài làm của Kỹ sư chuyên nghiệp, cho thấy một ràng buộc duy nhất — "có thể chia nhỏ không?" — là yếu tố quyết định phân chia tính hợp lệ của tham lam (xem [[dynamic-programming]]).
C. Mã hóa Huffman
Mã hóa Huffman (Huffman coding) là thuật toán tham lam sinh mã tiền tố độ dài biến thiên (prefix code) theo tần suất của mỗi ký tự để nén dữ liệu không mất mát. Tiêu chí tham lam là "lặp lại hợp nhất hai nút có tần suất thấp nhất": tại mỗi bước lấy ra hai nút tần suất nhỏ nhất, gộp thành một nút hợp nhất và xây cây nhị phân từ dưới lên. Nó gán mã ngắn cho ký tự thường gặp và mã dài cho ký tự hiếm sao cho độ dài mã trung bình tiệm cận entropy thông tin. Ví dụ, nếu tần suất các ký tự a·b·c·d·e·f là 45·13·12·16·9·5, Huffman trước tiên hợp nhất f(5)·e(9) hiếm nhất thành 14, rồi hợp nhất c(12)·b(13) nhỏ kế tiếp thành 25, xây cây từ dưới lên. Trong cây hoàn chỉnh, a nhận mã 1 bit và phần còn lại mã 3–4 bit, thu nhỏ còn khoảng 224 bit, nhỏ hơn mã cố định 3 bit (tổng khoảng 300 bit) — hiệu ứng của việc dồn mã ngắn cho các ký tự thường gặp. Tính hợp lệ của tham lam "tần suất nhỏ nhất trước" này cũng được chứng minh bằng lập luận hoán đổi (trong cây tối ưu, hai lá sâu nhất có thể hoán đổi với hai ký tự tần suất thấp nhất mà không thiệt hại), và dùng min-heap (hàng đợi ưu tiên) nó chạy trong O(n log n). Mã hóa Huffman thực sự được nhúng vào giai đoạn mã hóa entropy của một dải rộng các chuẩn nén như JPEG, MP3, ZIP (DEFLATE), PNG, được xem là ví dụ tiêu biểu của thuật toán tham lam vận hành ở trái tim của các chuẩn công nghiệp.
D. Tham lam trên đồ thị: Cây khung nhỏ nhất và Dijkstra
Tham lam cũng là chiến lược thiết kế cốt lõi cho các bài toán đồ thị. Thuật toán Kruskal cho cây khung nhỏ nhất (MST) là tham lam "nhận cạnh từ trọng số nhỏ nhất, miễn là không tạo chu trình," và thuật toán Prim là tham lam "hấp thụ, từng cái một, đỉnh nối rẻ nhất vào cây hiện tại." Cả hai đều được bảo đảm tối ưu bởi tính chất cắt (cut property) của đồ thị — "cạnh trọng số nhỏ nhất băng qua một lát cắt bất kỳ nhất định được bao hàm trong một MST nào đó." Kruskal sắp xếp cạnh và kiểm tra chu trình bằng Union-Find, chạy trong O(E log E), còn Prim dùng min-heap, chạy trong O(E log V); chúng được dùng để tối thiểu hóa cáp mạng truyền thông, thiết kế lưới điện, phân cụm (single-linkage clustering), v.v.
Việc Kruskal và Prim dựng nên cùng một MST theo thứ tự khác nhau cho thấy sự linh hoạt của chiến lược tham lam. Nếu Kruskal là góc nhìn toàn cục "quét mọi cạnh theo thứ tự trọng số và dần hợp nhất các mảnh của một rừng (forest)," thì Prim là góc nhìn tăng trưởng cục bộ "khởi từ một đỉnh và nuôi cây lớn lên từng lớp." Dù thế nào, mỗi lựa chọn tham lam ở mỗi bước (cạnh nhỏ nhất, đỉnh nối nhỏ nhất) được tính chất cắt bảo đảm an toàn, nên tính tối ưu của kết quả là như nhau; lựa chọn phân chia theo mật độ đồ thị, với Prim (dựa trên ma trận kề O(V²)) được ưa chuộng trên đồ thị dày nhiều cạnh và Kruskal trên đồ thị thưa. Trong khi đó, thuật toán Dijkstra của [[shortest-path]] bàn trước đó cũng là tham lam "chốt đỉnh chưa chốt có khoảng cách tạm thời nhỏ nhất," nơi điều kiện trọng số không âm chống đỡ tính hợp lệ của lựa chọn tham lam. Thú vị là Prim và Dijkstra có bộ khung gần như giống nhau "hấp thụ đỉnh gần nhất với tập hiện tại," chỉ khác ở chỗ Prim lấy 'chính trọng số cạnh' làm tiêu chí còn Dijkstra lấy 'khoảng cách tích lũy từ nguồn.' Việc một phần đáng kể các thuật toán đồ thị đứng trên mô thức tham lam như vậy chứng tỏ rõ tính phổ quát ở cấp độ thiết kế của chiến lược tham lam.
4. So sánh: Tham lam · Quy hoạch động · Vét cạn
Ba mô thức tiêu biểu để giải bài toán tối ưu — tham lam, quy hoạch động, vét cạn — phân nhánh ở "cân nhắc bao nhiêu trường hợp" và "bảo đảm tính đúng đắn đến đâu." Bảng dưới đây sắp xếp các khác biệt, nhưng lý do chúng nảy sinh bắt rễ ở cách mỗi kỹ thuật xử lý các bài toán con.
| Phân loại | Thuật toán tham lam | Quy hoạch động | Vét cạn |
|---|---|---|---|
| Chiến lược cốt lõi | Chọn tối ưu cục bộ, không thu hồi | Lưu/kết hợp lời giải bài toán con | Liệt kê mọi trường hợp |
| Xử lý bài toán con | Thu về một bằng lựa chọn | So sánh mọi lời giải | Tìm kiếm vét cạn các nhánh |
| Bảo đảm tối ưu | Chỉ khi điều kiện thỏa | Luôn luôn (với cấu trúc đó) | Luôn luôn |
| Độ phức tạp thời gian | Thường O(n log n) | Đa thức (số trạng thái × chuyển tiếp) | Mũ (n!·2ⁿ) |
| Bộ nhớ | Nhỏ | Lớn bằng bảng trạng thái | Nhỏ (ngăn xếp đệ quy) |
| Tình huống phù hợp | Tính chất lựa chọn tham lam thỏa | Bài toán con trùng lặp · cấu trúc con tối ưu | Quy mô nhỏ · tính đúng đắn tuyệt đối |
Tham lam và quy hoạch động gần nhau ở chỗ cả hai đều đòi hỏi cấu trúc con tối ưu, nhưng sự có mặt hay vắng mặt của tính chất lựa chọn tham lam phân chia chúng. Khi tính chất này thỏa, "lựa chọn ở mỗi bước có thể chốt ngay mà không cần so sánh," nên tham lam nhanh hơn DP theo cấp số mũ và hầu như không dùng bộ nhớ. Ngược lại, khi tính chất này vắng mặt (như ba lô 0/1) thì tham lam sai và DP phải lưu và so sánh mọi lựa chọn. Do đó hàm ý thực tiễn là "chọn tham lam nếu tính chất lựa chọn tham lam được chứng minh, DP nếu chỉ có bài toán con trùng lặp, và vét cạn nếu cả hai đều bất định và đầu vào nhỏ." Đặc biệt, bỏ qua điểm ngay cả với cùng một bài toán, kỹ thuật phù hợp thay đổi khi ràng buộc thay đổi (ba lô phân số ↔ ba lô 0/1) tạo ra một khiếm khuyết chí tử trông như câu trả lời đúng bề ngoài nhưng chệch hướng trên một số đầu vào.
Cảm nhận sự khác biệt độ phức tạp bằng con số làm rõ khoảng cách giữa ba mô thức. Giải một ba lô 0/1 với kích thước đầu vào n=40 bằng vét cạn đòi hỏi cân nhắc 2⁴⁰≈1 nghìn tỷ nhánh, mất hàng chục phút trở lên ngay cả trên CPU hiện đại, nhưng với dung lượng W quanh 1,000 thì quy hoạch động chỉ lấp 40×1,000=40,000 trạng thái và kết thúc trong mili-giây. Trong khi đó, với ba lô phân số nơi cùng các món có thể chia nhỏ, tham lam chỉ cần khoảng O(40 log 40)≈200 phép toán sắp xếp theo giá trị đơn vị. Sự cắt giảm chi phí ngoạn mục "vét cạn mũ → DP đa thức → tham lam gần tuyến tính" này được mua, ở mỗi bước, bằng cái giá là một giả định mạnh hơn về cấu trúc bài toán — DP đòi hỏi cấu trúc con tối ưu, và tham lam đòi hỏi thêm tính chất lựa chọn tham lam. Không có bữa trưa miễn phí, và nguyên lý này rằng thuật toán càng nhanh thì điều kiện áp dụng càng ngặt làm nền tảng cho việc chọn mô thức.
Tóm tắt quan hệ ba kỹ thuật trong một câu, vét cạn là "đường cơ sở chậm nhưng luôn đúng," quy hoạch động là "bộ tối ưu hóa an toàn nén vét cạn về đa thức bằng cách loại bỏ dư thừa," và tham lam là "bộ tối ưu hóa nhanh nhất, với tiền đề một cấu trúc đặc thù, thu cả DP về một nhánh duy nhất." Các hệ thống thực tế thường kết hợp chúng — ví dụ, nhánh cận (branch and bound) cho ba lô 0/1 cắt tỉa không gian tìm kiếm vét cạn bằng một cận trên tham lam (lời giải ba lô phân số), đẩy hiệu năng thực dụng lên.
5. Nâng cao: Lý thuyết matroid và thuật toán xấp xỉ
Câu trả lời lý thuyết sâu sắc nhất cho "khi nào tham lam bảo đảm tối ưu" nằm ở matroid. Matroid là một cấu trúc nơi một tập hữu hạn và họ các tập con của nó (các tập độc lập) thỏa mãn tính di truyền (hereditary) và tính chất hoán đổi (exchange property), và định lý (Rado-Edmonds) rằng "nếu một bài toán được biểu diễn dưới dạng matroid có trọng số thì thuật toán tham lam luôn bảo đảm một lời giải tối ưu" được thỏa mãn. Lý do căn bản cây khung nhỏ nhất thu được tối ưu qua tham lam (Kruskal) cũng đến từ cấu trúc matroid đồ thị (graphic matroid) của đồ thị. Ở chỗ lý thuyết này làm sáng tỏ về mặt toán học "điều kiện đủ để tham lam đúng là gì" vượt quá "tham lam có vẻ đúng theo trực giác không," nó là một khuôn khổ mạnh mẽ tổng quát hóa các lập luận hoán đổi riêng lẻ. Dẫu vậy, không phải mọi thành công của tham lam đều được giải thích bằng matroid (chọn hoạt động và tương tự thỏa dưới điều kiện yếu hơn), và matroid là điều kiện đủ, chứ không phải điều kiện cần. Hàm ý thực tiễn của lý thuyết matroid là khi gặp một bài toán tối ưu mới, ta có thể sàng lọc trước về mặt cấu trúc khả năng áp dụng tham lam bằng cách kiểm tra "tập lời giải của bài toán này có thỏa tính di truyền và tính chất hoán đổi không?" Cũng được biết rằng trong khi giao của hai matroid (matroid intersection) vẫn giải được trong thời gian đa thức, thì giao của ba matroid trở lên vượt sang NP-khó, nên một bài toán có thể quy về bao nhiêu ràng buộc matroid trở thành thước đo lý thuyết để đo giới hạn áp dụng của tham lam và các thuật toán đa thức.
Một sân khấu quan trọng khác của tham lam là thuật toán xấp xỉ (approximation algorithm). Vì các bài toán tối ưu NP-khó được cho là không giải tối ưu được trong thời gian đa thức, nên trong thực tế người ta thỏa hiệp với một lời giải xấp xỉ "không tối ưu nhưng bảo đảm trong một tỷ lệ nhất định so với tối ưu." Đáng chú ý, trong bài toán phủ tập hợp (Set Cover), tham lam "lặp lại chọn tập phủ nhiều phần tử chưa phủ nhất" bảo đảm tỷ lệ xấp xỉ ln n, được biết là gần như tỷ lệ tốt nhất có thể về mặt lý thuyết dưới giả định P≠NP. Tham lam láng giềng gần nhất (nearest neighbor) cho bài toán người bán hàng rong (TSP) và tham lam công việc dài nhất trước (LPT) cho cân bằng tải công việc cũng là những phương pháp thực dụng với tỷ lệ xấp xỉ được bảo đảm. Như vậy, tham lam không chỉ là "bộ tối ưu hóa chính xác" mà còn là "bộ xấp xỉ đáng tin cậy cho các bài toán khó," hiện thực hóa sự đánh đổi điển hình là nhượng một phần tính đúng đắn để đổi lấy thời gian đa thức và bảo đảm hiệu năng.
Lý do tham lam được ưa chuộng đặc biệt trong thuật toán xấp xỉ nằm ở tính đơn giản và khả năng phân tích. Các phương án thay thế như tìm kiếm cục bộ, thuật toán di truyền, quy hoạch số nguyên có thể cho lời giải tốt hơn nhưng khó bảo đảm trước tính hội tụ và thời gian chạy, trong khi xấp xỉ tham lam đơn giản để cài đặt mà vẫn có thể chứng minh toán học một bảo đảm trường hợp xấu nhất (worst-case guarantee) là "trong vài lần tối ưu." Ví dụ, trong bài toán phân phối công việc trên nhiều máy để tối thiểu hóa thời điểm hoàn thành, tham lam LPT (công việc dài nhất trước) được chứng minh là trong khoảng (4/3 − 1/3m) so với tối ưu, cho phép một cam kết chất lượng rõ ràng trong thực tế như "dù tệ đến đâu, lịch này cũng không xấu hơn 33% so với tối ưu." Sự có mặt của một bảo đảm như vậy là yếu tố quyết định phân chia việc một thuật toán có thể được tin cậy và chọn dùng trong môi trường vận hành hay không, và đây chính là bối cảnh đưa xấp xỉ tham lam trở thành chiến lược mặc định của vô số bộ lập lịch và hệ thống xử lý lô.
Một xu hướng gần đây thu hút chú ý là tham lam trong môi trường trực tuyến và luồng. Trong các tình huống không thể thấy trước toàn bộ đầu vào và dữ liệu chảy vào (phân bổ quảng cáo trực tuyến, ghép cặp thời gian thực, phủ tập hợp dạng luồng), bản chất không ngoái lại của tham lam lại có sự phù hợp tự nhiên tốt. Như thuật toán RANKING cho ghép cặp hai phía trực tuyến đạt tỷ lệ cạnh tranh 1−1/e, phân tích cạnh tranh (competitive analysis) của các thuật toán trực tuyến dựa trên tham lam là một lĩnh vực nghiên cứu sôi động. Hơn nữa, kết quả rằng tham lam bảo đảm xấp xỉ 1−1/e trong tối đa hóa hàm dưới mô-đun (submodular function) cung cấp nền tảng lý thuyết cho tham lam trong các ứng dụng AI và dữ liệu hiện đại như hệ thống gợi ý, tóm tắt dữ liệu, bố trí cảm biến, cho thấy thuật toán tham lam đang mở rộng vượt khỏi các cấu trúc dữ liệu cổ điển sang các lĩnh vực mới nhất.
6. Cân nhắc và hàm ý
Khi chuyển các nguyên lý, ví dụ và lý thuyết của thuật toán tham lam đã khảo sát đến nay vào thiết kế hệ thống thực tế, Kỹ sư chuyên nghiệp phải phán đoán một cách toàn diện — cân nhắc tính hợp lệ, điều kiện áp dụng, và quan hệ với các phương án thay thế — thay vì chọn tham lam chỉ vì nó "nhanh." Sau đây là những cân nhắc then chốt trong phán đoán đó.
Cảnh giác với việc áp dụng tham lam mà không có chứng minh tính hợp lệ. Không được chọn dùng tham lam chỉ vì nó "trông có vẻ đúng theo trực giác"; phải kiểm chứng tính chất lựa chọn tham lam và cấu trúc con tối ưu qua lập luận hoán đổi hoặc cấu trúc matroid. Vì các trường hợp tham lam sai khi điều kiện thay đổi — như thối tiền và ba lô 0/1 — là phổ biến, ở giai đoạn phân tích yêu cầu nên chủ động kiểm tra "bài toán này có thực sự giải được bằng tham lam không, có phản ví dụ không?" để loại trừ các lời giải "có vẻ hợp lý nhưng sai."
Chuyển kỹ thuật theo điều kiện và ràng buộc của bài toán. Với cùng bài toán ba lô, kỹ thuật phù hợp phân chia thành tham lam (phân số) và DP (0/1) tùy theo 'có thể chia nhỏ không,' và sự có mặt của cạnh âm trong đồ thị chi phối khả năng áp dụng Dijkstra (tham lam). Phán đoán thiết kế là then chốt: chẩn đoán điều kiện và chọn mô thức đúng — tham lam nếu tính chất lựa chọn tham lam thỏa, DP nếu chỉ có bài toán con trùng lặp, vét cạn nếu đầu vào nhỏ và tính đúng đắn tuyệt đối.
Lựa chọn tiêu chí tham lam (khóa sắp xếp) quyết định tính hợp lệ. Như 'thời điểm kết thúc trước' là tối ưu nhưng 'hoạt động ngắn nhất trước' có phản ví dụ trong chọn hoạt động, ngay cả với cùng bài toán, lấy tiêu chí nào để lựa chọn tham lam sẽ phân chia đúng với sai. Do đó phải so sánh nhiều tiêu chí ứng viên, xem xét phản ví dụ của mỗi tiêu chí và chỉ chọn dùng tiêu chí có tính hợp lệ được chứng minh; bỏ qua quá trình này sẽ sinh ra một khiếm khuyết tiềm ẩn chỉ thất bại trên một số đầu vào.
Điều chỉnh sự đánh đổi giữa xấp xỉ và tính đúng đắn theo yêu cầu dịch vụ. Với các bài toán NP-khó, lời giải xấp xỉ tham lam thay vì tối ưu là lựa chọn thực tế, và điều quan trọng là biết tỷ lệ được bảo đảm, như xấp xỉ ln n của phủ tập hợp. Trong các hệ thống có ràng buộc thời gian thực và tài nguyên lớn (định tuyến, lập lịch, luồng), một lời giải tham lam 'nhanh và đủ tốt' có thể hợp lý hơn 'tối ưu hoàn hảo,' nên phải phán đoán điểm cân bằng giữa tính đúng đắn, tính đáp ứng và tài nguyên từ góc độ SLA và chi phí.
Kiểm chứng các cạm bẫy cài đặt và trường hợp biên. Vì tham lam thường là cấu trúc sắp xếp rồi duyệt, phải quy định rõ tính ổn định của sắp xếp và quy tắc xử lý hòa (tie) mới thu được kết quả tái lập được. Các lỗi cài đặt nhỏ — thiếu nén đường đi trong Union-Find của Kruskal, xử lý hòa tần suất trong cây Huffman, điều kiện biên (kết thúc=bắt đầu) của chọn hoạt động — có thể phá vỡ tính tối ưu, nên hãy đưa vào thiết kế việc kiểm chứng các trường hợp biên như bất khả đạt, đầu vào rỗng, và trọng số bằng nhau.
Tích cực tận dụng sự kết hợp của tham lam với các mô thức khác. Tham lam hữu dụng không chỉ đứng một mình mà còn như một phương tiện tăng tốc hoặc khởi tạo cho các kỹ thuật khác. Nhánh cận cắt tỉa vét cạn bằng một cận trên tham lam, tìm kiếm cục bộ và siêu kinh nghiệm (metaheuristic) cải thiện bằng cách lấy lời giải tham lam làm lời giải ban đầu, và các lý thuyết mở rộng như giao matroid mở rộng phạm vi áp dụng của tham lam. Góc nhìn tích hợp này — xem tham lam như một thành phần của tổng thể thiết kế tối ưu hóa — nâng cao năng lực giải quyết vấn đề thực tiễn.
Tóm lại, thuật toán tham lam là chiến lược đơn giản "lấy cái tốt nhất tại mỗi thời khắc và không ngoái lại," nhưng tính hợp lệ của nó được chống đỡ bởi tính chất lựa chọn tham lam và cấu trúc con tối ưu, và xa hơn bởi cấu trúc sâu của matroid. Khi điều kiện thỏa, tham lam cung cấp các lời giải tối ưu có thể chứng minh trong thời gian đa thức — như cây khung nhỏ nhất, mã hóa Huffman, và chọn hoạt động — và với các bài toán khó nó đưa ra lời giải thực dụng với tỷ lệ xấp xỉ được bảo đảm. Kỹ sư chuyên nghiệp phải có năng lực chẩn đoán chính xác cấu trúc bài toán, chọn mô thức đúng trong số tham lam, quy hoạch động và vét cạn, lập luận tính hợp lệ, và kết hợp các kỹ thuật tại điểm cân bằng giữa tính đúng đắn và hiệu năng.
Tài liệu tham khảo
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms" (3rd/4th ed.), Chapter 16: Greedy Algorithms, MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952. https://ieeexplore.ieee.org/document/4051119
- J. Edmonds, "Matroids and the greedy algorithm", Mathematical Programming, 1971. https://link.springer.com/article/10.1007/BF01584082
- V. Chvátal, "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, 1979. https://pubsonline.informs.org/doi/10.1287/moor.4.3.233
Tóm tắt một câu: Thuật toán tham lam là chiến lược chọn tối ưu cục bộ ở mỗi bước và không thu hồi; khi tính chất lựa chọn tham lam và cấu trúc con tối ưu (và xa hơn, một matroid) thỏa mãn, nó bảo đảm lời giải tối ưu trong thời gian đa thức — như cây khung nhỏ nhất, mã hóa Huffman, và ba lô phân số — nhưng khi điều kiện bị phá vỡ thì cho ra câu trả lời sai, nên điều then chốt là kiểm chứng tính hợp lệ bằng lập luận hoán đổi và chẩn đoán ranh giới với quy hoạch động và vét cạn để chọn mô thức đúng.