Những Hiểu Lầm Phổ Biến Về Thuật Toán A*

Có lẽ do thời sinh viên tôi từng đăng một bài viết trên mạng kèm theo đoạn mã nguồn minh họa cách áp dụng thuật toán A* để tìm đường, nên suốt 7 năm qua tôi liên tục nhận được email từ độc giả trao đổi về chủ đề này. Đúng vậy, không hề phóng đại đâu - đoạn code đơn giản đến mức sơ sài ấy sau khi tôi đăng tải đã lan truyền khắp các ngõ ngách của không gian mạng tiếng Trung. Đến nỗi mỗi lần nhìn lại đoạn code ấy, tôi vừa tiếc nuối vừa muốn gỡ bỏ hoàn toàn nhưng đã quá muộn màng.

Điều khiến tôi trăn trở nhất là tại sao một kiến thức thuật toán cơ bản được giảng dạy trên lớp lại bị hiểu sai bởi nhiều người đến vậy? Phải chăng các lập trình viên làm game đều không thèm mở sách giáo khoa ra đọc?

A*, đọc là “A sao” (A-Star), thực chất chỉ là một thuật toán tìm kiếm theo nguyên tắc heuristic. Nói cách khác, trong không gian nghiệm hữu hạn có thể liệt kê được, đây là phương pháp sử dụng hàm đánh giá thông minh để tìm ra nghiệm tối ưu. Cần hiểu rõ rằng A* không phải là thuật toán tìm đường, mà chỉ là công cụ chúng ta mượn để giải quyết bài toán tìm đường. Cũng giống như việc dùng bốn phép tính cơ bản để giải toán, A* là một công cụ nền tảng. Trong bài viết của tôi, phương pháp chia bản đồ thành các ô vuông, đánh dấu số thứ tự từ điểm xuất phát đến khi chạm đích để truy ngược đường đi ngắn nhất thực chất là một thuật toán tìm kiếm theo chiều rộng (BFS) cổ điển. Quá trình đánh dấu từng lớp ô xung quanh tương ứng với việc duyệt đồ thị theo từng mức độ sâu, và con số trên mỗi ô chính là khoảng cách ngắn nhất tính từ điểm bắt đầu.

Khi kết hợp hàm heuristic vào quá trình tìm kiếm này, chúng ta có được lớp thuật toán tìm kiếm có định hướng, trong đó A* là một thành viên tiêu biểu. Dấu sao (*) trong tên gọi phản ánh một ràng buộc đặc biệt: hàm heuristic phải đảm bảo không vượt quá giá trị thực tế (admissible), nhờ đó mới đảm bảo tìm được đường đi tối ưu tuyệt đối. Nếu bỏ qua ràng buộc này, ta sẽ có phiên bản cơ bản hơn gọi là thuật toán A.

Điều quan trọng cần nhận thức rõ là việc chia bản đồ thành ô vuông, gán trọng số cho đường đi giữa các ô (có thể bằng nhau hoặc khác nhau tùy địa hình), hay thiết lập đường một chiều… đều thuộc về cách mô hình hóa bài toán, chứ không phải bản chất của thuật toán A*. Ngay cả khi bạn sáng tạo phương pháp chia vùng bản đồ bất quy tắc hay biểu diễn dưới dạng vector, vẫn hoàn toàn có thể áp dụng A* như một công cụ hỗ trợ tìm nghiệm tối ưu. Còn các kỹ thuật mô phỏng hành vi con người như “luôn rẽ phải khi gặp ngã ba” hay “quay lại khi đụng tường” thì thuộc về cải tiến của phương pháp duyệt đồ thị truyền thống, chứ không liên quan gì đến bản chất A*.

Về mặt lý thuyết, A* đảm bảo tìm được nghiệm tối ưu nếu tồn tại, nhưng nhược điểm lớn nhất của nó là tiêu tốn bộ nhớ. Khi không gian trạng thái quá rộng, ta thường kết hợp với các kỹ thuật đánh đổi thời gian lấy không gian như IDA* (A* lặp sâu dần). Trong trường hợp đặc biệt khi không tồn tại đường đi khả dĩ (ví dụ bản đồ bị chia cắt), A* sẽ rơi vào tình trạng duyệt toàn bộ không gian, đây là lý do vì sao các game thương mại thường áp dụng thêm cơ chế kiểm tra kết nối bản đồ trước khi kích hoạt thuật toán.

P/s: Nếu sử dụng phương pháp waypoint (điểm mốc) để giải bài toán tìm đường, bản chất là bạn đang biểu diễn bản đồ dưới dạng đồ thị, lúc này thuật toán Dijkstra cổ điển sẽ là lựa chọn phù hợp. Trong các hệ thống sử dụng đa giác lồi để mô tả vật cản, có thể tham khảo bài toán ACM kinh điển từ 10 năm trước mang tên “Cắt góc” (Cutting Corners).