Các ứng dụng mình viết trong bài này đều đã được host lên ở đây, các bạn có thể vào xem nhé.
Thuật giải A* là gì?
Thuật giải A* là thuật giải tìm đường đi ngắn nhất trong đồ thị. Đây là 1 giải thuật Heuristics, tức là đây là 1 giải thuật mang tính xấp xỉ, kết quả đầu ra có thể không hoàn toàn chính xác. Vậy câu hỏi đặt ra là: Tại sao không sử dụng một thuật giải tuyệt đối, kết quả đầu ra luôn luôn chính xác mà lại phải sử dụng thuật giải xấp xỉ như thế này?Câu trả lời nằm ở chi phí tính toán. Để đưa ra được 1 kết quả chính xác, chúng ta phải vét cạn đồ thị ( nếu câu này sai thì mọi người hãy comment cho mình biết nhé), nhưng với thuật giải A*, nó không vét cạn, do đó, chi phí tính toán sẽ là thấp hơn.
Nói ra thì dài dòng, chốt lại là: Thuật giải A* là thuật giải tìm đường đi ngắn nhất trong đồ thị mà không vét cạn do đó mang tính xấp xỉ.
Thuật giải A* hoạt động như thế nào?
Trong thuật giải A*, mỗi 1 điểm trong đồ thị sẽ mang theo nó 3 giá trị cốt lõi:
g: đây là chi phí cần phải bỏ ra để đi từ điểm bắt đầu đến điểm hiện tại.
h: đây là chi phí ước lượng để đi từ điểm hiện tại đến điểm kết thúc.
f : giá trị này thì dễ tính: f = g + h.
Dưới đây là thuật giải A*:
Input: 1 tập các điểm trong đồ thị với trọng số tương ứng. Node start và node end.
Output: Đường đi ngắn nhất từ node start đến node end.Thuật giải gồm các bước sau đây:
B1: Khởi tạo 1 tập Open = rỗng . Khởi tạo tập Close = rỗng.
B2: Gán điểm Current = start để tính toán. Đưa điểm start vào tập Close.
B3: nếu current là end thì truy ngược lại đường đi dựa theo giá trị parent.
B4: Tìm tất cả những điểm lân cận (có thể đi được) từ điểm current và đưa vào 1 tập Neighbors. Duyệt qua từng điểm trong neighbors.
B4.1: nếu điểm neighbor đang xét đã có trong tập Close => bỏ qua
gán neighbor g = current g + cost(current, neighbor)
neighbor f = neighbor g + neighbor h.
neighbor parent = current
B4.2: nếu điểm neighbor đang xet chưa có trong tập Open thì đưa neighbor vào tập Open
B4.3: nếu neighbor đã có trong tập Open.
Nếu neighbor trong open có g > neighbor g. Thì đưa neighbor vào thay thế cho neighbor trong open.
B5: Nếu Open còn phần tử thì lấy phần tử có f nhỏ nhất để làm current, đưa current vào tập close và quay lại bước 3.
B6: nếu Open rỗng thì không tìm được đường đi.
Chắc chắn đọc xong đoạn thuật giải trên các bạn chẳng hiểu được gì đâu. Vì vậy chúng ta sẽ đi vào ví dụ cho dễ hiểu nhé:
Ta có đồ thị sau:
POINT
|
h value
|
A
|
9
|
B
|
8
|
C
|
8
|
D
|
7
|
E
|
6
|
F
|
5
|
G
|
4
|
H
|
4
|
K
|
3
|
L
|
0
|
Step
|
Open Set
|
Close Set
|
Current
|
Neighbors
|
Description
|
1
|
{}
|
{}
|
A(g=0, h=9, f=9)
|
||
2
|
{}
|
A(g=0, h=9, f=9)
|
A(g=0, h=9, f=9)
|
B(g=3,h=8,f=11, parent=A)
C(g=7,h=8,f=15, parent=A)
G(g=6,h=4,f=10,parent=A)
|
|
3
|
B(g=3,h=8,f=11, parent=A)
C(g=7,h=8,f=15, parent=A)
G(g=6,h=4,f=10,parent=A)
|
A(g=0, h=9, f=9)
|
Vì trong tập Open, G có f bé nhất nên lấy làm
current.
|
||
4
|
B(g=3,h=8,f=11, parent=A)
C(g=7,h=8,f=15, parent=A)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
|
G(g=6,h=4,f=10,parent=A)
|
C(g=8,h=8,f=16,parent=G)
K(g=9,h=3,f=12,parent=G)
|
|
5
|
B(g=3,h=8,f=11, parent=A)
C(g=7,h=8,f=15, parent=A)
K(g=9,h=3,f=12,parent=G)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
|
Vì trong tập open, B có f nhỏ nhất nên lất
làm current
|
||
6
|
C(g=7,h=8,f=15, parent=A)
K(g=9,h=3,f=12,parent=G)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
|
B(g=3,h=8,f=11, parent=A)
|
D(g=8,h=7,f=15,parent=B)
E(g=7,h=6,f=13,parent=B)
|
|
7
|
C(g=7,h=8,f=15, parent=A)
K(g=9,h=3,f=12,parent=G)
D(g=8,h=7,f=15,parent=B)
E(g=7,h=6,f=13,parent=B)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
|
Vì trong tập open, K có f nhỏ nhất nên lất
làm current
|
||
8
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
E(g=7,h=6,f=13,parent=B)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
|
K(g=9,h=3,f=12,parent=G)
|
D(g=12,h=7,f=19,parent=K)
L(g=16,h=0,f=16,parent=K)
|
|
9
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
E(g=7,h=6,f=13,parent=B)
L(g=16,h=0,f=16,parent=K)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
|
Vì trong tập open, E có f nhỏ nhất nên lất
làm current
|
||
10
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
L(g=16,h=0,f=16,parent=K)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
E(g=7,h=6,f=13,parent=B)
|
E(g=7,h=6,f=13,parent=B)
|
F(g=8,h=5,f=13,parent=E)
H(g=15,h=4,f=19,parent=E)
|
|
11
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
L(g=16,h=0,f=16,parent=K)
F(g=8,h=5,f=13,parent=E)
H(g=15,h=4,f=19,parent=E)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
E(g=7,h=6,f=13,parent=B)
|
Vì trong tập open, F có f nhỏ nhất nên lất
làm current
|
||
12
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
L(g=16,h=0,f=16,parent=K)
H(g=15,h=4,f=19,parent=E)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
E(g=7,h=6,f=13,parent=B)
F(g=8,h=5,f=13,parent=E)
|
F(g=8,h=5,f=13,parent=E)
|
L(g=10,h=0,f=10,parent=F)
|
Vì L trong neighbor có g < L trong open, nên thay L trong open bằng
L trong neighbor
|
13
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
L(g=10,h=0,f=10,parent=F)
H(g=15,h=4,f=19,parent=E)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
E(g=7,h=6,f=13,parent=B)
F(g=8,h=5,f=13,parent=E)
|
Vì trong tập open, L có f nhỏ nhất nên lất
làm current
|
||
14
|
C(g=7,h=8,f=15, parent=A)
D(g=8,h=7,f=15,parent=B)
H(g=15,h=4,f=19,parent=E)
|
A(g=0, h=9, f=9)
G(g=6,h=4,f=10,parent=A)
B(g=3,h=8,f=11, parent=A)
K(g=9,h=3,f=12,parent=G)
E(g=7,h=6,f=13,parent=B)
F(g=8,h=5,f=13,parent=E)
L(g=10,h=0,f=10,parent=F)
|
L(g=10,h=0,f=10,parent=F)
|
Vì L là điểm end. Nên thuật toán kết thúc.
Truy ngược đường đi theo parent ta có:
A -> B -> E -> F -> L
|
Và cũng trong một khoảng thời gian rảnh rỗi và có hứng thú, mình cũng đã viết 1 đoạn chương trình bằng javascript hiện thực hóa thuật giải A* này trong việc tìm đường đi trong ma trận.
Code mình đã up sẵn lên github ở đây. Bạn chỉ cần clone về và chạy thôi nhé.
Cám ơn các bạn đã xem bài viết này của mình. Nếu có thắc mắc gì thì cứ comment vào blog. Nếu được mình sẽ giải đáp.
0 nhận xét:
Đăng nhận xét