Thuật toán A* - Tìm đường ngắn nhất
Bài toán tìm đường ngắn nhất thực chất là một hình thức vét cạn (bruteforce). Máy tính sẽ tìm tất cả các đường đi có thể cho đến khi tìm đến đích. Với bài toán tìm đường trên bảng vuông, nếu xuất phát từ giữa bản đồ, máy tính sẽ tìm đường lan tỏa ra mọi hướng, kể cả các hướng mà nếu xét trực quan thì không hề có lợi, gây ra lãng phí tính toán khá nhiều. Thuật toán A* thêm vào một hàm lượng giá (heuristic function). Hàm này sẽ giúp ước lượng khoảng cách một cách tương đối giữa vị trí hiện tại đến đích, giúp máy tính trong quá trình tìm đường sẽ ưu tiên các con đường có lợi hơn.
Nếu bạn chưa đọc qua giải thuật tìm đường, mình khuyến khích các bạn nên đọc lại bài viết cấu trúc dữ liệu queue.
Về cơ bản, với thuật toán tìm đường không dùng heuristic, mỗi node tìm được sẽ được đưa vào một queue và có thông tin là khoảng cách từ điểm xuất phát đến node đó, tạm đặt là \(g(node)\) , rồi lần lượt lấy từng node ra xét dần dần mà không có sự ưu tiên. Việc đưa các node vào queue rồi liên tục gỡ ra để tìm các node mới nhằm đảm bảo khoảng cách \(g(node)\) sẽ được xét tuần tự tăng dần. Với thuật toán A*, một node sẽ chứa thêm thông tin ước lượng \(h(node)\) bên cạnh \(g(node)\), và thay vì dequeue dần dần, các node sẽ được lấy ra dựa theo ưu tiên các node có \(f(node) = g(node) + h(node)\) nhỏ nhất xét trước.
Đối với bài toán tìm đường, hàm heuristic có thể được chọn là:
Khoảng cách đường chim bay (Euclidean distance): \(h(node) = \sqrt{(node.x - target.x)^2 + (node.x - target.x)^2 + (node.y - target.y)^2}\)
Hoặc khoảng cách Manhattan: \(h(node) = |node.x - target.x| + |node.y - target.y|\)
Demo dưới sẽ cho ta thấy hiệu quả của việc sử dụng hàm lượng giá. Thông số Processing steps của thuật toán tìm đường có hàm lượng giá thấp hơn hẳn so với không dùng. Tuy nhiên, với một số trường hợp đặc biệt, thuật toán A* sẽ không chắn chắn sẽ đưa ra con đường ngắn nhất.