Bài toán người đưa thư Trung Hoa hỏi: người đưa thư phải đi qua mọi con phố trong khu vực ít nhất một lần rồi về bưu cục, vậy đi thế nào cho tổng quãng đường ngắn nhất? Nếu mạng phố có 0 ngã tư "lẻ", người đó đi một vòng Euler hoàn hảo, không lặp đoạn nào. Nếu có ngã tư lẻ, phải đi lại một số đoạn — và cách chọn đoạn đi lại tốt nhất là ghép các ngã tư lẻ thành từng cặp gần nhau nhất. Bài toán mang tên "Trung Hoa" vì nhà toán học Trung Quốc Quản Mai Cốc (Kwan Mei-Ko) đặt ra đầu thập niên 1960.
Từ bưu cục đến bài báo toán học
Quản Mai Cốc là giảng viên toán ở Sơn Đông. Đầu thập niên 1960, khi làm việc liên quan đến tổ chức phát thư, ông đặt câu hỏi: người đưa thư phải đi qua mọi con phố được phân công, làm sao bớt quãng đường đi lặp lại? Bài viết của ông in bằng tiếng Trung, sau đó được dịch sang tiếng Anh. Nhà toán học Mỹ Alan Goldman được cho là người đặt cái tên "Chinese postman problem" để ghi nhận nguồn gốc ấy.
Năm 1973, Jack Edmonds và Ellis Johnson đưa ra cách giải hoàn chỉnh, chạy nhanh trên máy tính cho cả mạng phố rất lớn.
Khác gì bài toán người du lịch?
| Người du lịch | Người đưa thư | |
|---|---|---|
| Phải đi qua | Mọi điểm (thành phố) | Mọi đoạn đường (con phố) |
| Gốc toán học | Chu trình Hamilton | Chu trình Euler |
| Độ khó | Rất khó, chưa có cách giải nhanh | Có cách giải nhanh, chính xác |
| Ví dụ | Giao hàng đến từng địa chỉ | Quét đường, thu gom rác, đọc đồng hồ nước |
Hai bài toán trông như anh em sinh đôi, nhưng một bài khó đến mức thành câu hỏi một triệu đô la, một bài có lời giải đẹp. Lý do: với cạnh, ta có quy tắc đếm bậc lẻ của Euler; với đỉnh, không có quy tắc nào tương tự.
Lời giải, từng bước
- Vẽ mạng phố thành đồ thị: ngã tư là đỉnh, đoạn phố là cạnh, ghi độ dài mỗi đoạn.
- Đếm bậc: tìm các ngã tư lẻ (số đoạn phố gặp nhau là số lẻ). Số ngã tư lẻ luôn chẵn.
- Nếu không có ngã tư lẻ: có vòng Euler — đi qua mọi đoạn đúng một lần. Xong. Tổng quãng đường bằng tổng độ dài phố.
- Nếu có ngã tư lẻ: ghép chúng thành từng cặp, sao cho tổng khoảng cách ngắn nhất giữa các cặp là nhỏ nhất.
- "Nhân đôi" các đoạn đường nối mỗi cặp (tức là sẽ đi các đoạn đó hai lần). Giờ mọi ngã tư đều chẵn.
- Đi vòng Euler trên mạng mới.
Phần khó nhất là bước 4 khi có nhiều ngã tư lẻ: có rất nhiều cách ghép cặp. Edmonds đã tìm ra thuật toán "ghép cặp tối ưu" giải bước này nhanh — đó là đóng góp lớn của ông.
Ví dụ nhỏ
Một khu phố hình chữ nhật chia làm hai ô bởi một con phố giữa. Có 6 ngã tư: 4 góc (mỗi góc 2 đoạn phố → chẵn) và 2 điểm nơi phố giữa chạm hai cạnh dài (mỗi điểm 3 đoạn → lẻ). Hai ngã tư lẻ nối với nhau bằng chính con phố giữa. Lời giải: đi con phố giữa hai lần, mọi đoạn khác một lần. Quãng đường thêm đúng bằng chiều dài con phố giữa — không cách nào ít hơn.
Ứng dụng: những người đi qua mọi con phố
- Xe quét đường, xe tưới cây: phải đi qua mọi đoạn đường được giao.
- Xe thu gom rác: ghé mọi con phố có nhà dân.
- Nhân viên đọc chỉ số đồng hồ điện, nước: đi dọc mọi dãy nhà.
- Xe dọn tuyết ở các nước xứ lạnh.
- Kiểm tra đường dây, đường ống: thanh tra đi dọc mọi đoạn.
- Xe chụp ảnh đường phố cho bản đồ.
Thực tế phức tạp hơn bài toán gốc: có đường một chiều (đồ thị có hướng), có xe quét chỉ quét được một bên đường mỗi lượt, có giờ cấm. Mỗi điều kiện thêm sinh ra một biến thể, có biến thể vẫn dễ, có biến thể trở nên khó như bài toán người du lịch.
Góc nhìn hôm nay: lộ trình đi bộ thể dục
Bạn muốn đi bộ buổi sáng qua mọi con ngõ trong khu mình ở, rồi về nhà. Vẽ sơ đồ các ngõ, đánh dấu ngã ba (thường là điểm lẻ, vì có 3 nhánh). Ghép các ngã ba thành từng cặp gần nhau nhất, những đoạn nối các cặp là đoạn bạn sẽ đi hai lần. Ngõ cụt cũng là một điểm lẻ (chỉ một nhánh), nên mỗi ngõ cụt chắc chắn phải đi vào rồi đi ra — đúng như kinh nghiệm. Bạn vừa giải bài toán người đưa thư cho chính đôi chân mình.
Câu hỏi thường gặp
Bài toán người đưa thư Trung Hoa là gì?
Là bài toán tìm lộ trình ngắn nhất đi qua mọi đoạn đường trong một mạng ít nhất một lần rồi quay về điểm xuất phát, như lộ trình của người đưa thư hay xe quét đường.
Vì sao gọi là bài toán người đưa thư Trung Hoa?
Vì nhà toán học Trung Quốc Quản Mai Cốc (Kwan Mei-Ko) đặt ra bài toán đầu thập niên 1960 khi nghiên cứu việc phát thư. Cái tên tiếng Anh được đặt sau để ghi nhận nguồn gốc này.
Bài toán người đưa thư khác bài toán người du lịch thế nào?
Người đưa thư phải đi qua mọi đoạn đường, có cách giải nhanh dựa trên chu trình Euler. Người du lịch phải ghé mọi điểm, là bài toán rất khó chưa có cách giải nhanh chính xác.
Giải bài toán người đưa thư thế nào?
Tìm các ngã tư có số đoạn phố lẻ, ghép chúng thành từng cặp sao cho tổng khoảng cách nhỏ nhất, đi lại các đoạn nối mỗi cặp, rồi đi một vòng Euler trên mạng mới.