Toán lớp 11: 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

Mục tiêu bài học

• Giải thích và vận dụng đồ thị có trọng số trong một tình huống mới.
• Giải thích và vận dụng chi phí đường đi trong một tình huống mới.
• Giải thích và vận dụng đường đi ngắn nhất trong một tình huống mới.
• Giải thích và vận dụng kiểm tra tính tối ưu trong một tình huống mới.

Kiến thức cần nhớ

• đồ thị có trọng số: Mỗi cạnh mang một giá trị như độ dài, thời gian hoặc chi phí.
• chi phí đường đi: Chi phí đường đi là tổng trọng số các cạnh được đi qua.
• đường đi ngắn nhất: Đường đi ngắn nhất có tổng trọng số nhỏ nhất trong các đường hợp lệ.
• kiểm tra tính tối ưu: Cần xác nhận không còn phương án hợp lệ có chi phí thấp hơn.

Khởi động và dự đoán

• Quan sát tình huống, dự đoán đại lượng bất biến rồi ghi lại lý do.

Thuật ngữ và kí hiệu

đồ thị có trọng số chi phí đường đi đường đi ngắn nhất kiểm tra tính tối ưu

Công thức, điều kiện và ý nghĩa

Biểu thức	Điều kiện	Ý nghĩa
Mỗi cạnh mang một giá trị như độ dài, thời gian hoặc chi phí.	Ghi rõ ý nghĩa và đơn vị trọng số.	Lập đồ thị trọng số từ bảng khoảng cách.
Chi phí đường đi là tổng trọng số các cạnh được đi qua.	Cộng đúng cạnh thuộc đường, giữ đơn vị.	So sánh chi phí ba tuyến hợp lệ.
Đường đi ngắn nhất có tổng trọng số nhỏ nhất trong các đường hợp lệ.	So tổng chi phí, không so hình vẽ.	Tìm tuyến ngắn nhất trên một mạng nhỏ và chứng minh.
Cần xác nhận không còn phương án hợp lệ có chi phí thấp hơn.	Liệt kê/đánh dấu các phương án cạnh tranh.	Trình bày bảng so sánh để bảo vệ kết luận tối ưu.

Tự kiểm tra kiến thức nền

• Đọc đúng kí hiệu, đơn vị và dữ kiện đã cho.
• Phân biệt định nghĩa với tính chất suy ra.
• Nêu điều kiện trước khi thay số hoặc kết luận.
• Tự kiểm tra bằng một cách biểu diễn khác khi có thể.

Khung lập luận và chứng minh

• Ghi giả thiết và kết luận bằng kí hiệu rõ ràng.
• Chọn định nghĩa/tính chất đúng và nêu điều kiện áp dụng.
• Tách từng bước suy luận, không suy từ hình vẽ không tỉ lệ.
• Kiểm tra kết quả bằng dữ kiện độc lập hoặc trường hợp biên.

Trường hợp biên cần nhớ

• Đường ít cạnh nhất chưa chắc có tổng trọng số nhỏ nhất.
• Chỉ kết luận tối ưu sau khi so đủ phương án hợp lệ/phương pháp đã học.

Phản ví dụ chống học máy móc

• Phản ví dụ/biên cần kiểm: Đường ít cạnh nhất chưa chắc có tổng trọng số nhỏ nhất.
• Phản ví dụ/biên cần kiểm: Chỉ kết luận tối ưu sau khi so đủ phương án hợp lệ/phương pháp đã học.

Ứng dụng và mô hình thực tế

• Lập đồ thị trọng số từ bảng khoảng cách.
• So sánh chi phí ba tuyến hợp lệ.
• Tìm tuyến ngắn nhất trên một mạng nhỏ và chứng minh.
• Trình bày bảng so sánh để bảo vệ kết luận tối ưu.

Minh họa trực quan

Đồ thị trọng số để so tuyến

Cộng trọng số đúng các cạnh trên từng tuyến; không đếm số cạnh thay cho chi phí.

Ví dụ giải từng bước

Ví dụ 1 — đồ thị có trọng số

Đường gồm cạnh trọng số 3 và 5 có tổng trọng số bao nhiêu?

1. 1 Dữ kiện cần dùng: Mỗi cạnh mang một giá trị như độ dài, thời gian hoặc chi phí.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới 8.
3. 3 Kết luận: 8. Tự kiểm: Ghi rõ ý nghĩa và đơn vị trọng số.

Đáp án: 8

Tự kiểm: Ghi rõ ý nghĩa và đơn vị trọng số.

Ví dụ 2 — chi phí đường đi

Đường có trọng số 2, 4, 1 có chi phí bao nhiêu?

1. 1 Dữ kiện cần dùng: Chi phí đường đi là tổng trọng số các cạnh được đi qua.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới 7.
3. 3 Kết luận: 7. Tự kiểm: Cộng đúng cạnh thuộc đường, giữ đơn vị.

Đáp án: 7

Tự kiểm: Cộng đúng cạnh thuộc đường, giữ đơn vị.

Ví dụ 3 — đường đi ngắn nhất

Hai tuyến có tổng 12 và 10; tuyến tối ưu có tổng nào?

1. 1 Dữ kiện cần dùng: Đường đi ngắn nhất có tổng trọng số nhỏ nhất trong các đường hợp lệ.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới 10.
3. 3 Kết luận: 10. Tự kiểm: So tổng chi phí, không so hình vẽ.

Đáp án: 10

Tự kiểm: So tổng chi phí, không so hình vẽ.

Ví dụ 4 — kiểm tra tính tối ưu

Một đường chi phí 9 có tối ưu nếu còn đường chi phí 8 không?

1. 1 Dữ kiện cần dùng: Cần xác nhận không còn phương án hợp lệ có chi phí thấp hơn.
2. 2 Thực hiện phép tính hoặc đối chiếu đúng quy ước; kết quả trung gian dẫn tới không.
3. 3 Kết luận: không. Tự kiểm: Liệt kê/đánh dấu các phương án cạnh tranh.

Đáp án: không

Tự kiểm: Liệt kê/đánh dấu các phương án cạnh tranh.

Lỗi sai thường gặp

• Sai: Trọng số là số đỉnh. Cách sửa: Ghi rõ ý nghĩa và đơn vị trọng số.
• Sai: Mọi cạnh phải cùng trọng số. Cách sửa: Ghi rõ ý nghĩa và đơn vị trọng số.
• Sai: Không cần đơn vị. Cách sửa: Ghi rõ ý nghĩa và đơn vị trọng số.
• Sai: Là số cạnh. Cách sửa: Cộng đúng cạnh thuộc đường, giữ đơn vị.
• Sai: Là trọng số lớn nhất. Cách sửa: Cộng đúng cạnh thuộc đường, giữ đơn vị.
• Sai: Là tổng bậc các đỉnh. Cách sửa: Cộng đúng cạnh thuộc đường, giữ đơn vị.
• Sai: Luôn ít cạnh nhất. Cách sửa: So tổng chi phí, không so hình vẽ.
• Sai: Luôn đi qua đỉnh bậc lớn. Cách sửa: So tổng chi phí, không so hình vẽ.