Dưới đây là trích một phần bài tập thực hành Trí tuệ nhân tạo.


Lưu đồ và mã giả của thuật giải A*

  • Close hay Examined?

Tập hợp Close là tập hợp những đỉnh đã từng có tổng chi phí nhỏ nhất tập hợp Open.

Tập hợp Examined là tập hợp những đỉnh đã được mở rộng nhưng có thể chưa đủ tiêu chuẩn để vào tập hợp Close truyền thống. [1]

Nếu một đỉnh không bao giờ rời khỏi tập hợp Close thì có nghĩa là không bao giờ tồn tại một đường đi khác ngắn hơn tới dỉnh đó. [1]

Nếu một đỉnh phải rời khỏi tập hợp Close và vào tập hợp Open thì có nghĩa là tồn tại một đường đi khác ngắn hơn tới đỉnh đó. [2]

Nếu một đỉnh nằm trong tập hợp Open và phải cập nhật chi phí thì có nghĩa là tồn tại một đường đi khác ngắn hơn tới đỉnh đó. [3]

Tập hợp [2] hợp với tập hợp [3] sẽ cho ra một tập hợp những đỉnh có thể được cập nhật lại chi phí, tập hợp này chính là tập hợp Examined. Nếu như một đỉnh không bao giờ phải cập nhật chi phí thì cho dù đỉnh đó có ở trong tập hợp Examined, giá trị chi phí của nó cũng sẽ không bị thay đổi, thỏa mãn trường hợp [1].

Vậy việc bỏ tập hợp Close và sử dụng tập hợp Examined không làm thay đổi kết quả của thuật giải.

A* cổ điển dành cho consistent heuristic có thể sử dụng tập hợp Close để giảm một chút chi phí tính toán. Nhưng trong cài đặt A* không chỉ dành cho consistent heuristic, tập hợp Examined lại tiện lợi hơn: Xem mục mã giả và mã nguồn kèm theo của A*.

Bài viết này chọn sử dụng tập hợp Examined và bỏ tập hợp Close.

  • Lưu đồ

Nhấn chuột phải chọn Save as Picture… để có hình lưu đồ rõ hơn.

1

  • Mã giả của thuật giải

Input: Trạng thái bắt đầu start, trạng thái kết thúc end.

Output: Đường đi (ngắn nhất có thể) từ trạng thái bắt đầu đến trạng thái kết thúc bất kỳ.

Các bước thực hiện chính:

Bước 1:

  • Khởi tạo tập hợp open rỗng.
  • Đưa trạng thái start vào tập hợp open.

Bước 2:

Vòng lặp: Điều kiện dừng: Tập hợp open rỗng.

Lấy state có state.totalcost nhỏ nhất ra khỏi tập hợp open.

Nếu: state == end [2], Thì:

Trả về path(start, state).

Dừng thuật toán.

Kết thúc Nếu-Thì.

Vòng lặp: Với mỗi neighbor của state.

Khởi tạo biến pastcost = state.pastcost + movecost(state, neighbor) [3].

Nếu: neighbor.examined == false hoặc pastcost < neighbor.pastcost [4], Thì:

neighbor.examined = true.

neighbor.pastcost = pastcost.

neighbor.heuristiccost = heuristiccost(state, end) [5].

neighbor.totalcost = neighbor.pastcost + neighbor.heuristiccost.

neighbor.parentnode = state.

Nếu: neighbor không có trong open, Thì:

Đưa neighbor vào open.

Kết thúc Nếu-Thì.

Kết thúc Nếu-Thì.

Dừng vòng lặp.

Dừng vòng lặp.

Trả về dấu hiệu không tìm thấy đường đi.

Kết thúc thuật giải.

Định nghĩa hàm path(start, state):

Khởi tạo completepath rỗng.

Khởi tạo cost = state.totalcost.

Vòng lặp: Điều kiện dừng: state ==  start.

completepath.prepend(state).

