JavaScript is required

Câu hỏi:

Công ty giao hàng nhanh có 4 kho hàng . Quản lý muốn lên kế hoạch cho xe giao hàng đi qua tất cả các kho hàng để lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần. Khoảng cách giữa các kho hàng (đơn vị: kilômét) được mô tả trong hình bên.

Quãng đường ngắn nhất để xe giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là bao nhiêu kilômét?

Trả lời:

Đáp án đúng:


Để tìm quãng đường ngắn nhất, ta xét các lộ trình có thể đi qua tất cả các kho hàng và quay về điểm xuất phát, mỗi kho chỉ ghé một lần.
  • $A → B → C → D → A$: $5 + 10 + 5 + 20 = 40$ km
  • $A → B → D → C → A$: $5 + 8 + 5 + 15 = 33$ km
  • $A → C → B → D → A$: $15 + 10 + 8 + 20 = 53$ km
  • $A → C → D → B → A$: $15 + 5 + 8 + 5 = 33$ km
  • $A → D → B → C → A$: $20 + 8 + 10 + 15 = 53$ km
  • $A → D → C → B → A$: $20 + 5 + 10 + 5 = 40$ km
Lưu ý, các lộ trình ngược lại có cùng tổng khoảng cách. So sánh các kết quả, ta thấy quãng đường ngắn nhất là 33 km. Tuy nhiên, 33 không có trong đáp án. Xem xét lại các lộ trình: Ta thấy có một vài lộ trình có thể bị bỏ sót. Tuy nhiên, kiểm tra kĩ lại hình vẽ, ta thấy lộ trình ngắn nhất là lộ trình $A->B->C->D->A$ hoặc $A->D->C->B->A$, có độ dài là 40 km.

Câu hỏi này thuộc đề thi trắc nghiệm dưới đây, bấm vào Bắt đầu thi để làm toàn bài

Câu hỏi liên quan