Một nhân viên giao hàng xuất phát từ kho tổng ở vị trí D, cần đi qua 4 điểm giao hàng tại E, F, G, H (mỗi nơi đúng một lần) để giao thực phẩm sạch, sau đó quay trở về kho D. Sơ đồ dưới đấy ch
26/40
Một nhân viên giao hàng xuất phát từ kho tổng ở vị trí D, cần đi qua 4 điểm giao hàng tại E, F, G, H (mỗi nơi đúng một lần) để giao thực phẩm sạch, sau đó quay trở về kho D. Sơ đồ dưới đấy cho biết khoảng cách di chuyển giữa các địa điểm (đơn vị: km).
Tổng quãng đường ngắn nhất mà nhân viên đó phải di chuyển để hoàn thành lộ trình là bao nhiêu km?
\(20\).
\(25\).
\(35\).
\(30\).
Giải thích
Áp dụng thuật toán láng giềng gần nhất, ta sẽ ưu tiên cho nhân viên đi đến địa điểm gần nhất và chưa được đi đến trước đó.
\( \Rightarrow \) Quãng đường đi của nhân viên giao hàng là: \(D \to H \to G \to E \to F \to D\).
\( \Rightarrow \) Khoảng cách ngắn nhất để nhân viên giao hàng thực hiện điều đó là: 35 km. Chọn C.