state = state.parent.

Dừng vòng lặp.

Trả về completepath và cost.

Chứng minh tính dừng của A*

Từ thuật giải ở mục 1.a., ta có thể thấy A* dừng thuật giải khi và chỉ khi:

  • A* tìm thấy trạng thái kết thúc.

HOẶC

  • Tập hợp open của A* rỗng.

Vậy A* không thể dừng thuật giải khi và chỉ khi:

  • A* không tìm thấy trạng thái kết thúc.

  • Tập hợp open của A* không bao giờ rỗng.

Điều này có nghĩa là luôn tồn tại ít nhất một trạng thái nằm trong tập hợp open nhưng không trạng thái nào trong tập hợp open này có thể dẫn tới trạng thái kết thúc. Ta có thể phân thành các trường hợp sau:

  • Không tồn tại đường đi từ trạng thái bắt đầu đến trạng thái kết thúc nhưng vùng mở rộng đỉnh của trạng thái bắt đầu lại có vô số đỉnh.
  • Tập hợp open chứa hữu hạn trạng thái nhưng tồn tại một trạng thái bị lặp lại quá trình: Lấy ra khỏi open – Bỏ vào open. Điều này xảy ra khi luôn tồn tại một đường đi ngắn hơn từ trạng thái bắt đầu tới một trạng thái nằm trong vùng mở rộng đỉnh. Ta gọi trạng thái bị lặp lại quá trình trên là a, và điều này có nghĩa là tồn tại ít nhất một đỉnh u sao cho:

g(a) > g(u) + d(u, a) [6]

Lúc này, ta có hai trường hợp: Một là có vô hạn đỉnh u thỏa mãn trường hợp trên ; Hai là có hữu hạn đỉnh u thỏa mãn trường hợp trên nhưng các đỉnh này cũng mắc phải tình trạng như a: Luôn tồn tại một đường đi ngắn hơn tới đỉnh u. Nghĩa là tồn tại ít nhất một đỉnh v sao cho:

g(u) > g(v) + d(v, u)

Lúc này, ta có hai trường hợp: Một là có vô hạn đỉnh v thỏa mãn trường hợp trên ; Hai là có hữu hạn đỉnh v thỏa mãn trường hợp trên những các đỉnh này cũng mắc phải tình trạng như a và u: Luôn tồn tại một đường đi ngắn hơn tới đỉnh v – Từ đó, ta lại dẫn đến sự tồn tại của các đỉnh như k, q,v.v… dẫn đến một đồ thị vô hạn đỉnh – Hoặc cũng có thể tồn tại một vòng lặp:

g(v) > g1(u) + d(u, v) [7]

Thế nhưng trước khi đi vào giả thiết này, ta thấy: Nếu từ u có thể cập nhật một đường đi ngắn hơn cho v và từ v có thể cập nhật một đường đi ngắn hơn cho u, vậy thì thuật giải A* sẽ rơi vào vòng lặp u – v – u và có thể không bao giờ chạm tới được a (hoặc khi chạm tới được rồi thì thuật giải cũng không còn rơi vào vòng lặp nữa). Do đó, ta đặt lại giả thiết trên thành:

g(v) > g1(a) + d(a, v)

Để vòng lặp này tồn tại, cần phải có ít nhất một lần a mở rộng đỉnh v, sao cho:

g2(v) = g2(a) + d(a, v) [8] [1]

Sau đó giải thuật A* có thể tiếp tục chọn xét đỉnh nào khác ngoài đỉnh u trong open để cập nhật lại chi phí đi đến đỉnh a thành g3(a) < g2(a). Song trừ phi đồ thị là vô hạn đỉnh, hoặc ngoài vòng lặp a – u – v – a đang xét thì còn tồn tại một vòng lặp khác, thì chi phí đi đến đỉnh a chỉ có thể thay đổi nhờ đỉnh u. Nhưng trước đó, với cách lý luận tương tự, chi phí của đỉnh u sẽ phải chịu sự thay đổi từ đỉnh v:

