TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
===== o0o =====

BÀI TẬP LỚN MƠN: TRÍ TUỆ NHÂN TẠO
Đề tài: Tìm hiểu thuật tốn A* và ứng dụng vào trò
chơi Pacman

Hà Nội -08/2023


MỤC LỤC
DANH MỤC HÌNH ẢNH...................................................................................

DANH MỤC BẢNG BIỂU..................................................................................

LỜI MỞ ĐẦU......................................................................................................

Phần I. TÌM HIỂU THUẬT TỐN TÌM KIẾM TRONG
KHƠNG GIAN TRẠNG THÁI..........................................................................
1.1 Tổng quan.....................................................................................................................................6
1.2 Thuật tốn tìm kiếm theo chiều sâu (Depth First Search)............................................................8
1.3 Thuật tốn tìm kiếm theo chiều rộng (Breadth First Search)......................................................10
1.4 Thuật toán AT.............................................................................................................................13
1.4.1 Khái niệm:............................................................................................................................13
1.4.2 Phương pháp: Sử dụng hai danh sách CLOSE và OPEN.........................................................14
1.5 Thuật toán AKT...........................................................................................................................16
1.5.1 Thuật giải.............................................................................................................................17
1.5.2 Ví dụ....................................................................................................................................18
1.6 Thuật giải A*...............................................................................................................................18
1.6.1 Khái niệm.............................................................................................................................18

1.6.2 Các tính chất........................................................................................................................20
1.6.3 Ví Dụ....................................................................................................................................21

Phần II. XÂY DỰNG CHƯƠNG TRÌNH.........................................................
2.1 Mơ tả bài tốn............................................................................................................................24
2.2 Các bước xây dựng trị chơi........................................................................................................24
2.3 Áp dụng thuật toán A*...............................................................................................................29
2.3.1 Ý tưởng xây dựng thuật toán...............................................................................................29
2.3.2 Áp dụng thuật toán..............................................................................................................30
2.4 Kết luận......................................................................................................................................33

Tài liệu tham khảo...............................................................................................


DANH MỤC HÌNH ẢN

Hình 1.1 Ví dụ về bài tốn trị chơi đốn số......................................................7
Hình 1.2 Các bước chuyển đổi trạng thái của bài tốn trị chơi đốn số............7
Hình 1.3 Ví dụ về đồ thị tìm kiếm theo chiều sâu..............................................9
Hình 1.4 Ví dụ về bài tốn tìm kiếm theo chiều rộng......................................12
Hình 1.5 Ví dụ về thuật giải At........................................................................15
Hình 1.6 Ví dụ về thuật giải Akt......................................................................18
Hình 1.7 Các bước của thuật giải Akt..............................................................18
Hình 1.8 Ví dụ về thuật giải A*.......................................................................21
Hình 2.1 Tạo map cho trị chơi........................................................................25
Hình 2.2 Giao diện của trị chơi.......................................................................26
Hình 2.3 Vẽ người chơi....................................................................................27
Hình 2.4 Kiểm tra vị trí cho người chơi...........................................................27
Hình 2.5 Di chuyển người chơi........................................................................28
Hình 2.6 Tạo Ghost cho trị chơi......................................................................28

Hình 2.6 Tạo di chuyển cho Ghost...................................................................29
Hình 2.7 Kiểm tra các node kề với node hiện tại.............................................30
Hình 2.8 Kiểm tra đường dẫn tối ưu................................................................32


DANH MỤC BẢNG BIỂU
Bảng 1.1 Các bước giải của thuật tốn tìm kiếm theo chiều sâu.....................10
Hình 1.2 Các bước giải của thuật tốn tìm kiếm theo chiều rộng....................13
Bảng 1.3 Các bước giải của thuật toán At........................................................16
Bảng 1.4 Các bước giải của thuật toán A*.......................................................22
Bảng 1.5 Bảng so sánh thuật toán BFS và DFS.............................................23


LỜI MỞ ĐẦU

