Bác tài taxi xuất phát từ bến xe $T$, cần đến thăm các khách sạn $A, B, C$ (mỗi nơi đúng một lần) rồi quay về $T$. Khoảng cách (km): TA=10, TB=3, TC=4, AB=5, AC=4, BC=8. Nếu đi theo lộ trình T $\to$ A $\to$ B $\to$ C $\to$ T thì tổng quãng đường là $27$ km. Hỏi nếu chọn hành trình khép kín NGẮN NHẤT thì tiết kiệm được bao nhiêu km so với lộ trình trên?
ĐÁP ÁN
1
1
LỜI GIẢI
Bước 1 — Chi phí lộ trình đã cho.
Lộ trình T $\to$ A $\to$ B $\to$ C $\to$ T có chi phí
$d_{TA} + d_{AB} + d_{BC} + d_{CT} = 10 + 5 + 8 + 4 = 27$ km.
Bước 2 — Tìm hành trình ngắn nhất.
Xét mọi thứ tự thăm $p=(v_1,\dots,v_{n-1})$ xuất phát từ $T$, chi phí $C(p)=d_{Tv_1}+\dots+d_{v_{n-1}T}$; 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$ B $\to$ A $\to$ C $\to$ T có chi phí
$d_{TB} + d_{BA} + d_{AC} + d_{CT} = 3 + 5 + 4 + 4 = 16$ km.
Kết luận: số km tiết kiệm $= 27 - 16 = 11$ km.
70% trả lời đúng
396 đúng · 171 sai