Leo núi bằng cách "mỗi bước cứ chọn hướng dốc lên nhất" nghe rất hợp lý — cho tới khi bạn kẹt trên một mỏm đồi thấp, xung quanh đều dốc xuống, mà đỉnh thật thì ở tận bên kia thung lũng. Chọn cái tốt nhất ngay lúc này không đảm bảo tới được cái tốt nhất cuối cùng. Đó chính là ranh giới giữa tham lam (greedy) và quy hoạch động. QHĐ xét mọi khả năng để chắc chắn ra lời giải tối ưu; tham lam thì cứ chộp cái tốt nhất mỗi bước, không nhìn xa, không lật lại. Nó nhanh, gọn, và trong rất nhiều trường hợp cho đúng đáp án tối ưu. Vấn đề là "rất nhiều" không phải "mọi", và đó là chỗ người ta ngã. Tôi lấy bài toán đổi tiền — nơi tham lam trông hiển nhiên đúng đến mức ta làm nó mỗi ngày với ví tiền thật — và đo xem nó đúng thật tới đâu.
Tham lam trông hiển nhiên đúng
Bài toán: trả một số tiền T bằng ít đồng xu nhất. Thuật toán tham lam hiển nhiên: cứ lấy đồng xu lớn nhất còn nhỏ hơn hoặc bằng phần dư, lặp lại. Trả 87 xu với hệ tiền Mỹ {1, 5, 10, 25}? Lấy 25, 25, 25 (còn 12), rồi 10 (còn 2), rồi 1, 1 — sáu đồng. Đó đúng là cách ai cũng làm khi thối tiền, và nó cho ra số xu ít nhất. Trực giác này mạnh đến mức ta hiếm khi hỏi tại sao nó đúng — ta chỉ biết nó luôn đúng. Tôi vào bài với đúng niềm tin đó, định đo để xác nhận "tham lam vừa nhanh vừa đúng cho đổi tiền". Đồng hồ và bảng DP nói khác.
Tham lam sai 25 tới 40% số tiền
Tôi cài cả hai — tham lam (lấy đồng lớn nhất) và DP (bảng số xu ít nhất, tabulation từ bài trước, luôn tối ưu) — rồi với mỗi số tiền từ 1 tới 100 000, so số xu tham lam dùng với số xu tối ưu, đếm bao nhiêu lần tham lam dùng nhiều hơn:
hệ xu tham lam sai (dùng nhiều xu hơn tối ưu)
{1, 5, 10, 25} (Mỹ) 0 % (luôn tối ưu)
{1, 3, 4} 25 %
{1, 7, 10} 30 %
{1, 10, 25} 40 % (bỏ đồng 5 khỏi hệ Mỹ)
Với hệ tiền thật, tham lam đúng tuyệt đối — 0% sai. Nhưng chỉ cần đổi sang một hệ xu khác, nó sai trên một phần rất lớn số tiền. Ví dụ rõ nhất: hệ {1, 7, 10}, trả 14 xu. Tham lam lấy 10 trước (vì là đồng lớn nhất ≤ 14), rồi phải bù bằng 1+1+1+1 — năm đồng. Nhưng đáp án tối ưu là 7+7 — hai đồng. Tham lam gấp hơn hai lần tối ưu, vì nó chộp lấy đồng 10 lớn nhất ở bước đầu mà không thấy rằng bỏ qua nó để dùng hai đồng 7 sẽ tốt hơn. Đây là bản chất của tham lam: nó tối ưu từng bước nhưng có thể hỏng toàn cục — đúng cái mỏm đồi thấp ở đầu bài.
"Nhanh" vô nghĩa nếu chưa hỏi "đúng chưa"
Cú hớ của tôi nằm ngay ở giả định ban đầu: tham lam đúng cho đổi tiền vì với tiền thật nó luôn đúng. Đo xong tôi thấy mình đã đảo ngược nhân quả. Không phải tham lam đúng nên tiền dùng nó; mà là các hệ tiền thật được thiết kế (một cách có chủ ý) sao cho tham lam đúng — đó là một tính chất đặc biệt của những hệ xu "chuẩn", không phải một sự thật chung của bài toán đổi tiền. Rút một đồng ra khỏi hệ Mỹ (bỏ đồng 5, còn {1, 10, 25}) là tham lam lập tức sai 40% số tiền. Tôi đã nhầm một tính chất được cài đặt sẵn vào dữ liệu thành một tính chất của thuật toán.
Và về tốc độ, tham lam đúng là nhanh khủng khiếp. Trả lời một số tiền T = 100 triệu: tham lam mất 2,1 nano giây (chỉ vài phép chia, không cần bảng), trong khi DP phải dựng một bảng 100 triệu ô mất 228 mili giây — tham lam nhanh hơn khoảng một trăm triệu lần. Nhưng đây chính là cái bẫy mà cả sê-ri lặp đi lặp lại: "nhanh" là một câu trả lời vô nghĩa cho tới khi bạn đã hỏi "đúng chưa". Một thuật toán nhanh hơn trăm triệu lần mà cho sai đáp số trên 40% đầu vào thì không phải một sự đánh đổi hấp dẫn — nó chỉ là sai nhanh hơn. Điều rút ra: tính đúng của tham lam là một thứ phải chứng minh hoặc kiểm chứng cho từng bài, không phải một mặc định vì nó "trông hợp lý". Tham lam là một chiến lược, không phải một sự bảo đảm.
Về đến code hằng ngày
Điều đầu tiên, rất cụ thể: đừng dùng tham lam cho một bài tối ưu trừ khi bạn đã chứng minh (hoặc kiểm bằng brute-force/DP trên miền nhỏ) rằng nó cho tối ưu. Tham lam cám dỗ vì nó ngắn, nhanh, và thường đúng trên các ví dụ bạn nghĩ ra đầu tiên — đúng như tham lam đổi tiền đúng trên hệ Mỹ mà bạn quen. Rồi dữ liệu thật đưa vào một cấu hình mà tính chất tham lam không giữ, và bạn nhận đáp án dưới tối ưu mà không hề có lỗi báo. Cách an toàn: với một bài tham lam nghi ngờ, viết thêm một lời giải DP/brute-force chậm nhưng chắc, chạy cả hai trên nhiều đầu vào ngẫu nhiên, và xem chúng có bao giờ lệch không. Nếu lệch, tham lam sai.
Điều thứ hai, về cân nhắc: khi tham lam đã được chứng minh đúng, nó là món hời lớn. Cái giá 228 mili giây so với 2,1 nano giây là khác biệt thật, và với những bài mà tính chất tham lam giữ vững (có cả một lớp bài như vậy — Dijkstra là một ví dụ tham lam đúng nhờ điều kiện trọng số không âm), chọn tham lam là chọn nhanh hơn hàng triệu lần mà không mất gì. Điểm mấu chốt là thứ tự: chứng minh đúng trước, hưởng tốc độ sau — không đảo ngược.
Và cái bẫy "tối ưu cục bộ không phải tối ưu toàn cục" này bám theo bạn xa hơn bài đổi tiền nhiều. Bộ tối ưu truy vấn của cơ sở dữ liệu là một ví dụ sống: chọn thứ tự join bằng tham lam (cứ ghép hai bảng rẻ nhất trước) nhanh nhưng có thể ra kế hoạch tệ, nên PostgreSQL dùng quy hoạch động cho tới ~8 bảng rồi mới chuyển sang tìm kiếm tham lam/di truyền (geqo) khi không gian quá lớn — đúng sự đánh đổi "đúng nhưng chậm" đối "nhanh nhưng gần đúng". Huấn luyện mô hình bằng gradient descent cũng là leo dốc tham lam và có thể kẹt ở cực tiểu địa phương. Ngay cả trình biên dịch phân bổ thanh ghi hay các bộ lập lịch đều chọn giữa heuristic tham lam (nhanh) và tối ưu đầy đủ (đắt). Mẫu số chung: tốc độ và tính đúng là hai câu hỏi tách biệt, và trả lời câu tốc độ trước câu đúng là cách chắc chắn để tự lừa mình.
Muốn tự phòng thì lần tới khi định giải một bài tối ưu bằng quy tắc "cứ chọn cái tốt nhất mỗi bước", dừng lại và hỏi: tôi có chắc chọn tốt nhất từng bước sẽ cho tốt nhất toàn cục không, hay tôi chỉ đang hy vọng vậy? Cách thử nhanh: nghĩ ra vài ví dụ nhỏ nơi một lựa chọn tham ở bước đầu có thể khóa bạn khỏi một lời giải tốt hơn về sau — như đồng xu 10 chắn mất cặp 7+7. Nếu tìm được dù chỉ một ví dụ như thế, tham lam sai, và bạn cần quy hoạch động. Nếu không tìm được mà vẫn cần chắc chắn, hãy viết một lời giải DP chậm để đối chiếu trên hàng nghìn đầu vào ngẫu nhiên. Đừng để đầu vào của người dùng là thứ đầu tiên phát hiện rằng "cái tốt nhất mỗi bước" của bạn không hề tốt nhất.
