Nội dung text CHUYÊN ĐỀ 30. ĐƯỜNG ĐI NGẮN NHẤT – BÀI TOÁN TỐI ƯU (17 câu TLN).pdf
TÀI LIỆU ÔN THI TỐT NGHIỆP THPT Câu 1: Để tạo một mô hình trò chơi gồm 5 trụ A B C D E , , , , với số lượng thử thách đi trên đường giữa các trụ được mô tả như hình dưới. Người chơi xuất phát từ 1 trụ nào đó, đi qua tất cả các trụ còn lại, mỗi khi đi qua 1 trụ thì trụ đó bị phá hủy nhưng người chơi vẫn phải trở về trụ ban đầu. Tổng số thử thách của đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất bằng bao nhiêu? Câu 2: Một bác Shipper giao hàng xuất phát từ kho A để lấy hàng và đi giao tất cả các con đường sau đó lại trở về kho A để trả lại những hàng hóa mà khách hàng chưa nhận. Con đường có sơ đồ và thời gian giao hàng (phút) trên mỗi con đường được mô tả trong hình sau: Thời gian ngắn nhất để bác Shipper hoàn thành công việc trên là bao nhiêu phút? Câu 3: Công ty giao hàng nhanh có 4 kho hàng A B C , , và D . Quản lý muốn lên kế hoạch cho xe giao hàng đi qua tất cả các kho hàng để lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần. Khoảng cách giữa các kho hàng (km) được mô tả trong hình bên. Quãng đường ngắn nhất để xe giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là bao nhiêu? Câu 4: Một trò chơi điện tử quy định như sau: Có 5 trụ A B C D E , , , , với số lượng các thử thách trên đường đi giữa các cặp trụ được mô tả trong hình bên. Người chơi xuất phát từ một trụ nào đó, đi 3 5 7 3 2 4 A C B D CHUYÊN ĐỀ 30: ĐƯỜNG ĐI NGẮN NHẤT – BÀI TOÁN TỐI ƯU DẠNG THỨC 3 TRẮC NGHIỆM TRẢ LỜI NGẮN
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