Đây là thuật toán mình được học và tìm hiểu trong môn Nhập môn trí tuệ nhân tạo, mình thấy thuật toán này được áp dụng trong thực tế rất nhiều, đặc biệt là Google Maps nên mình muốn chia sẻ cho mọi người về thuật toán này.
Thuật toán A* (A-star search) được công bố lần đầu bởi ba nhà khoa học: Peter Hart, Nils Nilsson và Bertram Raphael vào năm 1968. Đây là thuật toán tìm đường đi từ một node (node bắt đầu) trên đồ thị có trọng số đến một node khác (node đích) trong đồ thị sao cho tổng chi phí của từng node n là f(n) của đường đi này là nhỏ nhất.
Ở trên, ta có hàm chi phí cho từng node n có dạng f(n) = g(n) + h(n), trong đó:
- g(n) là tổng trọng số từ node bắt đầu đến node n.
- h(n) là chi phí ước tính từ node n đến node đích. h(n) cón được gọi là hàm heuristic.
- Hàm heuristic “hợp lý”, nghĩa là h(n) <= g(n).
- Lượng bộ nhớ cần để lưu trữ tập hợp các node trên đường đi đó phải đủ lớn.
root
/ | \
node node node
- d là độ sâu của lời giải, hay ở đây là đường đi tối ưu.
Mặc dù vậy, thuật toán A* vẫn tỏ ra hiệu quả vì thuật toán này khám phá ít node hơn, từ đó có thời gian chạy nhanh hơn so với các thuật toán tìm đường đi khác mà điển hình là thuật toán Dijkstra. Chính vì vậy, thuật toán này được Google Maps sử dụng để tìm đường đi ngắn nhất giữa hai địa điểm trong thời gian ngắn.
55
|
2/23/2024 8:21:47 PM
