CĐ2 - Bài 10: Bài toán tìm đường đi tối ưu

I. Đồ thị có trọng số

📌 Định nghĩa Đồ thị có trọng số

Một đồ thị mà mỗi cạnh $e$ của nó được gán cho một số thực $w(e) \ge 0$ được gọi là đồ thị có trọng số. $w(e)$ gọi là trọng số (hoặc độ dài, chi phí) của cạnh $e$.

• Trọng số của đường đi: Tổng trọng số của tất cả các cạnh tạo nên đường đi đó.

II. Thuật toán Dijkstra

⚡ Thuật toán Dijkstra tìm đường đi ngắn nhất

Thuật toán gán cho mỗi đỉnh $v$ một nhãn $L(v)$ là độ dài tạm thời của đường đi ngắn nhất từ xuất phát $S$ đến $v$.

Khởi tạo: $L(S) = 0$, nhãn các đỉnh khác $L(v) = \infty$. Đánh dấu $S$ chưa cố định.
Bước lặp: Chọn đỉnh $u$ chưa cố định có $L(u)$ nhỏ nhất. Cố định nhãn cho $u$.
Cập nhật: Với mỗi đỉnh $v$ chưa cố định kề với $u$, cập nhật: $$L(v) = \min\{L(v), L(u) + w(u, v)\}$$
Lặp lại cho đến khi cố định được đỉnh đích $T$.

III. Bài toán người du lịch (TSP)

📌 Bài toán người du lịch

Cho $n$ thành phố với chi phí đi lại giữa các cặp thành phố. Một người du lịch xuất phát từ một thành phố, muốn ghé qua tất cả $n-1$ thành phố còn lại đúng một lần rồi quay về thành phố xuất phát sao cho tổng chi phí là nhỏ nhất.

Đây chính là bài toán tìm chu trình Hamilton có tổng trọng số nhỏ nhất.

🔷 Dạng 1: Tính trọng số của đường đi

📌 Phương pháp giải

Cộng tất cả trọng số các cạnh trên dãy đường đi $v_0 \to v_1 \to \dots \to v_k$.

🔍 Ví dụ 1

Cho đồ thị với các cạnh có trọng số: $w(AB) = 4, w(BC) = 3, w(CD) = 5, w(DA) = 2, w(AC) = 6$. Tính trọng số đường đi $A \to B \to C \to D$.

💡 Xem lời giải

• Trọng số $= w(AB) + w(BC) + w(CD) = 4 + 3 + 5 = 12$.

🔍 Ví dụ 2

So sánh độ dài hai đường đi từ $A$ đến $D$: Đường đi 1 ($A \to B \to C \to D$) trọng số 12 và Đường đi 2 ($A \to C \to D$) với $w(AC) = 6, w(CD) = 5$.

💡 Xem lời giải

• Đường đi 2 có trọng số $= w(AC) + w(CD) = 6 + 5 = 11$.

• Đường đi 2 ngắn hơn đường đi 1 ($11 < 12$).

📝 Thực hành — Dạng 1

✏️ Bài tập 1.1

Tính độ dài chu trình $A \to B \to C \to A$ với $w(AB)=5, w(BC)=7, w(CA)=4$.

💡 Xem lời giải

$5 + 7 + 4 = 16$.

✏️ Bài tập 1.2

Nếu tất cả các cạnh trong đồ thị đều có trọng số bằng 1 thì bài toán đường đi ngắn nhất trở thành bài toán gì?

💡 Xem lời giải

Trở thành bài toán tìm đường đi có ít cạnh nhất (khoảng cách đồ thị).

🔷 Dạng 2: Thuật toán Dijkstra tìm đường đi ngắn nhất

📌 Các bước thực hiện bảng Dijkstra

Lập bảng gồm các cột tương ứng với các đỉnh, mỗi dòng ghi nhãn $L(v)$ và đỉnh trước đó. Cố định đỉnh có nhãn nhỏ nhất sau mỗi vòng lặp.

🔍 Ví dụ 1

Tìm đường đi ngắn nhất từ $A$ đến $D$ trong đồ thị có trọng số: $w(AB)=2, w(AC)=4, w(BC)=1, w(BD)=7, w(CD)=3$.

💡 Xem lời giải

• Khởi tạo $L(A) = 0$; $L(B) = 2, L(C) = 4, L(D) = \infty$.

