App: tuyến giao hàng so sánh BFS, Dijkstra, A*

Giới thiệu

Bài này xây app tìm đường giao hàng. So 3 thuật toán xem ai nhanh mà đường vẫn ngắn.

Kiến thức cần nhớ

3 thuật toán tìm đường

• BFS đi theo lớp, đúng khi mọi bước tốn bằng nhau.
• Dijkstra luôn mở nút rẻ nhất nên đúng với trọng số không âm.
• A* cộng thêm heuristic ước lượng về đích nên thăm ít nút hơn.
• Ví dụ đời thường: BFS đi mò, Dijkstra cân giá xăng, A* có la bàn.

Heuristic phải admissible

• Admissible nghĩa là không bao giờ ước lượng cao hơn thật.
• Manhattan trên lưới trống là admissible nên vẫn tối ưu.
• Phóng đại heuristic gấp đôi sẽ cho đường dài hơn tối ưu.
• Chọn sai heuristic thì A* có thể tệ hơn Dijkstra.

Đa điểm và trực quan

• Đa điểm dùng tham lam: đi điểm gần nhất tiếp theo.
• Tô vùng đã thăm mỗi thuật toán 1 màu để so.
• Đầu cuối nằm trong chướng ngại phải báo lỗi rõ.
• Mọi bản đồ lưu file để benchmark tái lập.

Ví dụ

• Input: lưới không trọng số, 20 cặp ngẫu nhiên. Output: BFS và Dijkstra cho cùng độ dài.
• Giải thích: cạnh bằng nhau nên BFS đã tối ưu.
• Input: đồ thị trọng số, 20 cặp. Output: A* cùng chi phí Dijkstra nhưng thăm ít hơn 30%.
• Giải thích: heuristic hướng thẳng về đích nên bớt đi lạc.

💻 Bài tập

Ngôn ngữ: Python 3 với pygame hoặc matplotlib (hoặc C++ với SFML). Dùng code ngày 40, 42, 43. Nộp vào day-134-routes/.

Bài 1: Bản đồ lưới và 3 thuật toán

Bản đồ đọc từ file text: . đường, # tường, ~ bùn (chi phí 5), S kho, 1..9 điểm giao.

def bfs(grid, s, t) -> Result: ...        # bỏ qua chi phí bùn
def dijkstra(grid, s, t) -> Result: ...
def astar(grid, s, t, h, weight=1.0) -> Result: ...   # f = g + weight * h
# Result: path, cost, visited (tập ô đã mở), time_ms

Bản đồ không bùn -> 3 thuật toán cùng cost
Bản đồ có bùn    -> BFS đi xuyên bùn (cost cao hơn), Dijkstra và A* vòng qua
S hoặc đích nằm trong tường -> báo lỗi rõ ràng

Bài 2: Trực quan hóa

1. Vẽ bản đồ, tô ô đã mở của mỗi thuật toán một màu, vẽ đường đi.
2. Xuất 3 ảnh (hoặc 1 GIF quá trình mở ô).
3. A* với weight = 1, 1.5, 2, 5: bảng số ô mở và cost. Chỉ ra từ weight nào đường không còn tối ưu.

Bài 3: Giao nhiều điểm (nâng cao)

1. Kho S giao cho 9 điểm rồi quay về. Tính ma trận khoảng cách giữa 10 điểm bằng 10 lần Dijkstra.
2. Thứ tự giao: tham lam gần nhất, tham lam + 2-opt, Held-Karp (ngày 78, 10 điểm vẫn chạy được).
3. Vẽ tuyến cuối cùng trên bản đồ. In tổng chi phí 3 cách.
4. Thêm khung giờ: điểm 3 phải giao trước điểm 7. Sửa Held-Karp để tôn trọng ràng buộc.

✅ Tiêu chí hoàn thành

• Test 3 kịch bản bản đồ pass.
• Có ảnh so sánh vùng mở và bảng weight A*.
• Bảng 3 cách xếp thứ tự giao có số thật.
• Ràng buộc thứ tự được tôn trọng (có test).

❓ Câu hỏi ôn tập

• BFS đúng trong trường hợp nào?
• Dijkstra dùng heap để làm gì?
• Heuristic admissible nghĩa là gì?
• Khi nào không nên dùng A*?

🌕 Bạn đã hoàn thành ngày 134. Làm hết bài tập phía trên rồi sang ngày tiếp theo.