Bạn An xuất phát từ thư viện $T$, cần đến thăm các trường $A, B, C$ (mỗi nơi đúng một lần) rồi quay về $T$. Khoảng cách (km): TA=7, TB=8, TC=3, AB=5, AC=3, BC=6. Nếu đi theo lộ trình T $\to$ A $\to$ B $\to$ C $\to$ T thì tổng quãng đường là $21$ 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
2
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} = 7 + 5 + 6 + 3 = 21$ 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} = 8 + 5 + 3 + 3 = 19$ km.
Kết luận: số km tiết kiệm $= 21 - 19 = 2$ km.
64% trả lời đúng
474 đúng · 266 sai