QUANG HOANG'S BLOG

Tác giả: Trương Hải Nam

Trong lập trình, có lẽ các bạn đã được làm quen với khái niệm đồ thị và bài toán tìm đường đi ngắn nhất trên đồ thị nói chung. Có nhiều giải thuật liên quan đến bài toán loại này như thuật toán Dijkstra cho đồ thị đơn có trọng số của các cung (cạnh) là không âm; hoặc thuật toán Floy-Bellman cho đồ thị không có chu trình có tổng trọng số là âm. Trong bài viết này, tôi muốn giới thiệu thuật toán A* (đọc là “a sao” hoặc “a-star” trong tiếng Anh) – cách thức tìm đường heuristic dựa trên thuật toán Dijkstra và được ứng dụng rất rộng rãi trong thực tế. Cũng xin chú ý rằng một số bạn cho là heuristic đồng nghĩa với việc tìm nghiệm gần đúng, nhưng thuật toán A* lại cho chúng ta nghiệm chính xác đúng với một vài ràng buộc về hàm lượng giá.

Tại sao phải cần đến A*?

Các thuật toán cổ điển như Dijkstra được xây dựng trên các mô hình thuần tuý lý thuyết, trong đó đồ thị được xem là tập hợp các đỉnh và cung nối giữa các đỉnh đó, ngoài ra, không có bất kì thông tin gì bổ sung cho bài toán. Với mô hình lý thuyết thuần tuý như vậy, trên một đồ thị có thể tồn tại những đặc điểm ít khi xảy ra trong thực tế, chẳng hạn: có thể tồn tại một cung có trọng số lớn hơn tổng trọng số của tất cả các cung còn lại trên đồ thị, hoặc một đồ thị chẳng có cung nào. Quay lại với câu hỏi của chúng ta “Tại sao phải cần đến A*?”, câu trả lời thật đơn giản: “để giải quyết các bài toán tìm đường trong thực tế!”.

Thuật toán tìm đường Dijkstra đòi hỏi chi phí về thời gian là O(n2) cho việc tìm đường đi giữa hai cặp đỉnh bất kì; thuật toán Floy-Bellman đòi hỏi chi phí O(n) nhưng lại bắt buộc phải tìm đường đi giữa mọi cặp đỉnh trong đồ thị, dẫn đến tổng chi phí thời gian của cả thuật toán là O(n3), như vậy những thuật toán này thích hợp với các đồ thị không quá lớn (từ vài trăm tới không quá vài ngàn đỉnh). Trong khi đó, bài toán tìm đường trong thực tế thường làm việc với đồ thị có vài chục ngàn đỉnh; bù lại, các bài toán như vậy lại có thêm thông tin phụ giúp chúng ta định hướng tốt hơn trong quá trình tìm lời giải. Vấn đề ở đây là sử dụng các thông tin định hướng đó như thế nào. Ví dụ trên bài toán tìm đường, chúng ta cần tìm đường đi từ Hà Nội vào TP. Hồ Chí Minh, mọi người đều có xu hướng đi về phía Nam, vì TP. Hồ Chí Minh ở phía Nam Hà Nội, không mấy ai nghĩ đến chuyện đi lên Lạng Sơn rồi tìm đường về TP. Hồ Chí Minh (theo cách tìm kiếm mù của thuật toán Dijkstra). Một bài toán khác, trong các trò chơi chiến thuật thời gian thực, cần đi từ điểm A đến điểm B. Ở đây không thể áp dụng các thuật toán tìm đường thông thường vì bản đồ của trò chơi đôi khi có kích thước lên đến 512 x 512 ô, tương đương với một đồ thị thưa có 262.144 đỉnh; nhóm quân thường có xu hướng đi thẳng về hướng B và nếu gặp chướng ngại vật thì men theo chướng ngại vật.

Thông tin định hướng không nhất thiết chỉ là thông tin về “hướng” như hai ví dụ trên. Trong từng bài toán, thông tin này ở những hình thức khác nhau, chúng thay đổi muôn hình muôn vẻ, bản thân việc sử dụng các thông tin này như thế nào để xây dựng hàm lượng giá cũng là vấn đề lớn và thú vị. Chúng ta sẽ trở lại vấn đề này sau, còn tiếp sau đây là nội dung thuật toán A*.

Thuật toán A*

Như đã đề cập ở trên, A* là thuật toán dựa trên Dijkstra, vì vậy cũng như Dijkstra, tư tưởng tìm đường của A* dựa trên chiến lược tìm kiếm theo chiều rộng. Gần như có sự tương đương 1-1 giữa các bước thực hiện của cả hai thuật toán. Trước khi xem xét thuật toán, ta quy ước cho bài toán tìm đường đi ngắn nhất trên đồ thị G:

