Bài tự luận · Bài 27
Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 27
Giả sử 4 thành phố A,B,C,D với khoảng cách (đơn vị: km) giữa các thành phố được cho bởi bảng sau:
A B C D
A 0 10 15 20
B 10 0 25 35
C 15 25 0 30
D 20 35 30 0
Hãy tính quãng đường ngắn nhất để đi qua tất cả các thành phố đúng một lần rồi quay lại thành phố xuất phát?
A B C D
A 0 10 15 20
B 10 0 25 35
C 15 25 0 30
D 20 35 30 0
Hãy tính quãng đường ngắn nhất để đi qua tất cả các thành phố đúng một lần rồi quay lại thành phố xuất phát?
Xem lời giải
Lời giải
Sử dụng thuật toán láng giềng gần ta có:
Từ đỉnh A đỉnh gần nhất là đỉnh B với quãng đường $AB=10(km)$
Từ đỉnh B, đỉnh chưa đến gần nhất là C với quãng đường $BC=25(km)$
Từ đỉnh C, đỉnh chưa đến còn lại là D với quãng đường $CD=30(km)$.
Đến đây, không còn đỉnh nào nữa nên quay lại đỉnh A, với quãng đường: $DA=20(km)$
Tổng số quãng đường đi được theo chu trình $ABCDA$ là: $85(km)$
Tương tự với các đỉnh còn lại, ta có bảng sau
Đỉnh bắt đầu Chu trình Tổng số quãng đường(km)
A ABCDA 85
B BACDB 90
C CABDC 90
D DABCD 85
Vậy có thể chọn chu trình ABCDA hoặc DABCD, với tổng quãng đường ngắn nhất là 85 km.
Đáp số: 85.
Từ đỉnh A đỉnh gần nhất là đỉnh B với quãng đường $AB=10(km)$
Từ đỉnh B, đỉnh chưa đến gần nhất là C với quãng đường $BC=25(km)$
Từ đỉnh C, đỉnh chưa đến còn lại là D với quãng đường $CD=30(km)$.
Đến đây, không còn đỉnh nào nữa nên quay lại đỉnh A, với quãng đường: $DA=20(km)$
Tổng số quãng đường đi được theo chu trình $ABCDA$ là: $85(km)$
Tương tự với các đỉnh còn lại, ta có bảng sau
Đỉnh bắt đầu Chu trình Tổng số quãng đường(km)
A ABCDA 85
B BACDB 90
C CABDC 90
D DABCD 85
Vậy có thể chọn chu trình ABCDA hoặc DABCD, với tổng quãng đường ngắn nhất là 85 km.
Đáp số: 85.