Thuật toán A* (A-star) là gì? Giải thích dễ hiểu kèm demo tìm đường trên lưới

Trong bài viết này, chúng ta sẽ:

• Hiểu A* giải bài toán gì.
• Nắm được ý tưởng gốc: g(n), h(n), f(n).
• Xem demo trực quan A* tìm đường trên lưới bằng JavaScript.

A* là gì?

A* là thuật toán tìm đường đi ngắn nhất từ một điểm xuất phát đến một điểm đích trong đồ thị, thường là trên lưới 2D hoặc bản đồ. A* sử dụng hai loại chi phí cho mỗi ô (hoặc mỗi đỉnh):

• g(n): Chi phí thực tế từ điểm bắt đầu đến ô hiện tại n.
• h(n): Hàm ước lượng (heuristic) chi phí từ n đến đích.

Thuật toán sẽ ưu tiên mở rộng những ô có giá trị:

f(n) = g(n) + h(n)

Ô nào có f(n) nhỏ hơn sẽ được xét trước. Nhờ vậy, A* không “mò mẫm” vô hướng như BFS, cũng không duyệt quá rộng như Dijkstra, mà đi khá thẳng hướng về phía đích.

Heuristic trong A*: chọn thế nào?

Heuristic h(n) là phần làm nên sức mạnh của A*. Một heuristic tốt giúp:

• Tăng tốc quá trình tìm kiếm.
• Giảm số ô phải duyệt.
• Vẫn đảm bảo tìm được đường đi tối ưu nếu heuristic được chọn “chuẩn”.

Trên lưới 2D với di chuyển 4 hướng (lên, xuống, trái, phải), một heuristic rất thường dùng là:

h(n) = |x_n – x_goal| + |y_n – y_goal|

Đây là khoảng cách Manhattan, phù hợp cho di chuyển “theo ô” như trong mê cung hoặc trò chơi trên lưới.

Mô hình demo: tìm đường trên lưới có chướng ngại vật

Để trực quan, ta dùng một lưới vuông nhỏ với:

• Một ô bắt đầu (Start).
• Một ô đích (Goal).
• Một số ô tường (không đi qua được).

Thuật toán A* sẽ:

1. Bắt đầu từ Start, đưa vào tập open set.
2. Mỗi bước chọn ô trong open set có f(n) nhỏ nhất để mở rộng.
3. Chuyển ô đó sang closed set (đã xét xong).
4. Cập nhật các ô hàng xóm (gần kề) của nó.
5. Dừng lại khi gặp Goal hoặc không còn đường đi.

Demo thuật toán A* bằng JavaScript

Demo dưới đây minh họa việc A* tìm đường trên một lưới nhỏ:

• Ô xanh lá: điểm bắt đầu.
• Ô đỏ: đích.
• Ô xám: tường.
• Ô xanh nhạt: các ô đang nằm trong open set.
• Ô vàng: các ô đã duyệt (closed set).
• Ô xám đậm: đường đi ngắn nhất tìm được.

Giải thích ngắn gọn đoạn code A*

1. Gán giá trị g, h, f cho từng ô

node.g = chi phí từ Start đến node
node.h = heuristic đến Goal (Manhattan)
node.f = node.g + node.h

Khi bắt đầu, chỉ ô Start có g = 0, các ô khác được set là Infinity.

2. Open set và closed set

openSet = [startNode]; // các ô đang chờ xử lý
closed = true;         // ô đã xử lý xong

Mỗi bước, thuật toán chọn ô trong open set có f nhỏ nhất để mở rộng. Ô đó sau đó chuyển sang trạng thái closed.

3. Cập nhật hàng xóm (neighbor)

Với mỗi hàng xóm có thể đi tới, thuật toán:

• Tính tentativeG = current.g + 1 (một bước di chuyển trên lưới).
• Nếu tentativeG tốt hơn g hiện tại của neighbor thì cập nhật lại g, h, f, parent.
• Nếu neighbor chưa từng nằm trong open set thì đưa vào.

4. Dựng lại đường đi

Khi tới đích, ta lần ngược từ Goal về Start thông qua thuộc tính parent của từng node, rồi tô đậm đường đi đó trên lưới.

Khi nào nên dùng A*?

• Khi cần tìm đường đi ngắn nhất trên lưới hoặc bản đồ.
• Khi có thể định nghĩa một heuristic hợp lý (ví dụ Manhattan, Euclid).
• Khi muốn tốc độ nhanh hơn so với Dijkstra trên những bài toán có cấu trúc rõ ràng.
• Trong game, robot, mô phỏng đường đi, hệ thống điều hướng.

Kết luận

A* là một trong những thuật toán quan trọng nhất trong nhóm tìm đường đi ngắn nhất, đặc biệt là khi làm việc với lưới 2D, bản đồ hoặc game. Bằng cách kết hợp chi phí thực tế và heuristic, A* vừa đảm bảo tính tối ưu, vừa tăng tốc đáng kể so với việc duyệt rộng “mù mờ”.

Với demo JavaScript ở trên, bạn có thể quan sát trực tiếp cách A* mở rộng các ô, lựa chọn hướng đi và dựng lại đường đi cuối cùng.

Từ đây, bạn có thể áp dụng A* cho các bài toán lớn hơn, tùy biến heuristic hoặc kết hợp với các cấu trúc dữ liệu như priority queue để tối ưu hiệu năng.