Câu hỏi:
12/07/2024 1,033Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 (đơn vị: nghìn đồng). Ta nên chọn theo chu trình nào đi qua tất cả các địa điểm để tổng chi phí di chuyển là thấp nhất? Chi phí thấp nhất đó bằng bao nhiêu?
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 140k).
Quảng cáo
Trả lời:
Dễ thấy đồ thị Hình 33 có chu trình Hamilton.
+) Sử dụng thuật toán láng giềng gần nhất đối với đỉnh xuất phát A, ta có:
Từ A, đỉnh gần nhất là B, AB = 20 nghìn đồng;
Từ B, đỉnh chưa đến gần nhất là C, BC = 30 nghìn đồng;
Từ C, đỉnh chưa đến gần nhất là D, CD = 12 nghìn đồng;
Đến đây không còn đỉnh chưa đến, vì vậy quay về A, DA = 35 nghìn đồng.
Tổng chi phí di chuyển theo chu trình ABCDA là: 20 + 30 + 12 + 35 = 97 (nghìn đồng).
Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:
|
Đỉnh bắt đầu |
Chu trình |
Tổng chi phí (nghìn đồng) |
|
A |
ABCDA |
97 |
|
B |
BADCB |
97 |
|
C |
CDBAC |
108 |
|
D |
DCBAD |
97 |
Vậy có ba chu trình ABCDA, BADCB, DCBAD thỏa mãn đề bài và chi phí thấp nhất là 97 nghìn đồng.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Có bốn địa điểm với độ dài quãng đường giữa các địa điểm (đơn vị: kilômét) mô tả trong Hình 32. Sử dụng thuật toán láng giềng gần nhất, tìm các chu trình xuất phát từ một đỉnh đi qua tất cả các địa điểm, mỗi địa điểm đúng một lần sao cho tổng độ dài các cạnh của chu trình là nhỏ nhất.
Câu 2:
Sử dụng thuật toán láng giềng gần nhất, hãy giải bài toán người giao hàng đối với đồ thị ở Hình 34, số ghi trên mỗi cạnh của đồ thị mô tả độ dài quãng đường giữa các địa điểm (đơn vị: kilômét).
Câu 4:
Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2.
Câu 5:
Một nhân viên của bảo tàng nghệ thuật đang có kế hoạch giới thiệu nội dung cuộc triển lãm của bảo tàng đến ba trường học trong khu vực. Người đó muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường. Thời gian di chuyển (đơn vị: phút) giữa các trường học và giữa bảo tàng với mỗi trường học được mô tả trong Hình 35.
Tìm chu trình xuất phát từ viện bảo tàng sao cho thời gian đi là ít nhất.
Câu 6:
Hình 31 biểu diễn mạng lưới máy chủ và tốc độ truyền dữ liệu (đơn vị: Megabit/ giây, kí hiệu là Mbps) giữa một số thành phố. Vẽ một đồ thị sử dụng điểm, đường để biểu diễn mạng lưới đó.
về câu hỏi!