Bài toán người du lịch (Traveling Salesman Problem - TSP) là một bài toán kinh điển trong tối ưu tổ hợp và lý thuyết đồ thị. Nó được phát biểu như sau:

Phát biểu bài toán TSP:

Cho một danh sách các thành phố và khoảng cách (hoặc chi phí) giữa mỗi cặp thành phố. Tìm một hành trình ngắn nhất mà:

• Đi qua mỗi thành phố đúng một lần, và
• Trở về thành phố xuất phát.

Tính chất của TSP trong tối ưu tổ hợp:

• Là một bài toán NP-hard: Không có thuật toán đa thức nào được biết để giải TSP chính xác trong thời gian hợp lý với dữ liệu lớn.
• Không gian nghiệm rất lớn: Với n thành phố, có (n−1)!/2 tour khác nhau (nếu không xét hướng đi).
• Ứng dụng thực tế: Lập lịch, hậu cần, thiết kế mạch in, robot path planning...

Các phương pháp giải TSP:

1. Phương pháp chính xác (Exact algorithms):

• Brute force: Thử tất cả hoán vị — chỉ áp dụng được khi nnn nhỏ.
• Quy hoạch động (Dynamic Programming): Bellman–Held–Karp algorithm, độ phức tạp O(n22n).
• Ràng buộc và nhánh (Branch and Bound)

2. Phương pháp xấp xỉ (Heuristics):

• Greedy, Nearest Neighbor
• Christofides’ algorithm (áp dụng được nếu đồ thị thỏa mãn bất đẳng thức tam giác, cho kết quả ≤ 1.5 lần tối ưu)

3. Phương pháp metaheuristics (Tối ưu hóa mềm):

• Genetic Algorithms (GA)
• Simulated Annealing
• Ant Colony Optimization
• Particle Swarm Optimization

Ví dụ bài toán:

Giả sử có 5 thành phố với ma trận khoảng cách giữa các thành phố như sau (đơn vị: km):

🔄 Giải bằng thuật toán Nearest Neighbor (tham lam):

1. Bắt đầu từ thành phố A
2. Mỗi bước, đi đến thành phố gần nhất chưa đi qua
3. Khi đã đi qua tất cả, quay về A

📋 Bước giải:

• Bắt đầu từ A
• Từ A: gần nhất là B (10 km)
• Từ B: gần nhất là E (17 km)
• Từ E: gần nhất là D (14 km)
• Từ D: gần nhất là C (30 km)
• Quay lại A từ C: 15 km

✏️ Tổng đường đi:

A → B (10) → E (17) → D (14) → C (30) → A (15)
Tổng = 10 + 17 + 14 + 30 + 15 = 86 km