💡 Dữ liệu khoảng cách giữa các nhà (theo phút):
Hạnh | Hà | Đô | Ngọc | |
|---|---|---|---|---|
Hạnh | 0 | 6 | 6 | 14 |
Hà | 6 | 0 | 4 | 10 |
Đô | 6 | 4 | 0 | 8 |
Ngọc | 14 | 10 | 8 | 0 |
🔍 Các chu trình có thể (bắt đầu và kết thúc tại cùng một nhà):
Ta xét tất cả các hoán vị có thể của 3 điểm còn lại, rồi quay lại điểm xuất phát. Có 4 nhà nên mỗi bạn có thể là điểm bắt đầu, và có \(\left(\right. n - 1 \left.\right) ! = 3 ! = 6\) hoán vị các nhà còn lại.
Ví dụ với xuất phát từ nhà Hạnh:
- Hạnh → Hà → Đô → Ngọc → Hạnh:
6 (Hà) + 4 (Đô) + 8 (Ngọc) + 14 = 32 phút - Hạnh → Hà → Ngọc → Đô → Hạnh:
6 + 10 + 8 + 6 = 30 phút - Hạnh → Đô → Hà → Ngọc → Hạnh:
6 + 4 + 10 + 14 = 34 phút - Hạnh → Đô → Ngọc → Hà → Hạnh:
6 + 8 + 10 + 6 = 30 phút - Hạnh → Ngọc → Hà → Đô → Hạnh:
14 + 10 + 4 + 6 = 34 phút - Hạnh → Ngọc → Đô → Hà → Hạnh:
14 + 8 + 4 + 6 = 32 phút
Tương tự, bạn có thể thử với xuất phát từ các nhà còn lại, nhưng vì bài toán yêu cầu chỉ cần tìm đường đi ngắn nhất, ta chỉ cần chọn thời gian nhỏ nhất trong các chu trình trên.
✅ Kết luận:
- Lộ trình tối ưu nhất là:
Hạnh → Hà → Ngọc → Đô → Hạnh hoặc Hạnh → Đô → Ngọc → Hà → Hạnh - Tổng thời gian: 30 phút
- Đây là thời gian ngắn nhất để đi qua tất cả các nhà và quay lại nhà xuất phát.
