Tổng quan
A* Search là công cụ chủ lực của tìm đường trên lưới. Nó kết hợp đường đi ngắn nhất được đảm bảo của Dijkstra với một heuristic ước lượng khoảng cách còn lại tới đích, nên khám phá ít ô hơn nhiều nhờ đi đại thể đúng hướng.
Với mỗi nút, nó xếp hạng các ứng viên theo f = g + h, trong đó g là chi phí thực từ điểm xuất phát và h là chi phí ước lượng tới đích, giúp tập trung tìm kiếm vào các ô hứa hẹn nhất.
Tìm kiếm A* hoạt động thế nào?
- Bắt đầu với nút nguồn; g của nó bằng 0 và f bằng heuristic h tới đích.
- Từ hàng đợi ưu tiên, mở rộng nút đang mở có f = g + h nhỏ nhất.
- Với mỗi hàng xóm, tính g thử; nếu nó cải thiện chi phí của hàng xóm thì cập nhật g, f và nút cha.
- Lặp lại đến khi đích được mở rộng, rồi dựng lại đường đi qua các liên kết cha.
Khi nào nên dùng?
- Tìm đường thời gian thực trong game và robot trên lưới có trọng số.
- Định tuyến GPS và bản đồ, khi heuristic khoảng cách cắt tỉa mạnh không gian tìm kiếm.
- Mọi bài toán đường đi ngắn nhất một đích khi có sẵn ước lượng khoảng cách rẻ và chấp nhận được.
Phân tích độ phức tạp
Chi phí của A* phụ thuộc rất nhiều vào heuristic. Trong trường hợp xấu nhất nó là O((V + E) log V) như Dijkstra, nhưng một heuristic chấp nhận được và tốt (ví dụ khoảng cách Manhattan trên lưới) sẽ cắt tỉa phần lớn biên tìm kiếm. Nếu heuristic không bao giờ ước lượng vượt quá khoảng cách thực, A* đảm bảo trả về đường đi ngắn nhất.
Câu hỏi thường gặp
Điều gì khiến một heuristic 'chấp nhận được', và vì sao nó quan trọng?
Một heuristic chấp nhận được không bao giờ ước lượng vượt quá chi phí còn lại thực sự. Chính bảo đảm đó giữ cho A* tối ưu; nếu heuristic ước lượng quá cao, A* chạy nhanh hơn nhưng có thể trả về đường không phải ngắn nhất.
A* tốt hơn Dijkstra ở điểm nào?
Dijkstra mở rộng mù ra mọi hướng; A* dùng heuristic để thiên hướng mở rộng về phía đích, nên thường thăm ít nút hơn hẳn mà vẫn trả về cùng một đường đi ngắn nhất.