- u0 = đỉnh xuất phát.

- goal = đỉnh kết thúc.

- close = tập các đỉnh đã được tính toán chính xác đường đi ngắn nhất.

- open = tập các đỉnh còn lại.

- l[i,j] = trọng số của cung (i,j).

- d(i) = khoảng cách min từ i đến u0.

- v(i) = khoảng cách min ước lượng từ i đến u0.

Như vậy, nhiệm vụ đầu tiên của các thuật toán tìm đường đi ngắn nhất là phải tìm được giá trị d[goal], chúng ta hãy xem chi tiết thể hiện của hai thuật toán như dưới đây:

Thuật toán A*

d(i) = +VôCực i:[1..n]

close = [u0]

open = [1..n] - [u0]

k = u0

repeat

  { sửa đổi ước lượng min}

  i: open

    d(i) = min {d(i), d[k]+l[k,i]}

  { mở rộng tập close }

  chọn k :open để i:open

    có (d[k]+v[k])  (d(i)+v(i))

  open = open - [k]

  close = close + [k]

until goal Thuộcclose;

Thuật toán Dijkstra

d(i) = +VôCực i:[1..n]

close = [u0]

open = [1..n] - [u0]

k = u0

repeat

  { sửa đổi ước lượng min}

  i: open

    d(i) = min {d(i), d[k]+l[k,i]}

  { mở rộng tập close }

  chọn k :open để i:open

    có d[k]  d(i)

  open = open - [k]

  close = close + [k]

until goal Thuộcclose;

Sự khác biệt duy nhất của hai thuật toán ở điểm chọn đỉnh k để mở rộng tập close. Trong chiến lược tìm kiếm theo chiều rộng, việc lựa chọn trạng thái để mở rộng tìm kiếm đóng vai trò tối quan trọng. Với một trạng thái được lựa chọn tốt, có thể tìm thấy lời giải của bài toán chỉ sau số bước rất ít so với việc lựa chọn trạng thái mở rộng một cách ngẫu nhiên (lựa chọn mù). Theo chứng minh lý thuyết, nếu các trọng số của đồ thị G đều là dương (l[i,j] > 0 với mọi i¹j) và v(i) là lượng giá dương thấp hơn đường đi ngắn nhất từ đỉnh i đến u0 (0 < v(i) < d(i) với mọi i), thì thuật toán A* luôn cho kết quả đúng và không bao giờ yêu cầu nhiều thời gian hơn thuật toán Dijkstra. Có hai kết quả dễ thấy; thứ nhất, thuật toán Dijkstra có thể xem là trường hợp “suy biến” của A* trong trường hợp v(i) = 0; thứ hai, nếu v(i) là ước lượng đúng thì thuật toán A* có độ phức tạp thời gian là tuyến tính.


Vài cách xây dựng ước lượng cho bài toán ứng dụng thuật toán A*

Xây dựng hàm ước lượng cho các bài toán ứng dụng thuật toán A* là vấn đề thú vị và đôi khi rất khó. Sau đây chúng ta hãy xem xét một vài ví dụ khá đơn giản, có thể dễ dàng lý giải. Hãy xét việc phải xây dựng các ước lượng cho thuật toán A* đối với bài toán chỉ ra đường đi ngắn nhất của một quân cờ di chuyển trên bàn cờ vô tận, kẻ ô vuông và có một số ô đánh dấu không được đi vào. Chúng ta cần xây dựng v(x1,y1,x2,y2) là ước lượng của đường đi ngắn nhất từ ô (x1,y1) đến ô (x2,y2). Việc xây dựng hàm này phụ thuộc vào việc quân cờ mà chúng ta xét tới ở đây là loại gì. Sau đây tôi sẽ xây dựng kiểu lượng giá cho một vài loại quân, việc chứng minh lượng giá này là lượng giá thấp (tiêu chuẩn để thuật toán A* cho nghiệm đúng) khó dễ dàng, được dành cho bạn đọc như là bài tập:

a. Với loại quân cờ chỉ có thể dịch chuyển bước một sang một trong 4 ô có chung cạnh với ô mà nó đang đứng, có thể xây dựng hàm lượng giá đơn giản như sau:

v(x1,y1,x2,y2) = |x1-x2| + |y1-y2|

b. Với loại quân cờ là quân Vua (của cờ quốc tế), có thể dịch chuyển bước một sang một trong 8 ô có chung cạnh hoặc đỉnh với ô nó đang đứng, chúng ta có thể xây dựng hàm lượng giá như sau:

