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 cần xét tất cả các lộ trình có thể đi qua 4 kho hàng $A, B, C, D$ và quay lại $A$, mỗi kho đúng một lần. Các lộ trình có thể là:
  • $A → B → C → D → A$: $4 + 6 + 7 + 11 = 28$
  • $A → B → D → C → A$: $4 + 5 + 7 + 8 = 24$
  • $A → C → B → D → A$: $8 + 6 + 5 + 11 = 30$
  • $A → C → D → B → A$: $8 + 7 + 5 + 4 = 24$
  • $A → D → B → C → A$: $11 + 5 + 6 + 8 = 30$
  • $A → D → C → B → A$: $11 + 7 + 6 + 4 = 28$
Tuy nhiên, do tính đối xứng của đồ thị, ta chỉ cần xét một nửa số lộ trình, ví dụ:
  • $A → B → C → D → A$: $4 + 6 + 7 + 11 = 28$
  • $A → B → D → C → A$: $4 + 5 + 7 + 8 = 24$
  • $A → C → B → D → A$: $8 + 6 + 5 + 11 = 30$
Ta cũng cần xét các lộ trình ngược lại của chúng, nhưng tổng độ dài không thay đổi. So sánh các kết quả, quãng đường ngắn nhất là 24 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