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 vẽ.Tìm thời gian đi ít nhất để thực hiện chu trình trên.
Đáp án:
Đáp án:
Xét từng địa điểm và con đường mất ít thời gian di chuyển nhất tới địa điểm đó.
Từ viện bảo tàng, thời gian di chuyển đến trường B là ngắn nhất: 19 phút.
Từ trường B, thời gian di chuyển đến trường A là ngắn nhất: 38 phút.
Từ trường A, 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 B, trường A, 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).
Bài toán này có thể được mô hình hóa bằng Lý thuyết đồ thị. Ta cần tìm một chu trình Hamilton (đi qua mỗi đỉnh đúng một lần) trong đồ thị có tổng trọng số (tổng thời gian) nhỏ nhất.
Để giải bài toán, ta sử dụng thuật toán Láng giềng gần nhất.
Trước hết, ta chứng minh đồ thị có chu trình Hamilton. Sau đó, ta tiếp tục thực hiện các bước sau:
+ Chọn một đỉnh bắt đầu, ta gọi là đỉnh V.
+ 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 chưa đến. Đánh dấu đỉnh cuối của cạnh vừa chọn.
+ 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.
+ Quay lại đỉnh V.
Danh sách bình luận