v(x1,y1,x2,y2) = max(|x1-x2|,|y1-y2|)

c. Phức tạp hơn một chút, nếu quân cờ là quân Mã, có thể dịch chuyển bước một đến một trong 8 ô chéo 1/2 với ô mà nó đang đứng, có thể xây dựng hàm lượng giá như sau (ước lượng này có thể làm chặt hơn rất nhiều một cách dễ dàng):

v(x1,y1,x2,y2) = (|x1-x2| + |y1-y2|)/3

Các ứng dụng của A*

Là thuật toán có tính định hướng cao, hàm lượng giá của thuật toán sẽ dễ dàng xây dựng nếu bản chất bài toán có tính định hướng, như trong các bài toán ví dụ ở phần trên, tất cả đều là ước lượng đường đi trên bản đồ 2 chiều. Hàm ước lượng sẽ khó xây dựng hơn rất nhiều nếu thông tin về “chiều” của bài toán là trừu tượng. Để thấy rõ được điều này, các bạn hãy thử sức với các bài tập 2 và 3 được nêu trong phần cuối của bài viết này. Trong thực tế, thuật toán A* và các biến thể của nó được sử dụng rất rộng rãi. Một trong những lĩnh vực ứng dụng thuật toán này nhiều nhất là các trò chơi chiến lược/xây dựng, tiêu biểu là “Age of Empires” của Microsoft, hậu duệ của trò chơi này là “Age of Kings” và một loạt các trò chơi cạnh tranh cùng kiểu được xây dựng trên nền một biến thể tinh vi của thuật toán A*, đó là thuật toán RA* - thuật toán A* dùng cho các ứng dụng thời gian thực. A* không phải chỉ dành cho các trò chơi ứng dụng mà còn là một thay thế hiệu quả cho thuật toán Dijsktra trong nhiều trường hợp. Nó cũng được xem như một thuật toán tìm kiếm theo chiều rộng hiệu quả. Các thuật toán tìm đường song song trên mạng (intranet/internet), bài toán tìm kiếm thông tin trên cây tri thức, cây trò chơi... đều là các biến thể hoặc dựa trên tư tưởng của thuật toán A*.



Lời kết

Việc nắm bắt các giải thuật là rất quan trọng, nhưng áp dụng các giải thuật đó như thế nào trong các bài toán thực tế là điều quan trọng hơn. Các bài toán thực tế không bao giờ trọn vẹn như trong mô hình lý thuyết, bù lại, nó lại có tính “thực tế”; sử dụng các yếu tố thực tế đó vào ứng dụng của bạn sẽ đem lại một sức sống mới cho các ứng dụng đó; chương trình của bạn sẽ “cư xử” có tính người hơn, có tính định hướng tốt hơn và qua đó sẽ thân thiện hơn với người sử dụng. Nhưng trước khi xây dựng các ứng dụng như vậy, bạn hãy thử sức mình với các bài tập dưới đây. Có thể có nhiều phương pháp giải, nhưng các bạn hãy sử dụng thuật toán A*; xây dựng một vài kiểu hàm lượng giá khác nhau và phân tích xem với từng bài toán thì kiểu lượng giá nào là tốt nhất. Chúc các bạn thành công.

1. Cho một ma trận nhị phân (các số 0 hoặc 1) kích thước m x n, với m và n trong khoảng [8, 9,..., 512]. Hai ô gọi là kề nhau nếu chúng cùng chứa số 0 và chung một cạnh. Hai ô gọi là đi được đến nhau nếu chúng có thể đi được đến nhau qua một số bước dịch chuyển qua các ô kề nhau, số bước dịch chuyển là độ dài của đường đi.

Vấn đề: Tìm đường đi có độ dài ngắn nhất từ ô [x,y] đến ô [p,q].

2. Bài thi tin học quốc tế năm 1990, tại Belorussia. Cho một bảng kích thước 4 x 4 có ghi đủ các số từ 1 đến 14, hai ô còn lại được để trống. Quy tắc chuyển hình trạng: Mỗi số đều có thể chuyển sang 1 trong 4 ô liền kề (có chung cạnh) miễn là ô đó trống. Khi đã chuyển đi, ô trước đó thành ô trống.

Vấn đề: Cho hình trạng ban đầu (ví dụ như bảng A), hãy chuyển về hình trạng đích như được cho trong bảng B sau ít bước dịch chuyển nhất.

3. Tương tự như bài số 2, nhưng bảng có 15 số từ 1 đến 15 và chỉ có 1 ô trống (chú ý rằng bài số 2 luôn tồn tại phương án giải, còn bài này thì không, vì vậy, không chỉ đơn thuần sử dụng các hàm lượng giá).