Một nhân viên giao hàng xuất phát từ kho trung chuyển $T$, cần đến thăm các điểm giao $A, B, C, D$ (mỗi nơi đúng một lần) rồi quay về $T$. Khoảng cách (km) giữa các địa điểm: TA=4, TB=6, TC=8, TD=8, AB=10, AC=10, AD=11, BC=3, BD=8, CD=3. Tính tổng quãng đường nhỏ nhất (km) của hành trình khép kín.
ĐÁP ÁN
2
7
LỜI GIẢI
Bước 1 — Mô hình hoá.
Hành trình khép kín qua tất cả địa điểm là một CHU TRÌNH bắt đầu và kết thúc tại $T$, đi qua mỗi đỉnh còn lại đúng một lần. Chi phí của chu trình theo thứ tự thăm $p=(v_1,\dots,v_{n-1})$ là
$C(p)=d_{Tv_1}+d_{v_1v_2}+\dots+d_{v_{n-2}v_{n-1}}+d_{v_{n-1}T}.$
Bước 2 — Duyệt các thứ tự thăm.
Cố định điểm xuất phát $T$, cần xét mọi thứ tự thăm của $4$ đỉnh còn lại ($A,\dots,D$), tức $(5-1)! = 24$ thứ tự (kể cả chiều). Vì $n=5$ nhỏ, ta liệt kê và so sánh chi phí từng chu trình.
Bước 3 — Lộ trình tối ưu.
Chu trình ngắn nhất là T $\to$ A $\to$ D $\to$ C $\to$ B $\to$ T với chi phí
$d_{TA} + d_{AD} + d_{DC} + d_{CB} + d_{BT} = 4 + 11 + 3 + 3 + 6 = 27$ km.
Kết luận: tổng quãng đường nhỏ nhất $= 27$ km.
64% trả lời đúng
146 đúng · 81 sai