Để hoàn thành bản báo cáo này, chúng em đã nhận được rất nhiều sự hướng dẫn
từ phía các thầy các cô trong khoa. Sự giảng dạy chu đáo, tận tình và sự giúp đỡ nhiệt
tình từ các thầy các cô đã giúp chúng em hiểu ra nhiều vấn đề và hoàn thành bản báo
cáo này tốt nhất.
Chúng em tỏ lịng biết ơn sâu sắc với cơ Lê Thị Thuỷ, người cơ đã tận tình hướng
dẫn và giúp đỡ, chỉ bảo nhóm em trong suốt q trình nghiên cứu đề tài và hoàn thành
báo cáo này..
Sau khoảng thời gian cô Lê Thị Thủy đưa ra đề tài, chúng em đã rất nỗ lực và cố
gắng trong việc tìm hiểu về đề tài. Các bạn trong nhóm cùng các cộng sự đã rất chăm
chỉ cũng như giúp đỡ lẫn nhau để cho ra một báo cáo hoàn hảo nhất đến thời điểm hiện
tại. Một lần nữa nhóm em xin cảm ơn giảng viên Lê Thị Thủy, các bạn trong lớp và
tập thể nhóm làm việc đã cùng nhau hồn thành tốt được bản báo cáo này.

Chúng em xin chân thành cảm ơn!



Phần I. TÌM HIỂU THUẬT TỐN TÌM KIẾM TRONG
KHƠNG GIAN TRẠNG THÁI
1.1 Tổng quan
Trong thực tế có rất nhiều bài toán mà chúng ta cần phải sử dụng đến phương
pháp tìm kiếm như tìm đường đi tới một địa điểm trên bản đồ, tìm kiếm nước đi cho
quan cờ, tìm kiếm thơng tin, tìm kiếm đường đi tối ưu,... . Cụ thể hơn là tìm kiếm một
hay một số đối tượng nào đó trong một tập lớn các đơi tượng nhằm thỏa mãn u cầu
nào đó của bài tốn.
Ví dụ như trong trò chơi cờ caro, mỗi lượt đi ta có thể đánh ở nhiều vị trí khác
nhau, nhưng ta cần phải tìm ra vị trí đánh sao cho cuối cùng ta có thể dành chiến
thắng.
Trong lĩnh vực trí tuệ nhân tạo, vấn đề tìm kiếm lại trở nên cực kỳ quan trọng do
ta phải thường xuyên đối đầu với các bài tốn tìm kiếm. Để giải quyết bài tốn bằng
phương pháp tìm kiếm, trước hết ta phải xác định được khơng gian tìm kiếm (bao gồm
tất cả các đối tượng mà trên đó thực hiện việc tìm kiếm). Nó có thể là khơng gian liên
tục và nó cũng có thể là không gian các đối tượng rời rạc. Như vậy, ta sẽ xét việc biểu
diễn một bài toán trong không gian trạng thái sao cho việc giải quyết bài tốn này
được quy về việc tìm kiếm lời giải trong khơng gian trạng thái.
Giải bài tốn trong khơng gian trạng thái, trước hết phải xác định dạng mô tả
trạng thái bài toán sao cho bài toán trở nên đơn giản hơn, phug hợp bản chất vật lý của
bài tốn (có thể sử dụng các xâu ký hiệu, vector, mảng hai chiều, cây, danh sách, ...).
Mỗi trạng thái chính là mỗi hình trạng của bài tốn, các tình trạng ban đầu và tình
trạng cuối của bài tốn gọi là trạng thái đầu và trạng thái cuối. Dưới đây là một ví dụ
về trạng thái đầu và trạng thái cuối của trò chơi 8 số:

Hình 1.1 Ví dụ về bài tốn trị chơi đoán số


Dưới đây là các bước chuyển đổi trạng thái để biến trạng thái đầu của bài toán

này về với trạng thái đích của nó:

Hình 1.2 Các bước chuyển đổi trạng thái của bài tốn trị chơi đốn số

