Bài toán người du lịch (Travelling Salesman Problem) hỏi: cho một danh sách thành phố và khoảng cách giữa chúng, đâu là vòng đi ngắn nhất ghé mỗi thành phố đúng một lần rồi quay về? Đề bài một dòng, nhưng khó đến mức với vài chục thành phố, số vòng có thể có đã lớn hơn số hạt cát trên Trái Đất. Đến nay chưa ai biết có cách giải nhanh cho mọi trường hợp hay không — và câu hỏi ấy gắn với một giải thưởng một triệu đô la.
Đề bài, nói cho rõ
Một người giao hàng xuất phát từ kho, phải ghé 10 cửa hàng rồi về kho. Đi theo thứ tự nào cho tổng quãng đường ngắn nhất? Đó là bài toán người du lịch. Nó khác bài toán đường ngắn nhất (từ A đến B) ở chỗ: phải đi qua tất cả các điểm, và chọn thứ tự.
Trong ngôn ngữ đồ thị, ta tìm một chu trình Hamilton (đi qua mọi đỉnh đúng một lần) có tổng trọng số nhỏ nhất.
Vì sao khó: bùng nổ tổ hợp
Với n thành phố, cố định điểm xuất phát, số vòng đi khác nhau là (n − 1)! / 2 (chia đôi vì đi xuôi hay ngược là một).
| Số điểm | Số vòng có thể có |
|---|---|
| 5 | 12 |
| 8 | 2.520 |
| 10 | 181.440 |
| 15 | khoảng 43,6 tỉ |
| 20 | khoảng 6 × 10^16 (sáu chục triệu tỉ) |
| 63 (tỉnh thành Việt Nam trước 7/2025) | một con số có khoảng 86 chữ số |
Một máy tính kiểm một tỉ vòng mỗi giây cần gần hai năm cho 20 điểm. Với 30 điểm, thời gian vượt xa tuổi của vũ trụ. Thử hết là không thể; phải thông minh hơn.
Lịch sử ngắn
- Thế kỷ 19: William Rowan Hamilton nghĩ ra câu đố Icosian (năm 1857): tìm vòng đi qua 20 đỉnh của một khối mười hai mặt, mỗi đỉnh một lần. Chưa có khoảng cách, nhưng đã là hạt giống của chu trình Hamilton. Sổ tay cho người bán hàng rong ở Đức thế kỷ 19 cũng đã bàn chuyện chọn lộ trình.
- Thập niên 1930: nhà toán học Karl Menger và các đồng nghiệp bắt đầu nghiên cứu bài toán theo cách toán học.
- 1954: George Dantzig, Ray Fulkerson và Selmer Johnson giải chính xác một bài 49 thành phố của Mỹ — kỷ lục lớn thời đó, bằng phương pháp quy hoạch tuyến tính.
- Thập niên 1970: người ta chứng minh bài toán thuộc nhóm "NP-khó" — nhóm bài toán mà chưa ai tìm được cách giải nhanh cho mọi trường hợp.
- Những năm 2000: phần mềm Concorde giải chính xác các bài hàng chục nghìn điểm, trong đó có bài khoảng 85.900 điểm lấy từ thiết kế một con chip.
P và NP: câu hỏi một triệu đô la
Bài toán người du lịch có một đặc điểm: nếu ai đưa bạn một vòng đi và nói "vòng này dài dưới 500 km", bạn kiểm tra rất nhanh — cộng các đoạn lại là xong. Nhưng tự tìm ra một vòng như thế thì khó. Câu hỏi "mọi bài toán dễ kiểm thì cũng dễ giải?" gọi là bài toán P và NP. Năm 2000, Viện Toán Clay đưa nó vào danh sách bảy bài toán thiên niên kỷ, mỗi bài thưởng một triệu đô la. Tính tới nay, chưa ai giải được.
Nếu có người tìm ra cách giải nhanh bài toán người du lịch cho mọi trường hợp, họ sẽ đồng thời giải được hàng nghìn bài toán khó khác — vì chúng có thể chuyển đổi qua lại. Phần lớn nhà khoa học đoán rằng cách giải nhanh như vậy không tồn tại, nhưng chưa ai chứng minh được.
Người ta làm gì trong thực tế
Không tìm được lời giải tốt nhất nhanh, thì tìm lời giải đủ tốt thật nhanh:
- Láng giềng gần nhất: từ điểm hiện tại, luôn đi đến điểm gần nhất chưa ghé. Rất nhanh, rất dễ, nhưng thường dài hơn tối ưu một khoảng đáng kể, vì cuối cùng hay phải "chạy về" từ rất xa.
- Gỡ chéo (2-opt): nhìn vòng đi, chỗ nào hai đoạn cắt chéo nhau thì đảo ngược một khúc để gỡ chéo. Vòng không cắt chéo gần như luôn ngắn hơn. Lặp lại đến khi không còn chỗ chéo.
- Thuật toán có bảo đảm: năm 1976, Nicos Christofides đưa ra cách luôn tìm được vòng không dài quá 1,5 lần vòng tối ưu, với điều kiện khoảng cách tuân theo bất đẳng thức tam giác.
- Tìm kiếm thông minh: các phương pháp lấy cảm hứng từ tự nhiên (đàn kiến, tôi luyện kim loại, tiến hoá) cho kết quả rất sát tối ưu với bài lớn.
Bài toán người du lịch quanh ta
- Giao hàng: xếp thứ tự ghé các điểm trong ngày cho shipper, xe tải.
- Khoan mạch điện: máy khoan phải đi qua hàng nghìn lỗ trên bảng mạch; thứ tự tốt tiết kiệm nhiều thời gian máy.
- Kính thiên văn: xếp thứ tự quan sát các ngôi sao để kính xoay ít nhất.
- Sắp xếp gen: ghép các đoạn ADN theo thứ tự hợp lý.
- Du lịch thật: xếp lịch thăm các điểm trong một chuyến đi để bớt quay đầu.
Góc nhìn hôm nay: thử với bảy điểm
Lấy bản đồ một thành phố bạn sắp đi chơi, đánh dấu bảy điểm muốn ghé cùng khách sạn. Bảy điểm cộng khách sạn là 8 điểm, có 2.520 vòng đi — quá nhiều để thử hết, nhưng đủ nhỏ để thử hai cách: (1) láng giềng gần nhất, (2) vẽ xong rồi gỡ mọi chỗ cắt chéo. So tổng quãng đường. Bạn sẽ thấy cách gỡ chéo đơn giản thường cho kết quả tốt bất ngờ — và bạn vừa dùng đúng mẹo mà các phần mềm tối ưu lộ trình dùng mỗi ngày.
Câu hỏi thường gặp
Bài toán người du lịch là gì?
Là bài toán tìm vòng đi ngắn nhất ghé mỗi thành phố trong danh sách đúng một lần rồi quay về điểm xuất phát, khi biết khoảng cách giữa các thành phố.
Vì sao bài toán người du lịch khó?
Vì số vòng có thể có tăng theo giai thừa: 10 điểm có 181.440 vòng, 20 điểm có khoảng 6 × 10^16 vòng. Chưa ai tìm được cách giải nhanh chính xác cho mọi trường hợp.
Bài toán người du lịch liên quan gì đến giải một triệu đô la?
Nó thuộc nhóm bài toán NP-khó. Tìm được cách giải nhanh cho nó sẽ giải quyết câu hỏi P và NP, một trong bảy bài toán thiên niên kỷ của Viện Toán Clay với giải thưởng một triệu đô la.
Trong thực tế người ta giải bài toán người du lịch thế nào?
Dùng các cách tìm lời giải đủ tốt thật nhanh, như đi đến điểm gần nhất, gỡ các đoạn cắt chéo, thuật toán Christofides và các phương pháp tìm kiếm thông minh.
Bài toán người du lịch được ứng dụng ở đâu?
Trong giao hàng, xếp lộ trình xe, khoan bảng mạch điện, điều khiển kính thiên văn, sắp xếp gen và lên lịch du lịch.