• Cố định $B$ ($L(B) = 2$). Cập nhật qua $B$: $L(C) = \min(4, 2+1) = 3$; $L(D) = \min(\infty, 2+7) = 9$.

• Cố định $C$ ($L(C) = 3$). Cập nhật qua $C$: $L(D) = \min(9, 3+3) = 6$.

• Đường đi ngắn nhất là $A \to B \to C \to D$ với độ dài bằng $6$.

🔍 Ví dụ 2

So sánh đường đi trực tiếp $A \to D$ ($w(AD) = 8$) với đường đi thu được ở Ví dụ 1.

💡 Xem lời giải

Đường đi qua $B$ và $C$ có độ dài 6 ngắn hơn đường đi trực tiếp có độ dài 8 ($6 < 8$).

📝 Thực hành — Dạng 2

✏️ Bài tập 2.1

Tìm đường đi ngắn nhất từ $S$ đến $T$ biết $w(SA)=1, w(ST)=10, w(AT)=4$.

💡 Xem lời giải

$S \to A \to T$ có độ dài $1 + 4 = 5 < 10$.

✏️ Bài tập 2.2

Thuật toán Dijkstra dừng lại khi nào?

💡 Xem lời giải

Khi đỉnh đích $T$ được cố định nhãn, hoặc tất cả các đỉnh còn lại có nhãn bằng $\infty$.

🔷 Dạng 3: Bài toán người du lịch (TSP)

📌 Phương pháp giải cho n nhỏ

Liệt kê tất cả các chu trình Hamilton trong đồ thị.
Tính tổng trọng số của từng chu trình.
Chọn chu trình có tổng trọng số nhỏ nhất.

🔍 Ví dụ 1

Cho 3 thành phố $A, B, C$ với chi phí giữa các cặp: $w(AB) = 10, w(BC) = 15, w(CA) = 20$. Tìm hành trình người du lịch từ $A$ đi qua $B, C$ rồi về $A$ có chi phí nhỏ nhất.

💡 Xem lời giải

• Các chu trình Hamilton xuất phát từ $A$: $A \to B \to C \to A$ và $A \to C \to B \to A$.

• Tổng chi phí cả 2 hành trình $= 10 + 15 + 20 = 45$.

🔍 Ví dụ 2

Với $n = 4$ thành phố ($A, B, C, D$), đồ thị đầy đủ $K_4$ có bao nhiêu chu trình Hamilton xuất phát từ $A$ (không phân biệt chiều đi)?

💡 Xem lời giải

Số chu trình Hamilton $= \dfrac{(n-1)!}{2} = \dfrac{3!}{2} = 3$ chu trình.

📝 Thực hành — Dạng 3

✏️ Bài tập 3.1

Với $n = 5$ thành phố, có bao nhiêu chu trình Hamilton phân biệt?

💡 Xem lời giải

$\dfrac{(5-1)!}{2} = \dfrac{24}{2} = 12$ chu trình.

✏️ Bài tập 3.2

Bài toán TSP có phải là một bài toán tối ưu tổ hợp kinh điển không?

💡 Xem lời giải

Có, đây là bài toán NP-khó nổi tiếng trong toán học và tin học.

🔷 Dạng 4: Ứng dụng thực tế mạng lưới giao thông & chi phí

📌 Mô hình hóa bài toán giao thông

Các nút giao thông là các đỉnh, thời gian/chi phí/khoảng cách di chuyển là trọng số các cạnh.

🔍 Ví dụ 1

Một xe giao hàng cần đi từ kho $K$ tới khách hàng $H$. Có 2 tuyến đường: Tuyến 1 qua tuyến đường tránh (dài 15 km, vận tốc 60 km/h); Tuyến 2 qua trung tâm (dài 8 km nhưng tắc đường, vận tốc trung bình 20 km/h). Chọn tuyến đường tốn ít thời gian nhất.

💡 Xem lời giải

• Thời gian Tuyến 1: $t_1 = \dfrac{15}{60} = 0.25 \text{ giờ} = 15$ phút.

• Thời gian Tuyến 2: $t_2 = \dfrac{8}{20} = 0.4 \text{ giờ} = 24$ phút.

• Chọn **Tuyến 1** (đường tránh) tốn ít thời gian hơn (15 phút < 24 phút).

🔍 Ví dụ 2

Trong ứng dụng bản đồ (như Google Maps), thuật toán nào được áp dụng phổ biến để tìm đường đi ngắn nhất giữa hai điểm?

