09/06/2025
09/06/2025
Apple_SQV2i7WHqMWjQeELNhPsuHYUetB2
09/06/2025
09/06/2025
Apple_SQV2i7WHqMWjQeELNhPsuHYUetB2
Câu 2. Giả sử 4 thành phố A,B,C,D với khoảng cách (đơn vị: km) giữa các thành phố được cho bởi bảng sau:
Hãy tính quãng đường ngắn nhất để đi qua tất cả các thành phố đúng một lần rồi quay lại thành phố xuất phát?
Lời giải:
Sử dụng thuật toán láng giềng gần ta có:
Tổng số quãng đường đi được theo chu trình ABCDA là: 85 (km)
Tương tự với các đỉnh còn lại, ta có bảng sau:
Đỉnh bắt đầuChu trìnhTổng số quãng đường (km)AABCDA85BBACDB90CCABDC80DDABCD85
Vậy cần chọn đường đi ngắn nhất là CABDC với tổng số km là 80.
Đáp số: 80.
Nếu bạn muốn hỏi bài tập
Các câu hỏi của bạn luôn được giải đáp dưới 10 phút
CÂU HỎI LIÊN QUAN
2 giờ trước
2 giờ trước
Top thành viên trả lời