khoahoc.vietjack.com
Giảm 50% Kích hoạt VIP
khoahoc.vietjack.com
Kích hoạt VIP Đăng nhập
Tạo VIP
  2. Lớp 11
  3. Toán

Câu hỏi:

12/07/2024 7,909 Lưu

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.

Xem lời giải

Câu hỏi trong đề: Chuyên đề Toán 11 Cánh diều Chuyên đề 2. Làm quen với một vài yếu tố của lí thuyết đồ thị có đáp án !!

Flashcard Bắt Đầu Thi Giao bài

Quảng cáo

Trả lời:

verified Giải bởi Vietjack
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. (ảnh 1)

Dễ thấy đồ thị Hình 24 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 = 3 km;

Từ B, đỉnh chưa đến gần nhất là C, BC = 5 km;

Từ C, đỉnh chưa đến gần nhất là D, CD = 5 km;

Từ D, đỉnh chưa đến gần nhất là E, DE = 9 km;

Từ E, đỉnh chưa đến gần nhất là F, EF = 6 km;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, FA = 4 km.

Tổng quãng đường theo chu trình ABCDEFA là: 3 + 5 + 5 + 9 + 6 + 4 = 32 (km).

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ều dài (km)

A

ABCDEFA

32

B

BAFEDCB

32

C

CBAFEDC

32

C

CDEFABC

32

D

DCBAFED

32

E

EFABCDE

32

F

FABCDEF

32

 

Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.

Đang tải chế độ Học...

Hot: 1000+ đề thi giữa kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay

ĐẶC QUYỀN VIP

Đăng ký VIP để học và luyện thi không giới hạn

Trọn bộ quyền lợi trên Vietjack, trong một tài khoản.

  • Phòng luyện thi cấp tốc: ĐGNL - ĐGTD, Tốt nghiệp THPT, Ôn vào 10, Ôn vào 6, Ôn Giữa kì/Cuối kì
  • Hơn 200K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 3tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem hàng ngàn bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện
  • Đăng ký ngay
Avatar

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Người giao hàng xuất phát từ một địa điểm nào đó, đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Hãy tìm một đường đi thỏa mãn điều kiện trên cho người giao hàng sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất.

Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Người giao hàng xuất phát từ một địa điểm nào đó, đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Hãy tìm một đường đi thỏa mãn điều kiện trên cho người giao hàng sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất. (ảnh 1)

Lời giải

Để tìm quãng đường đi ngắn nhất trên đồ thị có trọng số, ta áp dụng thuật toán láng giềng gần nhất để tìm tất cả các chu trình xuất phát từ một đỉnh ban đầu, đi qua các đỉnh khác và trở về đỉnh ban đầu sao cho tổng độ dài các cạnh của chu trình đó là ngắn nhất. Sau đó, ta so sánh độ dài của tất cả các chu trình “tốt nhất” vừa tìm được để tìm ra chu trình có tổng độ dài các cạnh là ngắn nhất. Việc giải cụ thể Hoạt động 2 trang 46, ta cùng xem chi tiết ở Luyện tập 2 trang 46.

Câu 2

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.

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. (ảnh 1)

Lời giải

Từ viện bảo tàng, thời gian di chuyển đến trường A là ngắn nhất: 19 phút.

Từ trường A, thời gian di chuyển đến trường B là ngắn nhất: 38 phút.

Từ trường B, thời gian di chuyển đến trường C là ngắn nhất: 32 phút.

Đến đây, không còn địa điểm nào chưa đi qua nên quay lại viện bảo tàng với thời gian di chuyển: 51 phút.

Do đó, chu trình xuất phát từ viện bảo tàng, qua trường A, trường B, trường C rồi quay lại viện bảo tàng có thời gian đi là ít nhất và thời gian đi là: 19 + 38 + 32 + 51 = 140 (phút).

Câu 3

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ó 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. (ảnh 1)

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 4

Giả 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?

Giả 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? (ảnh 1)

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 5

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).

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). (ảnh 1)

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 6

Hãy cho ví dụ về đồ thị có trọng số.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem thêm các câu hỏi khác »

Đăng ký

Bằng cách đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của VietJack.

Bạn đã có tài khoản?

Khóa học 1 - 12
THPT
THCS
Phòng luyện đề
ĐGNL - ĐGTD
Tốt nghiệp THPT
Ôn vào 10
Ôn vào 6
Tài liệu
THPT
THCS
Tin Tuyển Sinh
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
Giấy chứng nhận ĐKKD số: 0108307822 do Sở KH & ĐT TP Hà Nội cấp lần đầu ngày 04/06/2018
© 2017 Vietjack37. All Rights Reserved.
zalo Nhắn tin Zalo Hỏi bài tập