| Tên thuật toán |
A* |
| Phân loại thuật toán |
Thuật toán tìm đường đi ngắn nhất, thuật toán tìm kiếm heuristic |
| Cấu trúc dữ liệu |
Ma trận kề, danh sách kề, hàng đợi ưu tiên |
| Độ phức tạp thời gian (Worst Case) |
O((V + E) log V) với danh sách kề và hàng đợi ưu tiên |
| Độ phức tạp dung lượng |
O(V) với danh sách kề và hàng đợi ưu tiên |
| Độ phức tạp bộ nhớ |
O(V + E) với danh sách kề và hàng đợi ưu tiên |
| Phạm vi sử dụng |
Tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh khác trong đồ thị có trọng số không âm |
| Khả năng xử lý trọng số âm |
Có thể xử lý trọng số âm nếu sử dụng heuristic thích hợp |
| Khả năng xử lý chu trình âm |
Không |
| Phù hợp với đồ thị có hướng |
Có |
| Phù hợp với đồ thị vô hướng |
Có |
| Người phát hiện đầu tiên |
Peter Hart, Nils Nilsson, Bertram Raphael (1968) |
| Ứng dụng ban đầu |
Tìm đường đi ngắn nhất trong các bài toán trí tuệ nhân tạo và trò chơi |
| Ứng dụng hiện đại |
Hệ thống định vị GPS, trò chơi điện tử, robot tự hành, lập kế hoạch tự động, tối ưu hóa |
| Một số ứng dụng và hệ thống nổi tiếng sử dụng thuật toán |
Google Maps, Apple Maps, các hệ thống định vị vệ tinh, hệ thống lập kế hoạch đường đi của robot, các trò chơi điện tử (ví dụ: trò chơi chiến lược, trò chơi nhập vai), hệ thống quản lý mạng, và các công cụ lập kế hoạch dự án. |