g2(u) = g2(v) + d(v, u) [2]

g3(a) = g2(u) + d(u, a) < g2(a) [3]

Lúc này, ta có:

[2][3] <=> g2(v) + d(v, u) + d(u, a) < g2(a) [4]

[1][4] <=> g2(a) + d(a, v) + d(v, u) + d(u, a) < g2(a) [5]

[5] <=> d(a, v) + d(v, u) + d(u, a) < 0 [6]

[6] => d(a, v) < 0 hoặc d(v, u) < 0  hoặc d(u, a) < 0 [9]

Một ví dụ cụ thể cho đồ thị có cạnh trọng số âm là:

4

Trạng thái bắt đầu là u, trạng thái kết thúc là a. Từ u ta mở rộng ra a và v, do d(u, a) = d(u, v) nên theo lý ta chọn a hay v đều được. Ngẫu nhiên, ta chọn v (chi phí: 0 + 1 = 1), từ v ta lại vòng về u (chi phí: -2 + 1 = -1 < 0). Ở u, nếu ta tiếp tục ngẫu nhiên chọn v (chi phí: -1 + 1 = 0) thì ta lại tiếp tục từ v vòng về u (chi phí: 0 – 2 = -2 < -1). Cứ thế thuật giải A* chỉ có thể dừng khi từ u ta có thể ngẫu nhiên chọn xét đỉnh a.

Điều này cũng có nghĩa là đồ thị có trọng số âm tuy có thể khiến cho thuật giải A* rơi vào vòng lặp không bao giờ dừng, nhưng không luôn luôn.

Admissible heuristic

Cho hàm heuristic h(a) cho ra chi phí đường đi ước lượng từ đỉnh a tới đỉnh kết thúc. Cho hàm L(a) cho ra chi phí đường đi thực tế nhỏ nhất từ đỉnh a tới đỉnh kết thúc. Hàm h được gọi là admissible nếu:

h(a) ≤ L(a), với đỉnh a thuộc đồ thị [10]

Thuật giải A* sử dụng hàm heuristic có tính admissible sẽ trở thành thuật toán, dưới đây là chứng minh:

Đỉnh bắt đầu: a.

Đỉnh kết thúc: v.

Trong quá trình chạy thuật giải A*, ta có thể tìm thấy một đường đi từ a đến k, với k là một đỉnh kề đỉnh v. Lúc này ta có:

g(v) = g(k) + d(k, v)

h(v) = 0 [11]

f(v) = g(v) + h(v) = g(v) [1]

Và v được đưa vào trong open (nhưng chưa được xét). Nếu như tồn tại một đỉnh u khác trong open có f(u) < f(v) thì đỉnh u này sẽ được đưa ra xét và đỉnh u này có thể dẫn đến g1(v) < g(v) hoặc không. Cứ vậy cho đến một lúc không còn đỉnh u nào trong open có f(u) < f(v) [2] [12], thì ta sẽ đưa đỉnh v ra xét, dừng A* và kết luận đó là đường đi ngắn nhất từ a tới v.

Lúc này, nếu như tồn tại một đường đi từ a tới v ngắn hơn đường đi đã kết luận, thì tồn tại một đỉnh u trong open sao cho:

g(u) + L(u) < g(v) [3]

Mà ta lại có g(u) ≤ L(u) [4] (do hàm heuristic h là admissible), nên:

[3][4] => g(u) + h(u) < g(v) [5]

[1][5] <=> f(u) < f(v) [6]

Từ đó ta có điều suy ra [6] mâu thuẫn với giả định [2] nên ta chứng minh được đường đi đã kết luận là đường đi ngắn nhất.

Consistent heuristic

Cho hàm heuristic h(x) cho ra chi phí đường đi ước lượng từ đỉnh xtới đỉnh kết thúc. Với y là đỉnh được mở rộng trực tiếp từ đỉnh x (y kề x), ta luôn có:

