Đề bài
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?
Phương pháp giải - Xem chi tiết
Bước 1. Chọn một đỉnh bắt đầu, ta gọi là đỉnh V.
Bước 2. 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.
Bước 3. 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.
Bước 4. Quay lại đỉnh V.
Lời giải chi tiết
Dễ thấy đồ thị Hình 33 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 = 20 nghìn đồng;
Từ B, đỉnh chưa đến gần nhất là C, BC = 30 nghìn đồng;
Từ C, đỉnh chưa đến gần nhất là D, CD = 12 nghìn đồng;
Đến đây không còn đỉnh chưa đến, vì vậy quay về A, DA = 35 nghìn đồng.
Tổng chi phí di chuyển theo chu trình ABCDA là: 20 + 30 + 12 + 35 = 97 (nghìn đồng).
Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:
Vậy có ba chu trình ABCDA, BADCB, DCBAD thỏa mãn đề bài và chi phí thấp nhất là 97 nghìn đồng.
English
French
Spanish
Russian