1. Danh sách các điểm:
- H: Hạnh
- Đ: Đô
- A: Hà
- N: Ngọc
2. Bảng thời gian đi giữa các nhà (đơn vị: phút)
Từ/Đến | Hạnh | Đô | Hà | Ngọc |
Hạnh | 0 | 6 | 6 | 14 |
Đô | 6 | 0 | 4 | 8 |
Hà | 6 | 4 | 0 | 10 |
Ngọc | 14 | 8 | 10 | 0 |
3. Xét tất cả các chu trình bắt đầu từ mỗi điểm, quay lại điểm đó, đi qua tất cả các nhà:
Tổng cộng có (4−1)! = 6 chu trình cho mỗi điểm xuất phát. Ta sẽ thử tất cả:
Xuất phát từ Hạnh (H):
- H → Đ → A → N → H: 6 + 4 + 10 + 14 = 34
- H → Đ → N → A → H: 6 + 8 + 10 + 6 = 30
- H → A → Đ → N → H: 6 + 4 + 8 + 14 = 32
- H → A → N → Đ → H: 6 + 10 + 8 + 6 = 30
- H → N → Đ → A → H: 14 + 8 + 4 + 6 = 32
- H → N → A → Đ → H: 14 + 10 + 4 + 6 = 34
→ Tối ưu khi xuất phát từ Hạnh: 30 phút
Xuất phát từ Đô (Đ):
- Đ → H → A → N → Đ: 6 + 6 + 10 + 8 = 30
- Đ → H → N → A → Đ: 6 + 14 + 10 + 4 = 34
- Đ → A → H → N → Đ: 4 + 6 + 14 + 8 = 32
- Đ → A → N → H → Đ: 4 + 10 + 14 + 6 = 34
- Đ → N → H → A → Đ: 8 + 14 + 6 + 4 = 32
- Đ → N → A → H → Đ: 8 + 10 + 6 + 6 = 30
→ Tối ưu khi xuất phát từ Đô: 30 phút
Xuất phát từ Hà (A):
- A → H → Đ → N → A: 6 + 6 + 8 + 10 = 30
- A → H → N → Đ → A: 6 + 14 + 8 + 4 = 32
- A → Đ → H → N → A: 4 + 6 + 14 + 10 = 34
- A → Đ → N → H → A: 4 + 8 + 14 + 6 = 32
- A → N → H → Đ → A: 10 + 14 + 6 + 4 = 34
- A → N → Đ → H → A: 10 + 8 + 6 + 6 = 30
→ Tối ưu khi xuất phát từ Hà: 30 phút
Xuất phát từ Ngọc (N):
- N → H → Đ → A → N: 14 + 6 + 4 + 10 = 34
- N → H → A → Đ → N: 14 + 6 + 4 + 8 = 32
- N → Đ → H → A → N: 8 + 6 + 6 + 10 = 30
- N → Đ → A → H → N: 8 + 4 + 6 + 14 = 32
- N → A → H → Đ → N: 10 + 6 + 6 + 8 = 30
- N → A → Đ → H → N: 10 + 4 + 6 + 14 = 34
→ Tối ưu khi xuất phát từ Ngọc: 30 phút
→ Kết luận: Bất kỳ bạn nào cũng có thể xuất phát, vì thời gian ngắn nhất đều là 30 phút.
Xin nhận giải ạ :)