Đội cứu trợ xuất phát từ trạm chỉ huy $T$, cần đến thăm các thôn $A, B, C, D$ (mỗi nơi đúng một lần) rồi quay về $T$. Bảng khoảng cách (km) giữa các địa điểm:
| | T | A | B | C | D |
|---|---|---|---|---|---|
| T | 0 | 10 | 5 | 11 | 12 |
| A | 10 | 0 | 5 | 9 | 6 |
| B | 5 | 5 | 0 | 2 | 4 |
| C | 11 | 9 | 2 | 0 | 8 |
| D | 12 | 6 | 4 | 8 | 0 |
Tính tổng quãng đường nhỏ nhất (km) của hành trình khép kín.
| | T | A | B | C | D |
|---|---|---|---|---|---|
| T | 0 | 10 | 5 | 11 | 12 |
| A | 10 | 0 | 5 | 9 | 6 |
| B | 5 | 5 | 0 | 2 | 4 |
| C | 11 | 9 | 2 | 0 | 8 |
| D | 12 | 6 | 4 | 8 | 0 |
Tính tổng quãng đường nhỏ nhất (km) của hành trình khép kín.
ĐÁP ÁN
3
1
LỜI GIẢI
Bước 1 — Đọc dữ liệu.
Ma trận đối xứng: ô hàng $X$ cột $Y$ là khoảng cách $d_{XY}$ (đường chéo bằng $0$, $d_{XY}=d_{YX}$).
Bước 2 — Công thức chu trình.
Với thứ tự thăm $p=(v_1,\dots,v_{n-1})$ xuất phát từ $T$:
$C(p)=d_{Tv_1}+d_{v_1v_2}+\dots+d_{v_{n-1}T}.$ Vì $n$ nhỏ, ta xét mọi thứ tự thăm và lấy giá trị nhỏ nhất.
Bước 3 — Lộ trình tối ưu.
Chu trình ngắn nhất T $\to$ A $\to$ D $\to$ C $\to$ B $\to$ T có chi phí
$d_{TA} + d_{AD} + d_{DC} + d_{CB} + d_{BT} = 10 + 6 + 8 + 2 + 5 = 31$ km.
Kết luận: tổng quãng đường nhỏ nhất $= 31$ km.
68% trả lời đúng
157 đúng · 73 sai