Mỗi trạng thái là mỗi hình trạng của bài tốn cho nên mỗi hình trạng của bài tốn
trên là mỗi một cách sắp xếp các con số. Ta có thể biểu diễn mỗi hình trạng của bài
tốn bằng một mảng hai chiều kích thước 3x3 trên máy tính.
Tốn tử là các phép biến đổi từ trạng thái này sang trạng thái khác. Có hai cách
để biểu diễn các toán tử:
Biểu diễn như một hàm xác định trên tập các trạng thái và nhận giá trị cũng trong
tập này.
Biểu diễn dưới dạng các tập luật sản xuất.
Trong ví dụ về trị chơi 8 số, mỗi tốn tử là cách chuyển ơ trống, có 4 kiểu tốn
tử: chuyển ơ trống lên trên, xuống dưới, sang trái, sang phải. Tuy nhiên, đối với một số
trạng thái nào đó, một tốn tử nào đó có thể khơng áp dụng được, chẳng hạn, nếu ô
trống nằm ở cột đầu tiên thì ơ trống khơng thể sang trái được.


Q trình tìm kiếm lời giải của bài tốn được biểu diễn trong không gian trạng
thái được xem như quá trình dị tìm trên đồ thị, xuất phát từ trạng thái đầu, thơng quan
các tốn tử dịch chuyển trạng thái, lần lượt đến với các trạng thái tiếp theo cho đến khi
gặp được trạng thái đích hoặc khơng cịn trạng thía nào để tiếp tục được nữa.
Khi áp dụng các phương pháp tìm kiếm trong khơng gian trạng thái người ta
thường quan tâm tới các vấn đề sau:
Kỹ thuật tìm kiếm lời giải.
Phương pháp luận của việc tìm kiếm.
Chiến lược tìm kiếm.
Tuy nhiên khơng phải các phương pháp này đều có thể áp dụng để giải quyết cho
tất cả các bài toán phức tạp mà chỉ cho từng lớp bài tốn. Việc lựa chọn chiến lược tìm
kiếm cho bài tốn cụ thể phụ thuộc nhiều vào các đặc trưng của bài tốn.


1.2 Thuật tốn tìm kiếm theo chiều sâu (Depth First Search)
Tư tưởng của chiến lược tìm kiếm theo chiều sâu 
Các đỉnh trong đồ thị sẽ được duyệt theo từng mức độ sâu, cụ thể là các đỉnh của
đồ thị được duyệt theo từng nhánh đến nút lá và nếu chưa tìm thấy đỉnh đích thì quay
lui tới một đỉnh nào đó để sang nhánh khác. Các đỉnh của đồ thị được duyệt theo các
nhánh đến nút lá.
Nếu chưa tìm thấy đỉnh TG thì quay lui tới một đỉnh nào đó để sang nhánh khác.
Việc tìm kiếm kết thúc khi tìm thấy đỉnh TG hoặc đã hết các đỉnh
Thuật tốn tìm kiếm theo chiều sâu
Lưu trữ: Sử dụng hai danh sách DONG và MO để lưu trữ các đỉnh trong đó:
DONG: Chứa các đỉnh đã xét, hoạt động theo kiểu FIFO (hàng đợi).
MO: chứa các đỉnh đang xét , hoạt động theo kiểu LIFO (ngăn xếp).
Thuật giải:
MO = Ø;

MO = MO  {T0} T0}

while (MO != Ø)


{T0}

n = get(MO) // lấy đỉnh đầu trong danh sach MO

if (n==TG) // nếu n là trạng thái kết thúc
return TRUE // tìm kiếm thành cơng, dừng
DONG = DONG  {T0} n} //đánh dấu n đã được xét
for các đỉnh kề v của n
if (v chưa đc xét) //v chưa ở trong DONG

MO = MO  {T0} v} //đưa v vào đầu DS MO
father(v)=n// lưu lại vết đường đi từ n đến v
}
Ví dụ thuật tốn tìm kiếm theo chiều sâu.
Cho đồ thị như hình vẽ sau:
A

B

M

X

N

Y

R

C

U

S

L

V

G


D

O

I

P

J

H

Hình 1.3 Ví dụ về đồ thị tìm kiếm theo chiều sâu

n là đỉnh xét, A(n) là đỉnh kề với đỉnh xét
Đỉnh đầu T0=A, TG = {T0} R}


n

A(n)

MO

DONG

A
A


B,C,D

B,C,D

A

B

M,N

M,N,C,D

A,B

M

X,Y

