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.

Thử: chạy cả 4 trên cùng map — BFS/Dijkstra nở đều, Greedy lao thẳng nhưng có thể sai, A* thăm ít node mà vẫn tối ưu.

BFS

—

Dijkstra

—

Greedy

—

A*

—
Thuật toánÔ duyệtĐộ dàiTố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

—