Thuật toán tìm kiếm A* là một công cụ tìm kiếm đường dẫn phổ biến và đồ thị giao tiếp được sử dụng trong nhiều ứng dụng như rô bốt, phát triển trò chơi và mạng lưới. Nó kết hợp các tính năng của tìm kiếm đồng nhất và tìm kiếm tham lam đầu tiên để tìm đường dẫn ngắn nhất từ nút đầu tiên đến một mục tiêu. Hướng dẫn này cung cấp một tiến trình từng bước một để thực hiện thuật toán A * với các phép tính toán để minh họa mỗi giai đoạn.

Hiểu thuật toán A*

Thuật toán A* sử dụng chức năng chi phí, f(n) = g(n) + h(n), ở đâu:

  • g(n): Chi phí thực sự từ nút đầu đến nút n.
  • [FLT: 0]h: ) Ước tính về giá cả từ nút n đến mục tiêu.

Thuật toán khám phá các nút có giá trị thấp nhất f(n), cân bằng các chi phí thực tế và ước tính để tìm ra con đường tối ưu.

Sự tăng dần dần

Theo những bước này để thực hiện thuật toán A*:

1. Khởi động danh sách mở và đóng

Danh sách mở chứa các nút cần đánh giá, bắt đầu với nút ban đầu. Danh sách đóng chứa nút đã đánh giá.

2. Chọn nút có f(n) thấp nhất

Gỡ bỏ nút này khỏi danh sách mở và thêm nó vào danh sách đã đóng.

3. Tạo nút nối kế

Tính g(n) và h(n) cho mỗi hàng xóm. Nếu một người hàng xóm không nằm trong danh sách mở hoặc có một g(n) thấp hơn, cập nhật giá trị của nó và đặt cha của nó vào nút hiện thời.

4 lập lại cho đến khi đạt mục tiêu

Tiếp tục tiến trình cho đến khi nút đích được thêm vào danh sách đóng, chỉ ra đường dẫn ngắn nhất đã được tìm thấy.

Tính toán gương

Hãy xem xét một mạng lưới đơn giản với nút A và đích nút G. Tiền định h(n) là khoảng cách thẳng. Các tính toán ban đầu là như sau:

Bắt đầu từ điểm A, g(A) = 0, h(A) = 4. điểm nối tiếp B và C được đánh giá:

Vì điểm B: g(B) = g(A) + chi phí (A), B = 0 + 1 = 1, h(B) = 3, f(B) = 4.

Vì điểm C: g(C) = 1, h(C) = 2, f(C) = 3. Node C có f(n) thấp nhất, vì vậy nó sẽ được chọn tiếp theo.

Tiến trình này tiếp tục, cập nhật g, h và f giá trị, cho đến khi điểm nút G mục tiêu được tiếp cận với đường dẫn ngắn nhất được xác định.