X,Y,N,C,D

A,B,M

X

rỗng

Y,N,C,D

A,B,M,X


Y

R,S

R,S,N,C,D

A,B,M,X,
Y

R
Bảng 1.1 Các bước giải của thuật tốn tìm kiếm theo chiều sâu

Đỉnh xét là đỉnh R nên ta dừng tìm kiếm.
Nhận xét:
+ Nếu trong đồ thị G tồn tại đường đi từ T0 đến 1 đỉnh TG  Goal thì hàm DFS
sẽ dừng lại và cho đường đi p có độ dài có thể khơng ngắn nhất
+ Với DFS các đỉnh được duyệt theo từng nhánh (theo chiều sâu) .
+ Thuật tốn DFS có độ phức tạp O(bd) với b là bậc của cây và d là chiều sâu
của cây. Tuy nhiên trong trường hợp xấu nhất cũng là O(bd)

1.3 Thuật tốn tìm kiếm theo chiều rộng (Breadth First Search)
a.
•
•
•

Tư tưởng của chiến lược tìm kiếm theo chiều rộng
Từ đỉnh xuất phát duyệt tất cả các đỉnh kề.
Làm tương tự với các đỉnh vừa được duyệt.
Quá trình duyệt kết thúc khi tìm thấy đỉnh TG hoặc đã hết các

đỉnh để duyệt.
b. Thuật tốn tìm kiếm theo chiều rộng
Lưu trữ: Sử dụng hai danh sách DONG và MO hoạt động theo
kiểu FIFO (hàng đợi).


DONG: Chứa các đỉnh đã xét
MO: chứa các đỉnh đang xét
MO = Ø; MO = MO ∪ {T0} T0}
while (MO != Ø)
{T0}
n = get(MO) // lấy đỉnh đầu trong danh sach MO
if (n==TG) // nếu n là trạng thái kết thúc
return TRUE // tìm kiếm thành cơng, dừng
DONG = DONG ∪ {T0} n} //đánh dấu n đã được xét
for các đỉnh kề v của n
if (v chưa đc xét) //v chưa ở trong DONG
MO = MO ∪ {T0} v} //đưa v vào cuối DS MO
father(v)=n// lưu lại vết đường đi từ n đến v
}
Chúng ta có một số nhận xét sau đây về thuật tốn tìm kiếm theo chiều rộng:
Trong tìm kiếm theo chiều rộng, trạng thái nào được sinh ra trước sẽ được phát
triển trước, do đó danh sách MỞ được xử lý như hàng đợi. Trong bước 2, ta cần kiểm
tra xem n có là trạng thái kết thúc hay khơng. Nói chung các trạng thái kết thúc được
xác định bởi một số điều kiện nào đó, khi đó ta cần kiểm tra xem n có thỏa mãn các
điều kiện đó hay khơng.
Nếu bài tốn có nghiệm (tồn tại đường đi từ trạng thái ban đầu tới trạng thái
đích), thì thuật tốn tìm kiếm theo chiều rộng sẽ tìm ra nghiệm, đồng thời đường đi tìm
được sẽ là ngắn nhất. Trong trường hợp bài tốn vơ nghiệm và khơng gian trạng thái
hữu hạn, thuật tốn sẽ dừng và cho thơng báo vơ nghiệm.

Đánh giá tìm kiếm theo chiều rộng:
Bây giờ ta đánh giá thời gian và bộ nhớ mà tìm kiếm theo chiều rộng
địi hỏi. Giả sử , mỗi trạng thái khi được phát triển sẽ sinh ra b trạng
thái kề. Ta sẽ gọi b là nhân tố nhánh. Giả sử rằng, nghiệm của bài
toán là đường đi có độ dài d. Bởi nhiều nghiệm có thể được tìm ra tại


