Thuật toán A (A-star) là một thuật toán tìm kiếm đường đi tối ưu trên đồ thị, dựa trên thuật toán tìm kiếm theo chiều rộng (BFS) và đặc biệt phù hợp cho các bài toán tìm kiếm đường đi ngắn nhất và tối ưu. Thuật toán A sử dụng hàm đánh giá f(n), quyết định thứ tự duyệt các nút trong đồ thị, với n là một nút của đồ thị. Hàm f(n) được tính như sau:
f(n) = g(n) + h(n)
Trong đó:
- g(n): là chi phí từ nút nguồn đến nút hiện tại n.
- h(n): là hàm ước lượng khoảng cách từ nút hiện tại n đến nút đích (đây là hàm heuristic). Hàm heuristic được chọn sao cho h(n) ít nhất là chi phí để đi từ nút hiện tại đến nút đích, không quá chặt chẽ nhưng cũng không quá lỏng lẻo.
Thuật toán A* tiến hành duyệt đồ thị theo các bước sau:
- Khởi tạo: đặt nút nguồn vào một danh sách mở (một cấu trúc dữ liệu ưu tiên hàng đợi) và đánh dấu nút nguồn như đã xem xét.
- Lặp lại đến khi danh sách mở trống hoặc tìm được đường đi:
a. Lấy nút n có f(n) nhỏ nhất ra khỏi danh sách mở và đặt là nút hiện tại.
b. Nếu nút hiện tại là nút đích, thuật toán kết thúc và đường đi được xây dựng từ nút nguồn đến nút đích thông qua việc theo dõi những nút đã xét.
c. Ngược lại, đối với mỗi nút kề của nút hiện tại, kiểm tra xem nếu chưa xét hoặc đã xét nhưng g(n) nhỏ hơn giá trị đã xét trước đó, cập nhật lại g(n), h(n) và f(n), và đưa nút này vào danh sách mở nếu chưa từng xét.
- Nếu không tìm được đường đi từ nút nguồn đến nút đích, đưa ra kết luận là không tồn tại đường đi.
Thuật toán A đảm bảo tìm được đường đi tối ưu nếu hàm heuristic h(n) không surestimate (dự đoán quá cao) khoảng cách đến nút đích. A cũng có hiệu suất tốt hơn so với thuật toán BFS và UCS khi sử dụng hàm heuristic phù hợp.