SA (chu trình Hamilton / TSP): xuất phát từ một điểm gốc, th...

Lớp 11 · Chỉnh hợp, tổ hợp

Một hướng dẫn viên du lịch khởi hành từ khách sạn, dự định đưa khách tham quan bốn địa điểm nổi tiếng. Độ dài quãng đường (đơn vị: kilômét) giữa các địa điểm như sau: khách sạn – địa điểm I: $3$; khách sạn – địa điểm II: $7$; khách sạn – địa điểm IV: $5$; địa điểm I – địa điểm II: $4$; địa điểm I – địa điểm III: $6$; địa điểm II – địa điểm III: $2$; địa điểm II – địa điểm IV: $8$; địa điểm III – địa điểm IV: $4$. Người đó xuất phát từ khách sạn và phải đi thăm cả bốn địa điểm còn lại, mỗi địa điểm chỉ đến đúng một lần, rồi quay trở về khách sạn. Tổng độ dài quãng đường đi nhỏ nhất thỏa mãn điều kiện trên là bao nhiêu kilômét?

ĐÁP ÁN

1 8

LỜI GIẢI

Bước 1 — Mô hình hoá thành chu trình Hamilton.
Coi mỗi địa điểm là một đỉnh của đồ thị, độ dài đường nối là trọng số cạnh. Hành trình cần tìm là một CHU TRÌNH đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần, bắt đầu và kết thúc tại khách sạn.

Bước 2 — Đếm số hành trình cần xét.
Do điểm đầu và điểm cuối đều cố định là khách sạn, mỗi hành trình ứng với một cách sắp thứ tự thăm bốn đỉnh còn lại. Số hành trình $= 4! = 24$ (hữu hạn nên có thể duyệt hết).

Bước 3 — Tìm tổng trọng số nhỏ nhất.
So sánh tổng độ dài của các hành trình hợp lệ, hành trình ngắn nhất là
$KS → I → II → III → IV → KS$ với tổng $= 3 + 4 + 2 + 4 + 5 = 18$ kilômét.

Kết luận: quãng đường ngắn nhất là $18$ kilômét. Đáp số: $18$.

*Lỗi thường gặp:* chọn cạnh nhỏ nhất ở mỗi bước (tham lam) dễ dẫn đến đường cụt hoặc bỏ sót đỉnh, không cho tổng nhỏ nhất.

59% trả lời đúng 486 đúng · 333 sai

SA (chu trình Hamilton / TSP): xuất phát từ một điểm gốc, thăm bốn đỉnh