30/09/2018, 16:13
Bài Toán Người Du lịch
cho n thánh phố đánh từ 1 -> n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp n x n, ở đây C[a,b]= c[b][a] chi phí đi đoạn đường trực tiếp từ thành phố a đến b. Giả thiết rằng C[a][b]=0 với , C[a][b]= dương vô cùng nếu không có đường trực tiếp từ thành phố a -> b.
Một người xuất phát từ thành phố 1, muốn đi tất cả thành phố còn lại. Mỗi thành phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra chi phí thấp nhất cho chuyến hành trình?
Bài liên quan
