Mini project 2 - tuyến giao hàng BFS, DFS, Dijkstra

Giới thiệu

Bài này tổng kết chặng đồ thị bằng mạng giao hàng. Bạn dùng nó để so BFS, DFS, Dijkstra và A*.

Kiến thức cần nhớ

Mạng giao hàng

• Đỉnh là kho, điểm trung chuyển và khách hàng.
• Cạnh là đoạn đường có trọng số thời gian.
• Cần ít nhất 15 đỉnh và 25 cạnh mẫu.
• Mọi trọng số không âm để Dijkstra và A* đúng.

BFS và DFS

• BFS lan theo lớp bằng hàng đợi, cho đường ít chặng nhất.
• DFS đi sâu bằng đệ quy, phát hiện cụm và đỉnh cô lập.
• Cả 2 phơi bày cấu trúc mạng trước khi tối ưu.
• Ví dụ đời thường: BFS như loang nước, DFS như chui 1 ngõ tới cùng.

Dijkstra và A*

• Dijkstra dùng heap, rút đỉnh rẻ nhất, nới lỏng cạnh.
• A* cộng thêm heuristic đường chim bay từ tọa độ.
• Cả 2 cho cùng tổng thời gian tối ưu.
• A* thường thăm ít đỉnh hơn nhờ đoán hướng tốt.

Đo và báo cáo

• Mỗi lần chạy ghi độ dài tuyến, số đỉnh thăm, thời gian.
• Lắp thành ma trận 4 thuật toán nhân 3 truy vấn.
• Mọi kết luận phải trỏ về 1 ô cụ thể trong ma trận.
• Khuyến nghị theo SLA: cần nhanh thì A*, cần chuẩn thì Dijkstra.

Ví dụ

• Input: khách nối trực tiếp kho 1 cạnh. Output: mọi thuật toán trả tuyến 1 cạnh.
• Giải thích: đường ngắn nhất hiển nhiên, sai là lỗi dựng đồ thị.
• Input: Dijkstra và A* cùng cặp kho khách. Output: tổng thời gian bằng nhau tuyệt đối.
• Giải thích: cả 2 đều tối ưu nên không thể lệch.

💻 Bài tập

Ngôn ngữ: C++ (hoặc Python). Dùng lại BFS, DFS, Dijkstra, A* các ngày 40-43. Nộp vào day-080-mini-project/. Dành 90 phút.

Bài 1: Dữ liệu mạng giao hàng

Tạo network.txt:

# nodes: id tên loại x y       (loại: KHO, TRUNG_CHUYEN, KHACH)
# edges: u v phút              (vô hướng, phút > 0)

• Ít nhất 15 đỉnh (2 kho, 4 trung chuyển, 9+ khách) và 25 cạnh.
• Tọa độ tính bằng km. Tốc độ tối đa 60 km/h nên phút >= khoảng_cách_km: heuristic A* chấp nhận được.
• Có 1 khách bị cô lập để kiểm tra xử lý lỗi.

Viết loadNetwork(path) và kiểm tra dữ liệu: cạnh trỏ tới đỉnh không có, trọng số âm, trùng id đều báo lỗi rõ dòng nào.

Bài 2: Bốn thuật toán, ba truy vấn

Với 3 truy vấn (kho, khách), chạy BFS (ít chặng), DFS (một đường bất kỳ), Dijkstra, A*. Ghi:

truy_vấn      thuật_toán   số_chặng   tổng_phút   đỉnh_đã_thăm   thời_gian(µs)
K1 -> C7      BFS          ...
K1 -> C7      DFS          ...
K1 -> C7      Dijkstra     ...
K1 -> C7      A*           ...

Kiểm tra: Dijkstra và A* luôn cùng tổng_phút. Truy vấn tới khách cô lập trả "không có đường".

DFS còn dùng để liệt kê thành phần liên thông và in đỉnh cô lập.

Bài 3: Báo cáo và mở rộng (nâng cao)

1. REPORT.md: bảng Bài 2, mỗi kết luận trỏ về 1 ô cụ thể. Khuyến nghị thuật toán cho 2 SLA: "phản hồi dưới 1 ms" và "luôn tối ưu thời gian".
2. Sinh mạng 10.000 đỉnh ngẫu nhiên theo tọa độ. Chạy lại 100 truy vấn. So số đỉnh thăm trung bình của Dijkstra và A*.
3. Tìm kho gần nhất cho mọi khách bằng một lần Dijkstra đa nguồn (mọi kho có dist = 0).

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

• loadNetwork bắt được 3 loại lỗi dữ liệu.
• Bảng 12 dòng đủ 3 truy vấn x 4 thuật toán.
• Dijkstra và A* cùng kết quả trên 100 truy vấn ngẫu nhiên.
• REPORT.md có khuyến nghị theo SLA gắn với số liệu.

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

• Mạng giao hàng gồm những đỉnh và cạnh nào?
• BFS và Dijkstra khác nhau ở điểm nào?
• A* hơn Dijkstra ở chỗ nào?
• Khi nào dùng BFS thay vì Dijkstra?

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