một đỉnh bất kỳ ở mức d của cây tìm kiếm, do đó số đỉnh cần xem xét
để tìm ra nghiệm là:
1 + b + b2 +… + bd-1 + k
Trong đó k có thể là 1, 2, …, bd. Do đó số lớn nhất các đỉnh cần
xem xét là: 1 + b + b2 +… + bd-1
Như vậy, độ phức tạp thời gian của thuật tốn tìm kiếm theo
chiều rộng là O(bd). Độ phức tạp không gian cũng là O(bd), bởi vì ta
cần lưu vào danh sách MỞ tất cả các đỉnh của cây tìm kiếm ở mức d,
số các đỉnh này là bd.
c. Ví dụ thuật tốn tìm kiếm theo chiều rộng.
Cho đồ thị như hình vẽ sau:
A

B

M

X

N

Y


R

C

U

S

L

V

G

D

O

I

H

Hình 1.4 Ví dụ về bài tốn tìm kiếm theo chiều rộng

P

J


n


A(n)

MO

DONG

A
A

B,C,D

B,C,D

A

B

M,N

M,N,C,D

A,B

M

X,Y

X,Y,N,C,D


A,B,M

X

rỗng

Y,N,C,D

A,B,M,X

Y

R,S

R,S,N,C,D

A,B,M,X,Y

R
Hình 1.2 Các bước giải của thuật tốn tìm kiếm theo chiều rộng

Đỉnh xét là đỉnh R nên ta dừng tìm kiếm.
Nhận xét:
+ Nếu trong đồ thị tồn tại đường đi từ T0 đến 1 đỉnh TG  Goal thì
hàm BFS sẽ dừng lại và cho đường đi p có độ dài ngắn nhất.
+ Với BFS các đỉnh được duyệt theo từng mức (theo chiều rộng).
+ Thuật tốn BFS có độ phức tạp O(bd) với b là bậc của cây và d là
chiều sâu của cây

1.4 Thuật toán AT

1.4.1 Khái niệm:
Thuật giải AT là một phương pháp tìm kiếm theo kiểu BeFS với chi phí của đỉnh
là giá trị hàm g (tổng chiều dài thực sự của đường đi từ đỉnh bắt đầu đến đỉnh hiện tại).

Cho đồ thị G = (V, E) với V: tập đỉnh; E: Tập cung. Với mỗi một cung người
ta gắn thêm một đại lượng được gọi là giá của cung.
C : E → R+
e → C(e)
Khi đó đường đi p = n1, n2, …nk có giá được tính theo cơng thức:
k -1




C(p) =C(ni , ni+1 )
i=1

Vấn đề đặt ra là tìm đường đi p tù T0 đến đỉnh TG ∈ Goal sao cho c(p) → min
Vào:

- Đồ thị G =
(V, E) C:
E → R+
e → C(e)
- Đỉnh đầu T0 và Goal chứa tập các đỉnh đoch

Ra:

Đường đi p: T0 → TG ∈ Goal sao cho:
C(p) = g(nk) = min {T0} g(n)/n ∈ Goal }.


1.4.2 Phương pháp: Sử dụng hai danh sách CLOSE và OPEN
Phương pháp:
-

Tìm đường đi có chi phí nhỏ nhất từ một đỉnh cho trước tới một đỉnh.
Sử dụng hai danh sách MO và DONG.
Ta sẽ chọn đỉnh có chi phí nhỏ nhất trong tập MO để đem ra xét tiếp. Xét
đến khi nào xuất hiện đỉnh cần tìm thì dừng.
Chi phí f(n) = g(n).
Lưu ý: Nếu xuất hiện hai đỉnh cùng min (chúng có cùng chi phí nhỏ nhất)
thì ta chọn ngẫu nhiên một đỉnh để xét.

-

Thuật giải:
void AT()
{T0}
OPEN ={T0} T0}, g(T0) = 0, CLOSE = ∅
while OPEN ≠ ∅do
{T0}
n ← getNew(OPEN)
// lấy đỉnh n sao cho g(n)
→ min if (n = TG) then return True
else
{T0}


for each m ∈ A(n) do
if(m ∈ OPEN) and (m ∈CLOSE) then

{T0}
g(m) = g(n) +
cost(m,n)
OPEN = OPEN
∪{T0} m}
}
else g(m) = min{T0} g(m),
gnew(m)}
CLOSE = CLOSE ∪ {T0} n}
}
return False;
}
}
Ví dụ :

Hình 1.5 Ví dụ về thuật giải At


Cha

Con

