Tổng quan
Bài toán cây cầu và ngọn đèn là một bài lập lịch kinh điển: bốn người với tốc độ khác nhau phải qua một cây cầu tối trong đêm với một ngọn đèn dùng chung duy nhất, và cầu chỉ chịu được hai người một lúc.
Trực giác ngây thơ — luôn để người nhanh nhất mang đèn quay lại — không tối ưu. Nước đi thông minh là cho hai người chậm nhất qua cùng nhau, để thời gian của họ chồng lên nhau thay vì cộng dồn.
Cách giải Cây Cầu & Ngọn Đèn từng bước
- Cho hai người nhanh nhất (1 và 2) qua trước: 2 phút.
- Cho người nhanh nhất (1) mang đèn quay lại: 1 phút (tổng 3).
- Cho hai người chậm nhất (5 và 10) qua cùng nhau, để chỉ 'trả' 10 một lần: 10 phút (tổng 13).
- Cho người nhanh nhì (2) mang đèn quay lại: 2 phút (tổng 15).
- Cho hai người nhanh nhất (1 và 2) qua lần nữa: 2 phút (tổng 17).
Mấu chốt
Ghép hai người chậm nhất vào cùng một lượt qua. Đưa người 5 đi cùng người 10 khiến chi phí 5 phút bị 'giấu' hoàn toàn trong 10, thay vì mỗi chuyến chậm bị tính riêng.
Biến thể & liên hệ
- Với các thời gian khác, tối ưu chuyển đổi giữa hai chiến lược; bạn so sánh 'hai người nhanh đưa đón' với 'chở hai người chậm thành một cặp'.
- Đây là câu hỏi phỏng vấn kỹ thuật ưa thích về lối tư duy tham lam so với tối ưu.
- Ý tưởng chồng lấn tương tự xuất hiện trong lập lịch công việc và gộp lô tác vụ song song.
Câu hỏi thường gặp
Vì sao không luôn cho người nhanh nhất quay lại?
Kế hoạch 'tham lam' đó tốn 19 phút ở đây. Cho hai người chậm nhất qua cùng nhau tiết kiệm thời gian bằng cách chồng 5 vào trong 10.
17 có phải tối thiểu đã chứng minh không?
Đúng, với các thời gian 1, 2, 5, 10 không có kế hoạch nào nhanh hơn 17 phút.