Thuật toán giải mê cung: Weighted A* – đánh đổi giữa tốc độ và tính tối ưu

Trong bài này, chúng ta sẽ quay lại A*, nhưng với một điều chỉnh quan trọng: đưa vào trọng số cho heuristic. Kết quả là một thuật toán linh hoạt hơn, cho phép kiểm soát trực tiếp sự cân bằng giữa tốc độ và tính tối ưu.

1. Ôn lại A*: f = g + h

A* mở rộng Dijkstra bằng cách bổ sung heuristic:

• g(n): chi phí thực tế từ start đến node n
• h(n): ước lượng chi phí từ n đến goal

Hàm đánh giá của A* là:

f(n) = g(n) + h(n)

Nếu h(n) là heuristic admissible (không bao giờ đánh giá quá), A* đảm bảo tìm được nghiệm tối ưu, nhưng số lượng node mở rộng vẫn có thể rất lớn.

2. Ý tưởng của Weighted A*

Weighted A* điều chỉnh hàm đánh giá của A* bằng cách nhân heuristic với một trọng số w:

f(n) = g(n) + w × h(n)

Trong đó:

• w = 1: Weighted A* trở về A* chuẩn
• w > 1: heuristic được ưu tiên mạnh hơn

Khi w tăng, thuật toán trở nên “tham lam” hơn: nó ưu tiên các node có vẻ gần goal, dù chi phí thực tế g có thể chưa tối ưu.

Đổi lại, số node mở rộng giảm mạnh, và thời gian tìm kiếm nhanh hơn đáng kể.

3. Trade-off: tốc độ vs. tối ưu

Weighted A* không đảm bảo nghiệm tối ưu tuyệt đối khi w > 1. Tuy nhiên, trong nhiều ứng dụng thực tế (game, robot, AI thời gian thực), sự đánh đổi này là hoàn toàn chấp nhận được.

Trong giới hạn nhất định, Weighted A* cho phép ta “bẻ cong” bài toán: hy sinh một phần tối ưu để đổi lấy hiệu năng.

4. Weighted A* và Dijkstra: mối quan hệ

Có thể nhìn mối quan hệ giữa các thuật toán như sau:

• Dijkstra: chỉ dùng g, không có heuristic
• A*: g + h, cân bằng chi phí và định hướng
• Weighted A*: g + w·h, ưu tiên định hướng mạnh hơn

Dijkstra là nền tảng đảm bảo tối ưu, A* là phiên bản có định hướng, và Weighted A* là công cụ để kiểm soát mức độ định hướng đó.

5. Trực quan hóa Weighted A*

Trong demo của bài này:

• Mê cung sử dụng cùng mô hình địa hình và chi phí như bài Dijkstra.
• Người dùng có thể điều chỉnh w bằng slider.
• Đường đi và số node mở rộng thay đổi ngay lập tức theo w.

Khi tăng w, bạn sẽ thấy agent:

• Đi thẳng hơn về phía goal.
• Mở rộng ít node hơn.
• Đôi khi chọn đường có tổng chi phí cao hơn Dijkstra.

Điều này giúp hiểu rõ trực giác của heuristic và vai trò của trọng số.

6. Kết luận

Weighted A* là bước chuyển quan trọng từ thuật toán “đúng tuyệt đối” sang thuật toán “đủ tốt nhưng nhanh”. Nó phản ánh đúng tinh thần của nhiều hệ thống AI thực tế, nơi thời gian và tài nguyên có giới hạn.