Tìm kiếm A*

Thuật toán Dijkstra tìm được đường ngắn nhất đến đích, nhưng nó tìm theo mọi hướng cùng lúc, kể cả hướng ra xa đích. Tìm kiếm A* thêm một hiểu biết: ước lượng đích còn cách bao xa, và bỗng nhiên quá trình tìm kiếm hướng thẳng về đó.

Một đồ thị trong đó các đỉnh đã xong tạo thành một dải hẹp từ điểm xuất phát về phía đích, với một đường thẳng nét đứt chỉ vào đích và hàng đợi vẽ bên dưới
Một đồ thị trong đó các đỉnh đã xong tạo thành một dải hẹp từ điểm xuất phát về phía đích, với một đường thẳng nét đứt chỉ vào đích và hàng đợi vẽ bên dưới

Ý tưởng

Khi tìm đường trên bản đồ, bạn không xem xét những con đường dẫn ra xa nơi cần đến kỹ như những con đường dẫn về phía đó. Tìm kiếm A* cũng vậy. Mỗi đỉnh nhận một điểm: khoảng cách từ điểm xuất phát đến lúc đó, g, cộng ước lượng quãng đường còn lại, h. Quá trình tìm kiếm luôn tiếp tục từ đỉnh có điểm thấp nhất, nên các đỉnh nằm về phía đích được lấy trước.

Từng bước

Gán cho điểm xuất phát khoảng cách 0 và đưa nó vào hàng đợi với điểm h(start). Lặp lại: lấy đỉnh có điểm thấp nhất và đánh dấu khoảng cách của nó là cố định. Nếu đó là đích thì dừng: lần ngược theo các đỉnh đã ghi nhớ sẽ được đường đi. Nếu không, với mỗi đỉnh kề chưa cố định, tính khoảng cách của nó khi đi qua đỉnh này. Nếu ngắn hơn khoảng cách hiện có, hạ nó xuống, ghi nhớ đỉnh này là đường đến đó, và cho đỉnh kề điểm bằng khoảng cách mới cộng ước lượng của nó. Khi hai điểm bằng nhau, lấy đỉnh có ước lượng nhỏ hơn trước thường đến đích sớm hơn.

Một ví dụ

Lấy điểm xuất phát A và đích D. A–B dài 2 và B–D dài 2, còn A–C dài 1 và C–D dài 5. Ước lượng đường thẳng đến D là 3 từ A, 2 từ B và 3 từ C. A bắt đầu với điểm 0 + 3 = 3. Lấy A cho B điểm 2 + 2 = 4 và C điểm 1 + 3 = 4. Khi bằng điểm, A* lấy B, đỉnh có ước lượng nhỏ hơn, và B cho D điểm 4 + 0 = 4. Giờ D có điểm thấp nhất với ước lượng nhỏ nhất, nên được lấy: đường đi ngắn nhất là A → B → D, dài 4, còn C, đỉnh dẫn sai hướng, không bao giờ được cố định. Thuật toán Dijkstra thì sẽ cố định C trước, vì đó là đỉnh gần A nhất.

Một ước lượng tốt

Ước lượng không bao giờ được dài hơn khoảng cách thật đến đích; ước lượng như vậy gọi là chấp nhận được, và với nó A* luôn tìm được đường đi ngắn nhất. Đường thẳng là chấp nhận được vì không tuyến đường nào ngắn hơn đường thẳng. Nếu ước lượng còn không bao giờ giảm nhiều hơn độ dài một cạnh khi đi từ đỉnh này sang đỉnh kế tiếp, nó là nhất quán, và không đỉnh cố định nào cần xem lại. Ước lượng càng gần thực tế, A* càng cần ít đỉnh. Ước lượng bằng 0 là chấp nhận được nhưng vô ích: khi đó A* trở thành thuật toán Dijkstra. Ước lượng quá lớn làm A* nhanh hơn nhưng có thể bỏ lỡ đường đi ngắn nhất.

Lịch sử và ứng dụng

Peter Hart, Nils Nilsson và Bertram Raphael tại Stanford Research Institute công bố A* năm 1968, khi đang làm việc với Shakey, một trong những robot di động đầu tiên. Các phiên bản trước của họ có tên A1 và A2; dấu sao đánh dấu phiên bản mà họ chứng minh là tối ưu. Ngày nay A* di chuyển nhân vật vòng qua chướng ngại vật trong trò chơi điện tử, lập lộ trình và chuyển động robot, và giải các câu đố như trò chơi 15 ô, nơi ước lượng cộng xem mỗi ô cách vị trí của nó bao xa.

Shakey, robot di động của Viện Nghiên cứu Stanford, chụp tại Bảo tàng Lịch sử Máy tính. Peter Hart, Nils Nilsson và Bertram Raphael công bố A* năm 1968 khi đang làm việc trên nó.
Shakey, robot di động của Viện Nghiên cứu Stanford, chụp tại Bảo tàng Lịch sử Máy tính. Peter Hart, Nils Nilsson và Bertram Raphael công bố A* năm 1968 khi đang làm việc trên nó.

Khám phá

Mở ứng dụng và nhấn Bước. Các số trên cạnh là độ dài của chúng, ở đây khớp với độ dài được vẽ, và đường nét đứt cho thấy ước lượng đường thẳng đến đích. Hàng đợi dưới đồ thị liệt kê các đỉnh theo điểm, thấp nhất trước. Khi đích đã cố định, dòng trạng thái so sánh số đỉnh A* đã cố định với số đỉnh thuật toán Dijkstra lẽ ra cần. Hãy thử đặt đích ở một góc xa của đồ thị lớn để thấy khác biệt lớn nhất.

Câu hỏi thường gặp

Dấu sao trong A* nghĩa là gì?

Hart, Nilsson và Raphael ban đầu mô tả các thuật toán mà họ gọi là A1 và A2. A* ("A sao") là phiên bản mà họ chứng minh tìm được đường đi ngắn nhất với ít đỉnh được mở rộng nhất trong số các thuật toán tương đương dùng cùng ước lượng, khi ước lượng nhất quán.

Độ phức tạp thời gian của A* là bao nhiêu?

Trong trường hợp xấu nhất, với một ước lượng vô ích, A* làm cùng khối lượng việc như thuật toán Dijkstra: O((V + E) log V) với heap nhị phân. Với ước lượng tốt, nó chỉ cố định một phần nhỏ các đỉnh, vì vậy trong thực tế nó nhanh.

Thế nào là một heuristic tốt cho A*?

Nó nên tính nhanh, không bao giờ ước lượng quá cao khoảng cách thật, và càng gần khoảng cách đó càng tốt. Trên lưới chỉ đi được lên, xuống, trái, phải, khoảng cách Manhattan là lựa chọn phổ biến; trên bản đồ là khoảng cách đường thẳng.

Nếu heuristic ước lượng quá cao thì sao?

Khi đó A* có thể trả về một đường đi không ngắn nhất, vì nó có thể kết thúc trước khi xem xét tuyến tốt hơn. Một số chương trình cố ý làm vậy (A* có trọng số) để đổi một chút chất lượng đường đi lấy tốc độ cao hơn nhiều.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử tìm kiếm A*