3, với d(x, y) là chi phí cạnh từ x tới y.

Hàm heuristic có tính chất consistent thì cũng có tính chất admissible [13]. Chứng minh:

Với P = (f,v1,v2,…,vn,g) là đường đi ngắn nhất từ đỉnh f tới đỉnh g:

2 [14]

Một tính chất quan trọng làm nên sự khác biệt giữa consistent heuristic và admissible heuristic là:

1 [15]

<=>  f(x) ≤ f(y)

Giả sử trong đỉnh open f(a) hiện đang là nhỏ nhất, ta có:

f(a) ≤ f(u), với mọi đỉnh u nằm trong open (bao gồm cả a)

Do tính chất consistent của hàm heuristic, ta cũng có:

f(u) ≤ f(v), với v là đỉnh được mở rộng trực tiếp từ đỉnh u (v kề u)

Đỉnh a chỉ được xét lại lần thứ hai [16] khi và chỉ khi tồn tại một f1(a) < f(a), và đỉnh a có f1(a) được xét lại lần thứ hai này buộc phải được mở rộng (trực tiếp hay không trực tiếp) từ một trong các đỉnh u đang nằm trong open. Ta giả sử chuỗi mở rộng đó là: u – u1 – … – un – a, từ đó ta có:

f(a) ≤ f(u) ≤ f(u1) ≤ … ≤ f(un) ≤ f1(a)

Trái với giả thiết f1(a) < f(a), do đó đỉnh a sẽ không được xét lại lần thứ hai.

Các phương pháp chọn hàm heuristic [17]

Có hai phương pháp chính để chọn hàm heuristic:

  • Heuristic được tính chính xác từ trước

Người ta có thể tính trước chính xác chi phí đường đi giữa hai đỉnh bất kỳ trong đồ thị, rồi lưu vào trong một cơ sở dữ liệu và hàm heuristic của chúng ta lúc này sẽ nhận vào hai đỉnh, trả về chi phí đường đi chính xác giữa hai đỉnh đó nhờ vào việc tra cơ sở dữ liệu được xây dựng từ trước.

Tuy nhiên, việc làm này trên thực tế không có giá trị thực tiễn cho lắm. Bởi vậy, thay vì tính trước chính xác chi phí đường đi giữa hai đỉnh bất kỳ trong đồ thị, người ta sẽ tính trước chính xác chi phí đường đi giữa những cặp đỉnh được chọn trong đồ thị và những đỉnh này được gọi là waypoint. Sau đó xây dựng hàm heuristic:

h(n) = h’(n, w1) + distance(w1, w2) + h’(w2, goal)

Trong đó n là đỉnh đang được mở rộng, w1 và w2 là hai waypoint gần với đỉnh n nhất. Trong đó: h’(n, w1) là chi phí ước tính cho đường đi ngắn nhất từ đỉnh n tới w1, distance(w1, w2) là chi phí chính xác cho đường đi ngắn nhất từ w1 tới w2, h’(w2, goal) là chi phí ước tính cho đường đi ngắn nhất từ w2 tới goal. [18]

  • Heuristic dựa trên tri thức và kinh nghiệm

Các hàm heuristic này nhận vào hai đỉnh và cho ra chi phí ước tính đường đi ngắn nhất giữa hai đỉnh này dựa trên tri thức và kinh nghiệm mà con người cài vào.

Đối với bài toán tìm đường trong mê cung, một số hàm heuristic mà người ta thường sử dụng dựa trên tri thức toán học về khoảng cách giữa hai điểm cho trước (với giả thiết là không có vật cản chắn giữa đường đi) như: Khoảng cách Manhattan, khoảng cách Chebyshev, khoảng cách Euclid,v.v…

Một ví dụ hàm Heuristic

  • Khoảng cách Euclid

