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)?
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:
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$
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

Trọn Bộ Giáo Án Word & PowerPoint Tiếng Anh 12 – I-Learn Smart World – Năm Học 2025-2026

Trọn Bộ Giáo Án Word & PowerPoint Tiếng Anh 12 – Global Success – Năm Học 2025-2026

Trọn Bộ Giáo Án Word & PowerPoint Hóa Học 12 – Kết Nối Tri Thức – Năm Học 2025-2026

Trọn Bộ Giáo Án Word & PowerPoint Hóa Học 12 – Chân Trời Sáng Tạo – Năm Học 2025-2026

Trọn Bộ Giáo Án Word & PowerPoint Công Nghệ 12 – Kết Nối Tri Thức – Năm Học 2025-2026
