Thuật toán A* - Thuật toán tìm đường đi ngắn nhất giữa hai điểm bất kì được Google Maps sử dụng

Đâ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.

Thuật toán A* sẽ đảm bảo tìm được đường đi tối ưu nhất nếu thoả mãn hai điều kiện sau:

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.

Trên thực tế, điều kiện 2 rất khó để có thể đạt được, vì độ phức tạp về bộ nhớ của thuật toán là O(b^d), trong đó:b là số node được “thấy” ở mỗi nhánh. Ví dụ ở hình dưới, b = 3.
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.

Thuật toán Lập trình

254 | 2/23/2024 8:21:47 PM