N

Bn

Mo

Dong


A(0)
A(0)

B,C

B(0),C(10)

A

A

B

B(2)

D,E

D(17),E(22),C(10)

A,B

A

C

C(10)

F,G

F(14),G(11),D(17),E(22)


A,B,C

C

G

G(11)

I

F(14),I(41),D(17),E(22)

A,B,C,G

C

F

F(14)

J,I

F(214),I(41),D(17),E(22)

A,B,C,G,F

B

D


D(17)

H

H(20),F(214),I(41),E(22)

A,B,C,G,F,D

D

H

H(20)

J

J(70), I(41), E(22)

A,B,C,G,F,D,H

B

E

E(22)

H,F

H(24),F(34),J(70),I(41)


A,B,C,G,F,D,H,E

E

H

H(24)

J

F(34),J(70),I(41),J(70)

A,B,C,G,F,D,H,E,H

E

F

F(34)

I,J

J(70),I(41)

A,B,C,G,F,D,H,E,H,F

G

I


I(41)

J,K

J(46),K(81)

A,B,C,G,F,D,H,E,H,F,I

I

J

J(46)

Đích

JIGCA
Bảng 1.3 Các bước giải của thuật tốn At

Nhận xét:
i)

Nếu thay điều kiện g(n) → min bằng điều kiện d(n) → max trong đó
d(n) là độ sâu hiện tại của đỉnh n. Khi đó AT trở thành DFS.

1.5 Thuật tốn AKT
Thuật giải AT trong q trình tìm đường đi chỉ xét đến các đỉnh và giá của
chúng. Nghĩa là việc tìm đỉnh triển vọng chỉ phụ thuộc hàm g(n) (thông tin quá
khứ). Tuy nhiên thuật giải này không cịn phù hợp khi gặp phải những bài tốn

phức tạp (độ phức tạp cấp hàm mũ) do ta phải tháo một lượng nút lớn. Để khắc
phục nhược điểm này, người ta sử dụng thêm các thông tin bổ sung xuất phát từ
bản thân bài tốn để tìm ra các đỉnh có triển vọng, tức là đường đi tối ưu sẽ tập
trung xung quanh đường đi tốt nhất nếu sử dụng các thơng tin đặc tả về bài tốn
(thơng tin q tương lai).
Theo thuật giải này, chi phí của đỉnh được xác
định:


f(n) = g(n) + h(n)
+ Đỉnh n được chọn nếu f(n) min.
+ g(n) là chi phí đi từ đỉnh trước đó đến đỉnh hiện tại.
+ h(n) là hàm thỏa mãn yêu cầu loại bỏ bớt các đỉnh không liên quan và tìm ra
các đỉnh có triển vọng (tùy thuộc vào từng bài toán)
Việc xác định hàm ước lượng h(n) được thực hiện dựa theo:
i)

Chọn toán tử xây dựng cung sao cho có thể loại bớt các đỉnh khơng liên
quan và tìm ra các đỉnh có triển vọng.

ii) Sử dụng thêm các thông tin bổ xung nhằm xây dựng tập OPEN và cách
lấy các đỉnh trong tập OPEN.
Để làm được việc này người ta phải đưa ra độ đo, tiêu chuẩn để tìm ra
các đỉnh có triển vọng. Các hàm sử dụng các kỹ thuật này gọi là hàm
đánh giá. Sau đây là một số phương pháp xây dựng hàm đánh giá:
i)

Dựa vào xác suất của đỉnh trên đường đi tối ưu.

ii) Dựa vào khoảng cách, sự sai khác của trạng thái đang xét với trạng thái

đích hoặc các thơng tin liên quan đến trạng thái đích.
1.5.1 Thuật giải
Vào:

- Đồ thị G = (V, E) trong đó V là tập đỉnh, E là tập cung.
- f: V RR+ ( f(n): hàm ước lượng)
- Đỉnh đầu T0 và tập các đỉnh đích

Ra:

- Đường đi p: T0 R TG  Goal

Phương pháp: Sử dụng 2 danh sách CLOSE và OPEN
void AKT()
{T0}
OPEN = {T0} T0}, g(T0) = 0
Tính h(T0), f(T0) = g(T0) + h(T0)
while OPEN ≠ ∅do
{T0}


n ← getNew(OPEN)
// lấy đỉnh n sao cho f(n)
→ min if(n = TG) then return True
else
{T0}
for each m ∈ A(n) do
{T0}
g(m) = g(n) + cost(m,n)
Tính h(m), f(m) = g(m)

+ h(m) OPEN = OPEN
∪ {T0} m}
}
}
return False;
}
1.5.2 Ví dụ

Hình 1.6 Ví dụ về thuật giải Akt

+ Chọn hàm h(n) là số các con số khơng nằm đúng vị trí của nó so với trạng
thái đích.
+ Chọn hàm g(n) là số lần dịch chuyển ô trống từ trạng thái đầu đến trạng thái
n.


Hình 1.7 Các bước của thuật giải Akt

1.6 Thuật giải A*
1.6.1 Khái niệm
A* là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật toán
này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút
thỏa mãn một điều kiện đích). Thuật tốn này sử dụng một "đánh giá heuristic" để xếp
loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó. Thuật toán này
duyệt các nút theo thứ tự của đánh giá heuristic này.
Thuật tốn tìm kiếm A* là một trong những kỹ thuật tốt nhất và phổ biến nhất được sử
dụng để tìm kiếm đường đi và duyệt đồ thị. Khơng giống như các kỹ thuật duyệt khác,
A* có “bộ não”. Điều đó có nghĩa là nó thực sự là một thuật tốn thơng minh tách biệt
nó với các thuật tốn thơng thường khác. Nhiều trị chơi và bản đồ dựa trên nền tảng
web sử dụng thuật tốn này để tìm đường đi ngắn nhất rất hiệu quả.

Thuật toán A* là mở rộng của Akt bằng cách bổ sung giả quyết trường hợp khi mở
một nút mà nút này đã có sẵn trong tập MO hoặc DONG.
Ngoài lưu trữ các giá trị cơ bản như f, h, g. Nó cịn lưu trữ:
+ Trạng thái cha của trạng thái Ti. Trong trường hợp có nhiều trạng thái dẫn đến
Ti (nhiều cha) thì chọn Cha(Ti) sao cho chi phí đi từ trạng thái khởi đầu đến Ti
là thấp nhất: g(Ti)min = (g(Tcha) + cost(Tcha, Ti)min).


+ Danh sách các trạng thái kế tiếp của Ti: danh sách này lưu trữ các trạng thái kế
tiếp Tk của Ti sao cho chi phí đến Tk thơng qua Ti từ trạng thái ban đầu là thấp
nhất.

Thuật toán A*
A* lưu giữ một tập các lời giải chưa hoàn chỉnh, nghĩa là các đường đi qua đồ thị,
bắt đầu từ nút xuất phát. Tập lời giải này được lưu trong một hàng đợi ưu tiên (priority
queue). Thứ tự ưu tiên gán cho một đường đi được quyết định bởi hàm.
Trong đó, là chi phí của đường đi cho đến thời điểm hiện tại, nghĩa là tổng trọng số
của các cạnh đã đi qua. là hàm đánh giá heuristic về chi phí nhỏ nhất để đến đích từ .
Ví dụ, nếu "chi phí" được tính là khoảng cách đã đi qua, khoảng cách đường chim
bay giữa hai điểm trên một bản đồ là một đánh giá heuristic cho khoảng cách còn phải
đi tiếp.
Hàm có giá trị càng thấp thì độ ưu tiên của càng cao (do đó có thể sử dụng một cấu
trúc heap tối thiểu để cài đặt hàng đợi ưu tiên này)
Void AStar ()
{T0}
Open = {T0} T0 }, Closed = Ø
g( T0) = 0, tính h ( T0), f ( T0) = g (T0) +h (T0)
while Open ≠ Ø
{T0}
n  getNew (Open) //lấy đỉnh n sao cho g(n)  min

if ( n = TG ) then return path T  TG
else
{T0}
for each m ∈ A(n) do
if (m ∉ Open + Closed)
{T0}
Tính h (m), g (m),
f (m) = g (m) + h (m)