Một nhân viên giao hàng xuất phát từ kho K đi giao hàng cho 4 khách hàng ở 4 địa chỉ A, B, C, D.

Câu hỏi số 970128:

Vận dụng

Một nhân viên giao hàng xuất phát từ kho K đi giao hàng cho 4 khách hàng ở 4 địa chỉ A, B, C, D. Yêu cầu bắt buộc là phải ghé qua mỗi địa chỉ 1 lần, sau đó về kho để kết thúc. Thời gian di chuyển cho trong đồ thị. Thời gian tối thiểu để hoàn thành là

A. 75 phút.

B. 78 phút.

C. 80 phút.

D. 72 phút.

Đáp án đúng là: A

Quảng cáo

Xem lời giải

Câu hỏi:970128

Phương pháp giải

Liệt kê các chu trình Hamilton có thể có (đi qua 4 đỉnh và quay về điểm xuất phát). Tính tổng thời gian từng chu trình và chọn giá trị nhỏ nhất.

Giải chi tiết

Yêu cầu của bài toán là tìm một chu trình xuất phát từ đỉnh K, đi qua các đỉnh A, B, C, D mỗi đỉnh đúng một lần rồi quay trở lại K (chu trình Hamilton) sao cho tổng độ dài các cạnh là nhỏ nhất.

Từ K đến C, B, A, D thì KB nhỏ nhất nên chọn đến B (tổng thời gian bằng 15)

Từ B đến $A\left( {15 + 10 = 25} \right)$, $C\left( {15 + 25 = 40} \right)$, $D\left( {15 + 70 = 85} \right)$ nên chọn đi tiếp đến A (tổng thời gian bằng 25)

Từ A đến $D\left( {25 + 12 = 37} \right)$ hoặc $C\left( {25 + 32 = 57} \right)$ nên ta chọn đến D (tổng thời gian bằng 37)

Từ D đến C rồi về K ta có tổng thời gian là $37 + 8 + 30 = 75$ phút

Đáp án cần chọn là: A

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.