Lesson 52 — Capstone: Pathfinding Visualizer CAPSTONE
Sản phẩm gắn kết toàn lộ trình. Vẽ tường, đặt start/goal, chọn thuật toán
(BFS / Dijkstra / Greedy / A*) và heuristic, rồi xem từng ô được duyệt sáng lên — thấy rõ
cái nào tối ưu, cái nào nhanh, cái nào tham lam mà sai. Ba module:
(1) grid tương tác, (2) so sánh 4 thuật toán cạnh nhau,
(3) demo heuristic.
1. Visualizer tương tác
Mẹo: chọn chế độ rồi click/kéo trên lưới. Mặc định kéo để vẽ/xóa tường; chọn start/goal rồi click ô để đặt lại.
Start
Goal
Tường
Đã duyệt
Frontier (đang xét)
Đường đi cuối
Ô đã duyệt
—
work
Độ dài đường
—
số bước
Tối ưu?
—
so với BFS
Trạng thái
Sẵn sàng
2. So sánh 4 thuật toán trên cùng một map
Cùng một bản đồ, 4 thuật toán chạy độc lập. Để ý: BFS & Dijkstra & A* cho cùng độ dài (đều tối ưu, cạnh = 1) nhưng A* duyệt ít ô nhất. Greedy duyệt ít nhưng đường có thể dài hơn.
BFS
—
Dijkstra
—
Greedy
—
A*
—
| Thuật toán | Ô duyệt | Độ dài | Tối ưu? |
|---|---|---|---|
| BFS | — | — | — |
| Dijkstra | — | — | — |
| Greedy | — | — | — |
| A* | — | — | — |
3. Heuristic demo — Manhattan vs Euclidean
Cùng A* trên map trống, đổi heuristic. Heuristic càng sát chi phí thực (Manhattan cho 4 hướng) thì duyệt ít ô hơn. Euclidean ước lượng thấp hơn → kém định hướng → duyệt nhiều hơn. Cả hai vẫn cho cùng độ dài tối ưu.
A* + Manhattan
—
A* + Euclidean
—