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 trng thái (State Space) là tập tất cả các
trng thái có thể có và tập các toán tử của bài toán.
hiu: K= (T, S, G, F). Trong đó:
oT: tập tất cả các trng thái có thể có của bài toán
oS (Start): trng thái đầu
oG (Goal): tập các trng 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 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, phù hợp
bản chất vật lý của bài toán
thể sử dụng các xâu ký hiu, véctơ, mảng hai
chiu, 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 trng thái là một tình trng của bài toán.
Các tình trng ban đầu và tình trng cuối của bài
toán gọi là trng thái đầu và trng thái cuối.
Ví dụ: Trò chơi đố 8 ô
Trng 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