JavaScript is required

Câu hỏi:

Một công ty vận tải cần giao hàng đến tất cả các thành phố \(A\), \(B\), \(C\), \(D\), \(E\) (hình vẽ). Chi phí di chuyển giữa các thành phố được mô tả trên hình (tính theo đơn vị nghìn đồng). Xe giao hàng của công ty xuất phát từ thành phố \(A\) đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố \(A\). Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)?

Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)? (ảnh 1)

Trả lời:

Đáp án đúng:


Đây là bài toán tìm chu trình Hamilton có trọng số nhỏ nhất.
Ta có thể liệt kê các hành trình có thể đi và tính tổng chi phí của từng hành trình:
  • $A-B-C-D-E-A$: $4+3+4+5+9 = 25$
  • $A-B-C-E-D-A$: $4+3+3+5+8 = 23$
  • $A-B-D-C-E-A$: $4+2+4+3+9 = 22$
  • $A-B-D-E-C-A$: $4+2+5+3+6 = 20$
  • $A-B-E-C-D-A$: $4+7+3+4+8 = 26$
  • $A-B-E-D-C-A$: $4+7+5+4+6 = 26$
Nhận thấy chi phí nhỏ nhất là 23.

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