Khoảng cách Euclid giữa hai điểm a(x1 ; y1) và b(x2 ; y2) là:

gif (2)

Đây chính là khoảng cách ngắn nhất trong các loại khoảng cách giữa hai điểm trong toán học do nó chính là chiều dài của đoạn thẳng nổi hai điểm, hướng mở rộng đường đi của vật thể cũng không bị giới hạn.

Trong trường hợp chi phí tính từ khoảng cách Euclid nhỏ hơn chi phí thực (chẳng hạn nếu có tám hướng mở rộng đường đi và chi phí của tám hướng này bằng nhau và bằng 1 thì rõ ràng chi phí tính từ khoảng cách Euclid sẽ lớn hơn chi phí thực tế khi chọn hướng di chuyển xéo: gif (3)), hàm heuristic được xây dựng dựa trên khoảng cách Euclid này có tính chất consistent, chứng minh:

1

Gọi v là đỉnh kết thúc cần đạt tới, h(a) là chi phí ước tính dựa khoảng cách Euclid giữa a và v, h(b) là chi phí ước tính khoảng cách Euclid giữa b và v, d(a, b) là chi phí chính xác khi đi từ a đến b. Với tính chất của tam giác avb trong hình học Euclid, ta có:

av < ab + bv

<=> h(a) < d(a, b) + h(b)

<=> Hàm heuristic h dựa trên khoảng cách Euclid có tính chất consistent

Vậy ta có điều cần phải chứng minh.

So sánh giữa A* và tìm kiếm mù [19]

Bản chất của thuật giải A* là cân lại trọng số của đồ thị rồi thực hiện thuật toán Dijkstra [20] trên đồ thị mới được cân lại trọng số ấy.

1
Hình 3.b.1. Phần màu hồng đậm là phần các nút mà thuật giải Dijkstra phải duyệt qua.
2
Hình 3.b.2. Phần màu hồng đậm là phần các nút mà thuật giải Dijkstra phải duyệt qua sau

 

Người ta cân lại trọng số đồ thị với mong muốn những nút không nằm trên đường đi ngắn nhất sẽ mang trọng số cao hơn những nút nằm trên đường đi ngắn nhất. Công việc cân lại trọng số này thường dựa trên tri thức riêng về không gian trạng thái – điều khiến cho thuật giải A* được nghiên cứu như một nhánh của trí tuệ nhân tạo.

Dù vậy, không có nghĩa là thuật giải A* luôn mở rộng ít đỉnh hơn Dijkstra. Trên thực tế, tất cả những hàm heuristic không có tính consistent đều có thể mở rộng nhiều đỉnh hơn Dijkstra do khả năng xét lại các đỉnh đã xét. Tuy vậy, nếu hàm heuristic – dù không consistent – nhưng có tính admissible và có khả năng định hướng tốt, nó vẫn có thể làm giảm đáng kể số đỉnh phải mở rộng so với Dijkstra thuần túy.

Đương nhiên, nếu hàm heuristic luôn có giá trị là 0 thì A* biến thành Dijkstra. Hay nói cách khác, Dijkstra chính là một trường hợp đặc biệt của A*.


 

[1] Chẳng hạn, thuật giải A* đang xét đỉnh a, từ đỉnh a này nó mở rộng ra được đỉnh v và cho đỉnh v vào tập hợp Open. Lúc này đỉnh v cũng sẽ nằm trong tập hợp Examined, cho dù có thể nó chưa phải là đỉnh có tổng chi phí nhỏ nhất (và nó cũng chưa đủ tiêu chuẩn nằm trong tập Close truyền thống).

[2] Ở đây ta đã ngầm giả định: Mỗi trạng thái chỉ có một thực thể duy nhất. Nghĩa là nếu A và B cùng chỉ đến một trạng thái thì A thay đổi giá trị (A.pastcost, A.heuristiccost, A.totalcost,v.v…) dẫn đến B thay đổi giá trị.