💡 Xem lời giải

Thuật toán Dijkstra và các biến thể nâng cao như $A^*$ (A-star).

📝 Thực hành — Dạng 4

✏️ Bài tập 4.1

Khi nào đường đi ngắn nhất giữa hai điểm trên đồ thị không phải là đường thẳng nối 2 điểm đó?

💡 Xem lời giải

Khi giữa hai điểm có vật cản hoặc không có tuyến đường trực tiếp trong mạng lưới giao thông.

✏️ Bài tập 4.2

Trọng số của một cạnh có thể đại diện cho những đại lượng thực tế nào?

💡 Xem lời giải

Khoảng cách (km), thời gian di chuyển (phút), chi phí cước phí (đồng), dung lượng băng thông (Mbps)...

📝 Bài tập tự luận — Tổng hợp

📝 Bài tập tự luận tổng hợp Tìm đường đi tối ưu (10 bài)

Bài 1. Đồ thị có trọng số là gì?

💡 Xem lời giải

Mỗi cạnh được gán 1 số thực không âm $w(e) \ge 0$.

Bài 2. Nêu mục tiêu của Thuật toán Dijkstra.

💡 Xem lời giải

Tìm đường đi ngắn nhất từ 1 đỉnh xuất phát đến các đỉnh còn lại.

Bài 3. Yêu cầu quan trọng đối với trọng số cạnh trong thuật toán Dijkstra?

💡 Xem lời giải

Trọng số phải không âm ($w(e) \ge 0$).

Bài 4. Bài toán người du lịch (TSP) phát biểu như thế nào?

💡 Xem lời giải

Tìm chu trình Hamilton có tổng chi phí (trọng số) nhỏ nhất.

Bài 5. Có bao nhiêu chu trình Hamilton khác nhau trong đồ thị đầy đủ $K_4$?

💡 Xem lời giải

$\dfrac{(4-1)!}{2} = 3$ chu trình.

Bài 6. Tính độ dài đường đi qua 3 cạnh có trọng số lần lượt là $2, 5, 8$.

💡 Xem lời giải

$2 + 5 + 8 = 15$.

Bài 7. Trong thuật toán Dijkstra, nhãn khởi tạo của đỉnh nguồn $S$ bằng bao nhiêu?

💡 Xem lời giải

Bằng 0 ($L(S) = 0$).

Bài 8. Nhãn khởi tạo của các đỉnh còn lại ngoài $S$ trong Dijkstra là bao nhiêu?

💡 Xem lời giải

Bằng vô cực ($\infty$).

Bài 9. Thuật toán Dijkstra có áp dụng được cho đồ thị có trọng số âm không?

💡 Xem lời giải

Không (phải dùng thuật toán Bellman-Ford).

Bài 10. Nếu 2 đỉnh $A$ và $B$ không có đường đi nối với nhau thì khoảng cách giữa chúng bằng bao nhiêu?

💡 Xem lời giải

Bằng vô cực ($\infty$).

🎯 Bài tập trắc nghiệm tự luyện

Làm các câu hỏi sau để củng cố toàn bộ kiến thức về Bài toán tìm đường đi tối ưu. Hệ thống sẽ hiển thị kết quả và lời giải chi tiết ngay khi bạn trả lời.

Câu 1:Thuật toán Dijkstra nổi tiếng dùng để giải quyết bài toán nào trên đồ thị có trọng số không âm?

Câu 2:Trọng số của một đường đi trong đồ thị có trọng số được tính bằng:

Câu 3:Bài toán Người du lịch (Traveling Salesperson Problem - TSP) yêu cầu tìm:

Câu 4:Trong thuật toán Dijkstra, điều kiện quan trọng đối với trọng số của các cạnh là:

Câu 5:Đường đi từ $A$ đến $B$ đi qua các đỉnh $A \to C \to B$ có trọng số các cạnh tương ứng là $w(AC) = 3, w(CB) = 5$. Tổng độ dài đường đi này bằng:

🎯

Ngân hàng câu hỏi trắc nghiệm Bài toán tìm đường đi tối ưu

Hàng trăm câu hỏi ngẫu nhiên từ ngân hàng đề — kiểm tra và tự đánh giá năng lực ngay!

🚀 Làm bài trắc nghiệm →

Miễn phí · Mở trong tab mới