Link đến bài TSP - Bài toán người du lịch
Cách 1: Duyệt quay lui, nhánh cận (Cách này thường không giải được với n >= 18)
Cách 2: Quy hoạch động trạng thái:
- Gọi là chi phí nhỏ nhất để xuất phát từ thành phố , đi thăm các thành phố có chỉ số là bit trong dãy bit biểu diễn (ta đánh số bit phải cùng có chỉ số là ) và thành phố thăm cuối cùng trong hành trình là (tất nhiên bit trong biểu diễn của mask phải bằng )
- Ta QHĐ (có thể dùng đệ quy có nhớ hay dạng BFS để tính toán mảng f). Chú ý: Từ trạng thái có thể đến được trạng thái nếu có đường đi từ tới và chỉ nhiều hơn một bit là bit thứ .
- Kết quả của bài toán:
Tham khảo thêm bài LEM3