Thuật toán A* – Thuật toán tìm đường

Bài toán:

Cho một bàn cờ kích thước n x n. Hãy tìm đường đi ngắn nhất từ điểm A đến điểm B biết rằng:

  • Các ô giá trị 0 là đường đi
  • Các ô giá trị 1 là vật cản, không đi được
  • Tại một ô bất kỳ, chỉ có thể đi lên, xuông, trái, phải nếu không bị cản. Không được đi chéo.

Thuật toán tìm đường

Đây là một bài toán khá phổ biến và được áp dụng vào rất nhiều trong trò chơi. Thực ra, ta có thể giải bài toán này với nhiều cách khác ví dụ như dùng Queue hay thuật toán Dijkstra (mình sẽ hướng dẫn ở bài khác). Tuy nhiên, nếu bản đồ quá lớn, việc dùng queue hay Dijsktra có thể gây ra tràn bộ nhớ vì phải lưu trữ quá nhiều trạng thái.

Để giảm bớt số lượng các trạng thái cần lưu, ta có thể sử dụng thuật toán A* này. Có một điểm các bạn nên lưu ý, đó là thuật toán này đôi khi sẽ không đưa ra đường đi ngắn nhất như các thuật toán khác, nhưng bù lại nó sẽ giảm đáng kể chi phí bộ nhớ cần thiết, phù hợp với không gian tìm kiếm lớn.

Thuật toán A*

Được công bố lần đầu tiên vào năm 1968 do Peter Hart, Nils Nilsson và Bertram Raphael của Viện nghiên cứu khoa học Stanford. Đây có thể được xem như là một mở rộng của thuật toán Dijkstra với các bước cài đặt tương đồng nhưng có thêm thông tin lượng giá (heuristic) ở mỗi bước tìm kiếm.

Bạn có thể hình dung ý tưởng vè thuật toán này như sau:
Giả sử bạn đang ở Quận 7 và muốn đi về Quận 1. Như vậy, nếu bạn không hề biết bất cứ thông tin gì về Quận 1, bạn có thể sẽ phải kiểm tra tất cả các hướng để đi đến các quận khác, bao gồm quận 8 hoặc Quận 2 hoặc Quận 4. Rồi từ các quận lân cận này, bạn lại tiếp tục tìm kiếm các lân cận xung quanh cho đến khi bạn tìm thấy Quận 1.

Tuy nhiên, nếu giả sử bạn có thêm 1 thông tin định hướng nói rằng khoảng cách từ Quận 1 đến Quận 2, 4, 8 lần lượt là 8km, 4km và 12km. Như vậy bạn sẽ ưu tiên đi về hướng Quận 4 ngay, thay vì phải đi kiểm tra các quận khác. Thông tin định hướng này được gọi là thông tin lượng giá (heuristic), nhằm tăng tốc cho quá trình tìm kiếm.

Các bước thuật toán:

Cũng như thuật toán Dijkstra, thuật toán này dùng 2 list: OPENCLOSE để lưu trạng thái các bước đi. Thực ra 2 list OPEN và CLOSE dùng để lưu các vị trí đang xét và đã xét. Ý tưởng đơn giản là những đỉnh nào đã được xét rồi thì sẽ không xét lại nữa và chuyển sang danh sách CLOSE. Tuy nhiên, nếu phát hiện có một đường đi ngắn hơn đường đi đã tìm thấy đến một đỉnh nằm trong CLOSE, đỉnh này sẽ được update lại đường đi mới.

Áp dụng vào bài toán tìm đường trong bản đồ, vì mỗi lần chỉ đi được 1 ô kề với ô đã cho, nên trọng số w(K,Mi) luôn là 1. Hàm heuristic được tính là khoảng cách từ điểm đang xét đến điểm mục tiêu theo công thức khoảng cách Euclide, nhưng vì để tiết kiệm tính toán, mình không cần lấy căn bậc 2.

Mời bạn xem hình minh họa cho thuật toán:

S: điểm khởi đầu
T: điểm mục tiêu
f(M): là khoảng cách ước lượng từ S đến T nếu đi theo con đường qua điểm M hiện tại. f(M) = g(M) + h(M)
g(M): là khoảng cách thực từ điểm S đến M
h(M): là khoảng cách ước lượng từ M đến T (heuristic function)
w(P,Q): là khoảng cách thực từ điểm P đến điểm Q kề với P hay còn gọi là trọng số của cung PQ.

Bước 1: Đặt S vào OPEN với f(S) = h(S)
Bước 2: Lặp cho đến khi list OPEN rỗng
Bước 2.1: Lấy một vị trí K có giá trị f(K) nhỏ nhất
Bước 2.2: Nếu K = T => đã tìm thấy đường đi. Dừng tìm kiếm.
Bước 3: Nếu K <> T, tìm tất cả các điểm Mi có thể đi đến được từ điểm K
Bước 3.1: Với mỗi Mi tìm được:
Bước 3.2: Tính giá trị d(Mi) = g(K) + w(K,Mi) là giá trị khoảng cách thực từ S đến Mi đi qua K.
Bước 3.3: Nếu Mi nằm trong OPEN
Bước 3.3.1: Nếu g(Mi) < d(Mi), qua bước 5
Bước 3.4: Nếu Mi nằm trong CLOSE
Bước 3.4.1: Nếu g(Mi) < d(Mi), qua bước 5
Bước 3.4.2: Chuyển Mi sang OPEN
Bước 3.5: Nếu Mi là không nằm trong OPEN và cũng không trong CLOSE
Bước 3.5.1: Thêm Mi vào OPEN
Bước 4: Cập nhật g(Mi) = d(Mi)
Bước 5: Đưa K vào CLOSE

Bài này, mình viết bằng javascript và dùng thư viện p5js để vẽ luôn UI cho các bạn dễ hình dung. Về mặt thuật toán, vẫn cứ theo đúng các bước mình đã nêu.

Mình tạo ra một class AStar để tìm đường gồm 2 hàm chính là init() để thiết lập bản đồ và solve() để tìm đường.
Hàm solve được cài đặt theo đúng các bước trên thuật toán:


Bạn có thể download toàn bộ mã nguồn tại đây.
No Comments

Post A Comment