Chào mừng các em học sinh đến với bài học số 10 trong chuyên đề 2 của chương trình Toán 11 Kết nối tri thức. Bài học hôm nay sẽ tập trung vào một chủ đề quan trọng trong toán học rời rạc và có ứng dụng thực tế cao: Bài toán tìm đường đi tối ưu.
Chúng ta sẽ cùng nhau khám phá các khái niệm cơ bản về lý thuyết đồ thị, các phương pháp giải quyết bài toán tìm đường đi ngắn nhất, và áp dụng những kiến thức này vào giải các bài tập cụ thể.
Bài toán tìm đường đi tối ưu là một bài toán kinh điển trong lý thuyết đồ thị, có ứng dụng rộng rãi trong nhiều lĩnh vực như giao thông vận tải, mạng máy tính, và logistics. Mục tiêu của bài toán là tìm ra đường đi ngắn nhất (hoặc rẻ nhất, nhanh nhất) giữa hai đỉnh trong một đồ thị.
Trước khi đi sâu vào giải bài toán tìm đường đi tối ưu, chúng ta cần nắm vững một số khái niệm cơ bản về lý thuyết đồ thị:
Có nhiều thuật toán khác nhau để giải bài toán tìm đường đi tối ưu, tùy thuộc vào đặc điểm của đồ thị (có trọng số hay không, có hướng hay không). Một số thuật toán phổ biến bao gồm:
Ví dụ 1: Cho một đồ thị có 5 đỉnh A, B, C, D, E và các cạnh có trọng số như sau:
| Cạnh | Trọng số |
|---|---|
| A-B | 4 |
| A-C | 2 |
| B-C | 5 |
| B-D | 10 |
| C-E | 3 |
| D-E | 7 |
Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh E.
Giải: Sử dụng thuật toán Dijkstra, ta có thể tìm được đường đi ngắn nhất từ A đến E là A -> C -> E với tổng trọng số là 2 + 3 = 5.
Bài tập 1: Cho một bản đồ giao thông với các thành phố là các đỉnh và các con đường là các cạnh. Mỗi cạnh có trọng số là khoảng cách giữa hai thành phố. Hãy tìm đường đi ngắn nhất từ thành phố A đến thành phố B.
Bài toán tìm đường đi tối ưu có rất nhiều ứng dụng thực tế, bao gồm:
Bài toán tìm đường đi tối ưu là một bài toán quan trọng trong lý thuyết đồ thị và có ứng dụng rộng rãi trong nhiều lĩnh vực. Việc nắm vững các khái niệm cơ bản và các thuật toán giải quyết bài toán này sẽ giúp các em học sinh có thêm công cụ để giải quyết các vấn đề thực tế.
