Tiêu đề CHUYÊN ĐỀ 30. ĐƯỜNG ĐI NGẮN NHẤT – BÀI TOÁN TỐI ƯU (17 câu TLN).docx ✅

Câu 8: Trong một trò chơi có sa bàn được thiết kế như hình: Trong đó các điểm là các trạm, các đoạn nối giữa hai điểm là con đường đi lại giữa hai vị trí. Con số gắn liền trên mỗi đoạn là số thuế khi một người đi qua con đường đó phải đóng. Một người đang đứng ở vị trí điểm H, đang cần đến vị trí điểm A. Tìm đường đi để tổng số thuế người đó chi trả nhỏ nhất. Số thuế chi trả khi đó bằng bao nhiêu? Câu 9: 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. Câu 10: Một người đưa thư xuất phát từ bưu điện ở vị trí A, các điểm cần phát thư nằm dọc các con dường cần đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu? Câu 11: Gia đình nhà bạn Kha dự định kì nghỉ hè tới, bố bạn Kha sẽ đưa gia đình đi du lịch tại các thành phố du lịch A, B, C bằng xe ô tô điện của gia đình. Trên các tuyến đường đi từ nhà bạn Kha đến các thành phố du lịch A, B, C và từ thành phố du lịch này đến thành phố du lịch kia đều có một trạm thu phí đường bộ. Sơ đồ các tuyến đường đi và mức phí đường bộ (tính bằng
đơn vị ngàn đồng) đối với loại ôtô điện như nhà bạn Kha tại mỗi trạm thu phí được cho như trên hình vẽ. Gia đình bạn Kha nên đi đến các thành phố du lịch theo lịch trình có tổng số tiền phải nộp cho các trạm thu phí thấp nhất là bao nhiêu ngàn đồng. Biết rằng lịch trình đi không bắt buộc phải đến địa điểm nào trước, địa điểm nào sau. Câu 12: Một trò chơi điện tử được thiết kế như sau: Có 4 điểm X , Y , Z , W với số lượng thử thách trên đường đi giữa các cặp điểm được mô tả trong hình bên dưới. Người chơi bắt đầu từ một điểm nào đó, đi qua tất cả các điểm còn lại một lần duy nhất và quay về điểm xuất phát. Mỗi khi đi qua một điểm, điểm đó sẽ bị phá hủy và không thể quay lại. Tổng số thử thách trên các đường đi để hoàn thành hành trình là bao nhiêu, với điều kiện số thử thách này phải nhỏ nhất. Y X Z W 7 15 9 10 12 8