BIỂU DIỄN VẤN ĐỀ TRONG
KHÔNG GIAN TRẠNG THÁI
Modelling the Problem By
State Space
2
NỘI DUNG
1. Định nghĩa không gian trạng thái
2. Tìm kiếm trong không gian trạng thái
3. Các hệ sản xuất
4. Các đặc trưng bài toán
5. Các đặc trưng hệ sản xuất
6. Các vấn đề trong thiết kế các chương trình tìm kiếm
7. Bài tập
3
ĐỊNH NGHĨA KHÔNG GIAN TRẠNGTHÁI
(KGTT)
•Một không gian trạng thái là một bộ bốn <N, A, S, GD>,
trong đó:
•N là một tập các trạng thái/ nút
•A là một tập các liên kết/ cung giữa các trạng thái/ nút
•S là một tập con không rỗng của N, bao gồm các trạng thái
ban đầu của bài toán
•GD là một tập con không rỗng của N, bao gồm các trạng thái
đích của bài toán. Tập GD được xác định bởi:
–Một liệt kê các trạng thái/ một tính chất có thể đo lường được của
các trạng thái cần đạt tới trong quá trình tìm kiếm
–Một tính chất của đường đi (path)
•Một đường đi lời giải là một đường đi trong đồ thị KGTT,
dẫn từ một trạng thái trong S đến một trạng thái trong GD
4
ĐỊNH NGHĨA KHÔNG GIAN TRẠNGTHÁI
(KGTT) (cont.)
•Ví dụ: bài toán (n2-1)-puzzle
một lưới nxn ô vuông, n2-1 ô chứa các số nguyên 1, 2, …, n2-1, ô còn lại trống. Xuất
phát từ một cấu hình đã cho, bằng một dãy các di chuyển các ô số sang ô trống để
đạt tới một cấu hình cho trước.
•15-puzzle Trạng thái ban đầu Trạng thái đích
Biểu diễn bài toán như thế nào ?
11
14
4 7
10
6 5
1 2
13
15
9
12
8 3
1 2 3 4
12
13
14
5
11
15
6
10
9 8 7
5
ĐỊNH NGHĨA KHÔNG GIAN TRẠNGTHÁI
(KGTT) (cont.)
•Tập các trạng thái: Lưới (mảng hai chiều) các ô, trong đó n2 –1
ô chứa các số từ 1 đến n2 –1 và một ôtrống
•Tập các cung « biến đổi trạng thái » (các toán tử):
–L(eft): phép dịch chuyển ô trống sang trái
–U(p): phép dịch chuyển ô trống lên trên
–R(ight): phép dịch chuyển ô trống sang phải
–D(own): phép dịch chuyển ô trống xuống dưới
?Điều kiện để các phép biến đổi này có thể thực hiện được
(tiền điều kiện – precondition)
dạng của một toán tử: <precond> →<action>
