Giải bài 4 trang 49 Chuyên đề học tập Toán 11 Cánh diềuSử 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 34Tổng hợ🐭p đề thi học kì 2 lớp 11 tất cả các 𓃲môn - Cánh diều Toán - Văn - Anh - Lí - Hóa - SinhQuảng cáo
Đề bài 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). Phương pháp giải - Xem chi tiết Bước 1. Chọn một đỉnh bắt đầu, ta gọi là đỉnh V. Bước 2. Xuất phát từ đỉnh hiện hành, chọn cạnh có độ dài nhỏ nhất🌱 nối đến một trong các đỉnh cꦯhưa đến. Đánh dấu đỉnh cuối của cạnh vừa chọn. Bước 3. Xuất phát từ đỉnh vừa ꦅđánh dấu, nếu còn đỉnh chưa đến thì quay ꦡlại bước 2. Bước 4. Quay lại đỉnh V. Lời giải chi tiết Dễ thấy đồ thị Hình 34 có chu trình Hamilton. Ta thấy chu trình xuất phát từ đỉnh A là AEDBCA thỏa mãn đề bài với t🍒ổng quãng đường nhỏ nhất là AE + ED + DB + BC + CA = 🌠5 + 5 + 3 + 5 + 3 = 21 (km). Các chu trình xuất phát từ đỉnh B, C, D, E có 1 đỉn𓆏h được đi qua hai lần nên không thỏa mãn quy tắc của thuật toán láng giềng gần nhất nên loại.
Quảng cáo
Tham Gia Group Dành Cho Lớp 11 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí |