Điểm mình sẽ làm rõ trong bài này là: A* không chỉ tìm đường, nó ưu tiên những ô “có triển vọng” hơn nhờ heuristic. Và demo sẽ được tách làm 2 giai đoạn cho trực quan:
- Giai đoạn 1 (Search): A* mở rộng dần các ô (open/closed) cho tới khi chạm Goal.
- Giai đoạn 2 (Commit): khi đã tìm ra đường đi cuối cùng, hiện path và agent chạy thẳng tới Goal (không replay quá trình search).
1. A* là gì?
A* là thuật toán tìm đường dựa trên một hàm điểm:
g(n): chi phí từ Start đến noden(với grid thì thường là số bước).h(n): heuristic — ước lượng từnđến Goal còn bao xa.f(n) = g(n) + h(n): tổng điểm để ưu tiên node nào được xử lý trước.
A* luôn chọn node trong open set có f nhỏ nhất để mở rộng tiếp. Khi heuristic “đàng hoàng” (admissible), A* vẫn đảm bảo tìm đường ngắn nhất như BFS nhưng thường nhanh hơn rất nhiều.
2. Heuristic phổ biến cho mê cung dạng lưới
Với lưới đi 4 hướng (trên/dưới/trái/phải), heuristic phổ biến và hiệu quả là Manhattan distance:
h(n) = |x_n - x_goal| + |y_n - y_goal|Manhattan hợp vì mỗi bước đi chỉ thay đổi 1 tọa độ (x hoặc y) một đơn vị. Nói nôm na: “còn bao nhiêu phố nữa tới nhà” 😈
3. Trực quan hóa A*: Open set, Closed set
Để nhìn A* “nghĩ” như thế nào, demo sẽ tô màu:
- Closed set (đã xử lý): đỏ nhạt
- Open set (đang chờ xử lý): trắng mờ
- Goal: sao vàng
- Agent: 1 chấm trắng duy nhất
- Final path: đường trắng sau khi tìm xong
4. Demo A* Maze Solver
A* Maze Solver Demo
5. Kết luận
A* là “phiên bản khôn hơn” của BFS: vẫn tìm đường ngắn nhất (với heuristic phù hợp), nhưng thường thăm ít ô hơn vì biết ưu tiên những hướng tiến gần Goal. Ở bài tiếp theo, mình sẽ chơi thêm các biến thể:
- Weighted A* (tăng tốc bằng cách “tham” hơn)
- Dijkstra và địa hình có trọng số (bùn/đường nhựa)
- Bidirectional A* (đi từ 2 đầu gặp nhau)
Bình luận