Quy hoạch động ở bài trước xét mọi khả năng để chắc chắn ra lời giải tối ưu. Có một cách tiếp cận cám dỗ hơn nhiều: tham lam (greedy) — cứ chọn cái tốt nhất ngay lúc này ở mỗi bước, không nhìn xa, không lật lại. Nó nhanh, nó gọn, và trong rất nhiều trường hợp nó cho đúng đáp án tối ưu. Vấn đề là "rất nhiều" không phải "mọi", và ranh giới đó là chỗ người ta ngã. Bài này 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 đó, và đị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.
Đo: 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.
Một lần tôi đo hớ: "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 là một sự đánh đổi hấp dẫn — nó chỉ là sai nhanh hơn. Bài học đo lường: 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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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 — bài về Dijkstra sau sẽ là một ví dụ tham lam đúng), 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.
Hệ quả thứ ba là con số mang theo: tham lam đổi tiền đúng 100% với hệ xu chuẩn {1,5,10,25} nhưng sai 25-40% số tiền với các hệ khác ({1,7,10}, số 14: tham lam 5 xu, tối ưu 2 xu), vì hệ tiền thật được thiết kế cho tham lam chứ tham lam không tự đúng; nó nhanh hơn DP ~100 triệu lần cho một truy vấn (2,1ns so với 228ms) nhưng nhanh mà sai thì vô dụng, còn DP chậm hơn mà luôn tối ưu. 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.
Thử ba mươi giây
Lần tới khi bạn định giải một bài tối ưu bằng một 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 và rẻ: 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 bạn 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 và 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.
