Bài 10. Bài toán tìm đường đi tối ưu trong một vài trường hợp đơn giản

Bài 10: Bài toán tìm đường đi tối ưu - Toán 11 Kết Nối Tri Thức

Bài toán tìm đường đi tối ưu là một trong những bài toán cơ bản và quan trọng trong lý thuyết đồ thị. Bài toán này có nhiều ứng dụng thực tế trong các lĩnh vực như giao thông vận tải, mạng máy tính, và lập kế hoạch.

1. Giới thiệu về lý thuyết đồ thị

Lý thuyết đồ thị là một nhánh của toán học rời rạc, nghiên cứu về các đồ thị. Đồ thị là một cấu trúc dữ liệu bao gồm các đỉnh (nodes) và các cạnh (edges) nối giữa các đỉnh. Các đỉnh biểu diễn các đối tượng, và các cạnh biểu diễn mối quan hệ giữa các đối tượng.

2. Các khái niệm cơ bản

• Đỉnh (Node): Một đối tượng trong đồ thị.
• Cạnh (Edge): Một kết nối giữa hai đỉnh.
• Đường đi (Path): Một dãy các đỉnh liên tiếp nhau bằng các cạnh.
• Chu trình (Cycle): Một đường đi bắt đầu và kết thúc tại cùng một đỉnh.
• Đường đi tối ưu (Optimal Path): Đường đi có chi phí (ví dụ: độ dài, thời gian, giá tiền) nhỏ nhất hoặc lớn nhất.

3. Bài toán tìm đường đi tối ưu

Bài toán tìm đường đi tối ưu là tìm đường đi giữa hai đỉnh cho trước sao cho chi phí của đường đi là nhỏ nhất hoặc lớn nhất. Có nhiều thuật toán khác nhau để giải bài toán này, tùy thuộc vào loại đồ thị và tiêu chí tối ưu.

4. Các thuật toán tìm đường đi tối ưu phổ biến

• Thuật toán Dijkstra: Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm.
• Thuật toán Bellman-Ford: Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số âm hoặc không âm.
• Thuật toán A*: Tìm đường đi ngắn nhất từ một đỉnh nguồn đến một đỉnh đích bằng cách sử dụng hàm heuristic để ước lượng chi phí còn lại.

5. Ví dụ minh họa

Xét một đồ thị có các đỉnh A, B, C, D và các cạnh có trọng số như sau:

Tìm đường đi ngắn nhất từ A đến D.

Sử dụng thuật toán Dijkstra, ta có thể tìm được đường đi ngắn nhất từ A đến D là A -> B -> D với chi phí là 5 + 3 = 8.

6. Ứng dụng của bài toán tìm đường đi tối ưu

• Giao thông vận tải: Tìm đường đi ngắn nhất giữa hai địa điểm.
• Mạng máy tính: Tìm đường đi ngắn nhất giữa hai máy tính trong mạng.
• Lập kế hoạch: Tìm kế hoạch tối ưu để hoàn thành một nhiệm vụ.
• Robot học: Tìm đường đi tối ưu cho robot để di chuyển từ điểm A đến điểm B.

7. Bài tập luyện tập

1. Cho một đồ thị có các đỉnh A, B, C, D, E và các cạnh có trọng số như sau: A-B (2), A-C (4), B-C (1), B-D (7), C-E (3), D-E (5). Tìm đường đi ngắn nhất từ A đến E.
2. Một công ty vận tải có các kho hàng tại các thành phố A, B, C, D. Chi phí vận chuyển hàng hóa giữa các thành phố được cho như sau: A-B (10), A-C (15), A-D (20), B-C (35), B-D (25), C-D (30). Tìm đường đi ngắn nhất để vận chuyển hàng hóa từ A đến D.

Hy vọng bài học này đã giúp các em hiểu rõ hơn về bài toán tìm đường đi tối ưu trong lý thuyết đồ thị. Chúc các em học tập tốt!