[3] Chi phí di chuyển thực tế từ trạng thái state sang trạng thái neighbor.

[4] Ta ngầm giả định rằng ban đầu giá trị examined của mọi trạng thái đều bằng false, bởi vì ta không muốn khởi tạo giá trị dương vô cùng cho pastcost của từng trạng thái (điều có thể gây bất tiện cho cài đặt thực tế).

[5] Chi phí di chuyển ước tính từ trạng thái state sang trạng thái end.

[6] g(a) = a.pastcost (tham khảo mục 1.a.). d(u, a) là chi phí thực tế trong việc di chuyển từ trạng thái u sang trạng thái a và d(u, a) có thể có giá trị khác với d(a, u). Ở đây, tuy có thể có rất nhiều u như u1, u2,… song tất cả đều được gộp chung lại là u để trình bày được ngắn gọn. Điều này cũng xảy ra tương tự với v.

[7] Đừng quên thứ tự cập nhật chi phí đỉnh: Đầu tiên là ta tìm thấy chi phí g(u), sau đó xuất hiện một g(v) + d(v, u) < g(u), sau đó lại xuất hiện một g1(u) + d(u, v) < g(v). Với g1(u) là chi phí đi đến đỉnh u sau bao lần cập nhật chi phí. Do chi phí đi đến đỉnh u chỉ được cập nhật khi tồn tại một đường đi có chi phí thấp hơn, nên: g1(u) < g(u).

[8] Để tránh nhầm lẫn, ở đây viết g2 thay vì g hay g1 nhưng điều đó không có nghĩa là g2 < g hay g2 < g1.

[9] Bài chứng minh này được truyền cảm hứng bởi một nhận xét trên Internet: Nếu như đồ thị có cạnh trọng số âm và pastcost được khởi tạo dương vô cực thay cho việc sử dụng tập hợp Close, thì thuật toán Dijkstra có thể rơi vào vòng lặp vô hạn. Đương nhiên bài chứng minh này vẫn khó có thể xem là hoàn thiện.

[10] Trên thực tế, nhiều khi, đỉnh a hay đỉnh kết thúc có thể không thuộc đồ thị nhưng h(a) và L(a) vẫn cho ra kết quả tốt.

[11] Do đường đi từ đỉnh v tới đỉnh v có chi phí bằng 0 và ta giả định rằng đồ thị không có trọng số âm.

[12] f(v) này có thể đã được thay đổi so với f(v) ở câu trước do g(v) = g1(v). Đỉnh u ở câu này và câu trưsớc cũng chỉ là một đỉnh biểu trưng cho các đỉnh còn lại trong tập hợp open, chứ không hẳn là một đỉnh cụ thể.

[13] Nhưng chiều ngược lại thì không đúng.

[14] Bài chứng minh này là của một người đóng góp Wikipedia, bài viết: http://en.wikipedia.org/wiki/A*_search_algorithm, ngày truy cập: 01 – 05 – 2015. Với L(P) là chi phí của đường đi P.

[15] Bài chứng minh này là của một người đóng góp Wikipedia, bài viết: http://en.wikipedia.org/wiki/A*_search_algorithm, ngày truy cập: 01 – 05 – 2015. Với L(X) = g(x), L(Y) = g(y).

[16] Theo cách nói khác là: Đỉnh a được loại ra khỏi tập close sau khi nằm trong tập close.

[17] Amit’s Thoughts on Pathfinding, tác giả: Amit Patel. Link: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html .

[18] Ở đây, h’(n, w1) và h’(w2, goal) có thể là những hàm heuristic dựa trên tri thức và kinh nghiệm.

[19] Reweighting a graph for faster shortest paths, tác giả: David Eppstein, năm: 2008. Link: http://11011110.livejournal.com/135302.html .

[20] Thật ra ở đây có thể là bất kỳ thuật giải nào tìm đường đi ngắn nhất có thể, như: bidirectional search, iterative deepening,v.v…


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *