
GV: HOÀNG ANH THƠ26

2.1. KHÔNG GIAN TRẠNG THÁI
2.1.1. Khái niệm
Không gian trng thái (State Space) là tập tất cả các
trng thái có thể có và tập các toán tử của bài toán.
Ký hiu: K= (T, S, G, F). Trong đó:
oT: tập tất cả các trng thái có thể có của bài toán
oS (Start): trng thái đầu
oG (Goal): tập các trng thái đch
oF: tập các toán tử
GV: HOÀNG ANH THƠ27

2.1. KHÔNG GIAN TRẠNG THÁI
2.1.2. Biểu diễn không gian trạng thái
Trước hết phải xác định dng mô tả trng thái bài
toán sao cho bài toán trở nên đơn giản hơn, phù hợp
bản chất vật lý của bài toán
Có thể sử dụng các xâu ký hiu, véctơ, mảng hai
chiu, cây, danh sách,...
GV: HOÀNG ANH THƠ28

2.1. KHÔNG GIAN TRẠNG THÁI
2.1.2. Biểu diễn không gian trạng thái
Mỗi trng thái là một tình trng của bài toán.
Các tình trng ban đầu và tình trng cuối của bài
toán gọi là trng thái đầu và trng thái cuối.
Ví dụ: Trò chơi đố 8 ô
Trng thái đầu Trái thái cuối
GV: HOÀNG ANH THƠ29
143
7 6
582
1 2 3
8 4
7 6 5

2.1. KHÔNG GIAN TRẠNG THÁI
Ví dụ: KGTT triển khai trong Trò chơi đố 8 ô
GV: HOÀNG ANH THƠ30