Đề bài

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?

Đáp án:

Đáp án

Đáp án:

Phương pháp giải

Liệt kê và so sánh.

Xe giao hàng có thể xuất phát từ một trong 4 kho hàng A, B, C, D.
Giả sử xe giao hàng xuất phát từ kho A.
Để đi qua tất cả các kho hàng và quay trở về A , xe giao hàng có thể đi theo một trong các đường đi:

Nếu xuất phát từ đỉnh khác thì chỉ là phép thay thế bước đi trong sơ đồ trên.
Vậy 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à 15 km.

Mở rộng

Một số phương pháp tìm đường đi ngắn nhất.

1. Thuật toán Láng giềng gần nhất.

Trước hết, cần chứng minh đồ thị có chu trình Hamilton. Sau đó, tiếp tục thực hiện các bước sau:

+ Chọn một đỉnh bắt đầu, ta gọi là đỉnh V.

+ 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.

+ 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.

+ Quay lại đỉnh V.

2. Thuật toán Dijkstra

Bước 1: Gán khoảng cách từ đỉnh nguồn đến chính nó là 0, và đến tất cả các đỉnh khác là vô cùng.

Bước 2: Gọi đỉnh chưa xét với giá trị đánh dấu nhỏ nhất là C.

Bước 3: Với mỗi đỉnh kề (N) với đỉnh hiện tại C và chưa được xét, tính toán khoảng cách mới từ nguồn qua C đến N (bằng khoảng cách của C cộng với trọng số cạnh nối C và N).... Nếu khoảng cách mới này nhỏ hơn khoảng cách hiện đang gán cho đỉnh N, hãy cập nhật lại khoảng cách của N bằng giá trị nhỏ hơn đó.

Bước 4: Đánh dấu đỉnh C là đã xét xong.