KHÔNG GIAN TR NG THÁI Ạ
VÀ BÀI TOÁN TÌM KI MẾ
Th.S Dương Thị Thùy Vân
1.Khái ni m v không gian tr ng tháiệ ề ạ

Vấn đề
 Những vướng mắc, khó khăn trong cuộc
sống mà ta cần giải quyết.

Bài toán
 Một loại vấn đề mà để giải quyết, cần đến
tính toán (phép toán số, luận lí, quan hệ).
Khái ni m v không gian tr ng thái (tt)ệ ề ạ

Mô hình bài toán:
A  B

Trong đó:

A: giả thiết, điều kiện ban đầu

B: kết luận cần đạt đến

: suy luận hay giải pháp cần xác định = một số
hữu hạn bước
Ví d (trò ch i 8 s )ụ ơ ố
Khái ni m v không gian tr ng thái (tt)ệ ề ạ

Sự sắp xếp các số tại mỗi thời điểm là một
trạng thái (TT).


7 6 5
Đ nh nghĩaị

KGTT là một bộ bốn (X, u0, F, G), trong đó:
X là tập các trạng thái
u0 là trạng thái bắt đầu
F là tập các toán tử, gồm các phép biến đổi.
G là tập trạng thái đích.
2. Các cách bi u di n KGTTể ễ

Không gian trạng thái có thể biểu diễn bằng
đồ thị có hướng: mỗi đỉnh là một trạng thái,
mỗi cung là một toán tử.

Đồ thị trạng thái xác định khi:

Biết trạng thái đầu

Biết hàm next(S)(tập hợp toán tử) trả về các trạng
thái kế của S.

Biết trạng thái kết thúc (tập trạng thái kết thúc)
2. Các cách bi u di n KGTT (tt)ể ễ

Bài toán tìm được nghiệm nếu như ta tìm
được đường đi từ trạng thái bắt đầu đến một
trong các trạng thái đích.

Trong đồ thị của KGTT có thể xuất hiện chu
trình gây khó khăn cho việc tìm kiếm

Đặc tả: Tại một bờ sông có 3 người và 3 quỷ
và tất cả muốn qua sông. Trên sông có 1
thuyền nhỏ chỉ chở tối đa 2 đối tượng. Yêu
cầu: số người không được ít hơn số quỷ.
Ví d : Bài toán ng i qu qua sôngụ ườ ỷ

Biểu diễn trạng thái bằng (a, b, k)
Với a, b là số người và quỷ ở bên bờ phải
k=1 là thuyền ở bờ phải, k=0 thuyền ở bờ trái
Không gian trạng thái
Trạng thái ban đầu (3, 3, 1)
Các toán tử: chở 1 người, 1 quỷ, 2 người, 2
quỷ, (1 người và 1 quỷ)
Trạng thái kết thúc (0, 0, 1)
Ví d : Bài toán ng i qu qua sông (tt)ụ ườ ỷ
3 , 3 , 1
3 , 2 , 0 3 , 1 , 0 2 , 2 , 0

Đồ thị: là một cấu trúc bao gồm:

Tập các nút N1, N2,… Nn, Không hạn chế

Tập các cung nối các cặp nút, có thể có nhiều
cung trên một cặp nút
A
B
D
C
E
B

3.Bài toán tìm ki m ế
Vấn đề = Tìm kiếm mục tiêu
Chi n l c tìm ki m?ế ượ ế

Khi tìm kiếm lời giải, từ một trạng thái nào đó chưa
phải là trạng thái đích, ta dựa theo toán tử sinh ra
tập các trạng thái mới: mở rộng.

Để được lời giải, ta phải liên tục chọn trạng thái
mới, mở rộng, kiểm tra cho đến khi tìm được trạng
thái đích hoặc không mở rộng được KGTT.

Tập các trạng thái được mở rộng sẽ có nhiều phần
tử, việc chọn trạng thái nào để tiếp tục mở rộng
được gọi là chiến lược tìm kiếm.
Đánh giá m t chi n l c?ộ ế ượ
+ Tính đầy đủ: chiến lược phải đảm bảo tìm
được lời giải nếu có.
+ Độ phức tạp thời gian: mất thời gian bao lâu
để tìm được lời giải.
+ Độ phức tạp không gian: tốn bao nhiêu đơn
vị bộ nhớ để tìm được lời giải.
+ Tính tối ưu: tốt hơn so với một số chiến lược
khác hay không.
Thông tin m i nút?ỗ
+ Nội dung trạng thái mà nút hiện hành đang
biểu diễn.
+ Nút cha đã sinh ra nó.
+ Toán tử đã được sử dụng để sinh ra nút hiện
hành.




⇒





(2 )
®é phøc t¹p cao khã chÊp nhËn
!
n
O
n

⇒


M t s ví d v bài toán có đ ph c t p cao ộ ố ụ ề ộ ứ ạ

Bài toán phân công công việc
Một đề án gồm n công việc và các việc sẽ đưọc
thực hiên bởi m máy như nhau.
Giả sử biết thời gian để 1 máy thực hiện viêc
thứ j là tj
Yêu cầu: Tìm phương án phân công sao cho
thời gian hoàn thành toàn bộ công việc là thấp nhất.
Mẫu số liệu
n=10, m=3