Bài giảng Trí tuệ nhân tạo - Chương 2: Tìm kiếm trên không gian trạng thái - Bùi Đức Dương

 nút của Graph. Mỗi nút là một trạng thái của quá trình giải 
quyết vấn đề
 A: Tập các cung nối giữa các nút N. Mỗi cung là một bước trong 
giải quyết vấn đề. Cung có thể có hướng
 S: Tập các trạng thái bắt đầu. S khác rỗng.
 GD: Tập các trạng thái đích. GD Không rỗng.

 Solution path: Là một path đi từ một nút bắt đầu Si đến 
một nút kết thúc GDj . 

Mục tiêu của các giải thuật tìm kiếm là tìm ra một
solution path và/hay solution path tốt nhất.
41. Không gian trạng thái (tt)
Ví dụ 1: Trò chơi Tic –Tac – Toe
Trạng thái là một tình huống
của bàn cờ
Số trạng thái bùng nổ nhanh.
Biểu diễn trạng thái
Biểu diễn không gian
Trạng tháii
Trạng thái kết thúc: có một người có 3 dấu X 
liên tục theo đường chéo, thẳng, ngang.
 Số trạng thái kết thúc=???
X
X
X
X
X
X
Trạng thái
kết thúc
i
51. Không gian trạng thái (tt)
Đồ thị có hướng không
lặp lại (Directed Dcyclic
Graph - DAG) 
61. Không gian trạng thái (tt)
Ví dụ 2: Trò chơi (đố) Puzzle

 Trò đố 8 ô Trạng thái đầu Trạng thái đích
1 2 3 4
12 13 14 5
11 15 6
10 9 8 7
1 2 3
8 4
7 6 5
11 14 4 7
10 6 5
1 2 13 15
9 12 8 3
2 8
3 5 7
6 2 1

 Cần biểu diễn KGTT cho bài toán này như thế nào?

 Trò đố 16 ô Trạng thái đầu Trạng thái đích
1. Không gian trạng thái (tt)
Có khả năng xảy ra
vòng lặp không?l
KGTT của 8-puzzle sinh ra
bằng phép “di chuyển ô trống”
1. Không gian trạng thái (tt)

 Cần biểu diễn KGTT cho bài toán này như thế nào?
Ví dụ 3: Bài toán TSP
2. Không gian trạng thái (tt)
Mỗi cung được đánh dấu
bằng tổng giá của con 
đường từ nút bắt đầu
đến nút hiện tại.
10
2. Tìm kiếm trên không gian trạng thái

 TTNT = Biểu diễn + Tìm kiếm
 Sự biểu diễn phải:
 Cung cấp một cơ cấu tự nhiên để thể hiện tri thức/thông tin/ dữ liệu
một cách đầy đủ (Tính biểu đạt).
 Hỗ trợ việc thực thi một cách hiệu quả việc tìm kiếmđáp án cho một
vấn đề (Tính hiệu quả).
 Liệu việc tìm kiếm:
 Có kết thúc không?
 Có chắc chắn sẽ tìm được lời giải không?
 Có chắc chắn sẽ tìm được lời giải tối ưu không?
11
2. Tìm kiếm trên không gian trạng thái (tt)

 Các vấn đề khó khăn trong tìm kiếm với các bài toán AI
 Đặc tả vấn đề phức tạp
 Không gian tìm kiếm lớn
 Đặc tính đối trượng tìm kiếm thay đổi
 Đáp ứng thời gian thực
 Meta knowledge và kết quả “tối ưu”
 Khó khăn về kỹ thuật
12
2. Tìm kiếm trên không gian trạng thái (tt)
 State Space
Không gian tìm kiếm thường là
một graph
Mục tiêu tìm kiếm là một path
Phải lưu trữ toàn bộ không gian 
trong quá trình tìm kiếm
Không gian tìm kiếm biến động 
liên tục trong quá trình tìm kiếm
Đặc tính của trạng thái/nút là
phức tạp & biến động
 Database
Không gian tìm kiếm là một list 
hay tree
Tìm kiếm một record/nút
Phần tử đã duyệt qua là không 
còn dùng tới
Không gian tìm kiếm là cố định 
trong quá trình tìm kiếm
Thuộc tính của một record/nút là
cố định

 State Space Search vs Database Search
13
2. Tìm kiếm trên không gian trạng thái (tt)

 Chiến lược tìm kiếm
 Data-Driven-Search: Quá trình search sẽ đi từ trạng thái hiện thời 
áp dụng các luật để đi đến trạng thái kế tiếp và cứ thế cho đến khi 
đạt được một goal.
 Goal-Driven-Search: Quá trình search sẽ đi từ trạng thái hiện tại 
(goal tạm thời) tìm xem luật nào có thể sinh ra trạng thái này. Các 
điều kiện để áp dụng được các luật đó trở thành subgoal. Quá trình 
lặp lại cho đến khi lui về đến các sự kiện ban đầu.
Data-Driven Search or 
Goal-Driven Search?
14
2. Tìm kiếm trên không gian trạng thái (tt)

 Cả hai chiến lược cùng làm việc trên không gian trạng thái 
nhưng thứ tự và số các sự kiện duyệt qua khác nhau do 
cơ chế sinh ra các trạng thái khác nhau.

Quyết định chọn lựa chiến lược tùy thuộc vào:
 Độ phức tạp của các luật
 Độ phân chia của không gian trạng thái
 Sự hiện hữu của dữ liệu
 Goal đã có hay chưa, nhiều hay ít
 Goal được đặc tả như thế nào: state cụ thể hay mô tả mang tính đặc tính
 Cơ sở thông tin để chọn lựa chiến lược hợp lý là một META 
KNOWLEDGE
15
2. Tìm kiếm trên không gian trạng thái (tt)
 Tìm kiếm đi từ dữ liệu đến mục tiêu thích hợp khi:
 Tất cả hoặc một phần dữ liệu được cho từ đầu.
 Có nhiều mục tiêu, nhưng chỉ có một số ít các phép toán có thể áp
dụng cho một trạng thái bài toán. 
 Rất khó đưa ra một mục tiêu hoặc giả thuyết ngay lúc đầu.
 Tìm kiếm đi từ mục tiêu trở về dữ liệu thích hợp khi:
 Có thể đưa ra mục tiêu hoặc giả thuyết ngay lúc đầu.
 Có nhiều phép toán có thể áp dụng trên 1 trạng thái của bài toán ⇒
sự bùng nổ số lượng các trạng thái. 
 Các dữ liệu của bài toán không được cho trước, nhưng hệ thống
phải đạt được trong quá trình tìm kiếm.
16
2. Tìm kiếm trên không gian trạng thái (tt)

 Tìm kiếm theo chiều rộng (BFS)
Procedure Breath_First_Search;
Begin
Open:=[start]; Close:=[];
While (Open []) do
begin
remove X which is the leftmost of Open;
If (X=goal) the return (Success)
else begin
generate children of X; Put X to Close;
put remain children on RIGHT end of Open;
end;
end;
Return (Fail);
End;
17
2. Tìm kiếm trên không gian trạng thái (tt)
S=[A] bắt đầu
GD=[G] là goal. Kết thúc
Cung: Đường đi

 Tìm kiếm theo chiều rộng (BFS)
18
2. Tìm kiếm trên không gian trạng thái (tt)
Lần
lặp
X Open Close
0
1
2
3
4
5
6
7
A
B
C
D
E
F
G
[A]
[B C D ]
[C D E F]
[D E F G]
[E F G]
[F G H I]
[G H I J]
[H I J]
[]
[A]
[A B]
[A B C ]
[A B C D]
[A B C D E]
[A B C D E F]
[A B C D E F]
A
B C D
E F G
H I J

 Tìm kiếm theo chiều rộng (BFS)
19
2. Tìm kiếm trên không gian trạng thái (tt)
Procedure Depth_First_Search;
Begin
Open :=[start]; Close:=[];
While (Open []) do
Begin
remove X which is the leftmost of Open;
If (X=goal) the return (Success)
else begin
generate children of X; Put X to close;
put remain children on LEFT end of open;
end;
End;
Return (Fail);
End;

 Tìm kiếm theo chiều sâu (DFS)
20
2. Tìm kiếm trên không gian trạng thái (tt)
Lần
lặp
X Open Close
0
1
2
3
4
5
6
7
8
9
A
B
E
H
I
F
J
C
G
[A]
[B C D ]
[E F C D]
[H I F C D]
[I F C D]
[F C D]
[J C D]
[C D]
[G D]
[]
[A]
[A B]
[A B E ]
[A B E H]
[A B E H I]
[A B E H I F]
[A B E H I F J]
[A B E H I F J C]
A
B C D
E F G
H I J

 Tìm kiếm theo chiều sâu (DFS)
21
2. Tìm kiếm trên không gian trạng thái (tt)
Tiêu chí BFS DFS
CTDL Open:QUEUE Open:STACK
Hiệu quả Luôn tìm ra nghiệm có
số cung nhỏ nhất
“Thường” cho kết quả 
nhanh hơn
Kết quả Chắc chắn tìm ra kết
quả nếu có
Có thể bị lặp vô tận
Bùng nổ tổ hợp X X
Giải pháp cho bùng
nổ tổ hợp?

 BFS vs DFS
22
2. Tìm kiếm trên không gian trạng thái (tt)

DFS có giới hạn (Depth Bound Search)
Depth First Search có khả năng lặp vô tận do các trạng thái 
con sinh ra liên tục. Độ sâu tăng vô tận.
Khắc phục bằng cách giới hạn độ sâu của giải thuật: quay lui
khi trạng thái đang xét đạt đến độ sâu giới hạn đã định → Sâu
bao nhiêu thì vừa? 
Chiến lược giới hạn
Cố định một độ sâu MAX, như các danh thủ chơi cờ tính trước 
được số nước nhất định
Theo cấu hình resource của máy tính
Meta knowledge trong việc định giới hạn độ sâu.
Giới hạn độ sâu → co hẹp không gian trạng thái → có thể mất 
nghiệm.
DFS có giới hạn (Depth Bound =5) trong trò chơi 8 - puzzle)
2. Tìm kiếm trên không gian trạng thái (tt)
24
2. Tìm kiếm trên không gian trạng thái (tt)

 DFS đào sâu nhiều lần (Depth-first Iterative 
Deepening Search)

 Độ phức tạp về thời gian cùng bậc với BFS và DFS.
Depth Bound =1
Depth First Search
Dừng
Tìm thấy
Goal
False INC (Depth Bound)
True
25
2. Tìm kiếm trên không gian trạng thái (tt)

 Backtrack Search
Graph Search (GS) phải có khả năng tìm kiếm ra tất cả các Path có
thể có để tìm được nghiệm: Path từ trạng thái khởi đầu đến Goal.
GS thực hiện bằng cách “lần” theo các nhánh của Graph. Từ một 
trạng thái, sinh ra các trạng thái con, chọn một trạng thái con, xem đó
là trạng thái xét kế tiếp. Lặp lại cho đến khi tìm thấy một trạng thái 
đích.
“Lần” theo các trạng thái→ Vào ngõ cụt?
Khi gặp nhánh không đi tiếp được, giải thuật phải có khả năng 
quay lui lại trạng thái trước đó để đi sang nhánh khác: Back Tracking.
26
2. Tìm kiếm trên không gian trạng thái (tt)
 Một số ký hiệu
SL (State list) : chứa danh sách các trạng thái trên path hiện đang 
xét. Nếu tìm ra goal thì SL chính là nghiệm.
NSL (New State List): chứa danh sách các trạng thái đang đợi 
xét.
DE (Dead End): chứa các trạng thái mà con cháu của chúng 
không chứa đích.
CS (Current State): chứa trạng thái đang xét.
Hướng phát triển của quá trình search tùy theo cơ cấu tổ chức 
của NSL: FIFO, FILO hay Evaluated.
27
2. Tìm kiếm trên không gian trạng thái (tt)
Procedure Backtrack_Search;
BEGIN
S:=[start]; NLS:=[start]; DE:=[ ]; CS:=start;
While (NSL[ ]) do
Begin
If (CS = Goal) then return(SL);
If (CS has no children (Except node in [DE, Sl, NSL]) )then
Begin 
While ((SL[ ]) and CS=First Element of SL)) do
Begin 
Add CS to DE
Remove first element from SL;
Remove first element from NSL;
Cs:= first element of NSL; 
End;
Add CS to SL;
End;
28
2. Tìm kiếm trên không gian trạng thái (tt)
Else 
Begin
Add children of CS (Except node in DE,SL and 
NSL) to NSL
CS:= first element of NSL;
Add CS to SL;
End;
End;
End; {end while}
Return Fail;
END.
29
2. Tìm kiếm trên không gian trạng thái (tt)
Lần
lặp
CS SL NSL DE
0
1
2
3
4
5
6
7
8
A
B
E
H
I
F
J
C
G
[A]
[B A]
[E B A]
[H E B A]
[I E B A]
[F B A]
[J F B A]
[C A]
[G C A]
[A]
[B C D A]
[E F B C D A]
[H I E F B C D 
A]
[I E F B C D A]
[F B C D A]
[J F B C D A]
[C D A]
[G C D A]
[]
[]
[]
[]
[H]
[E I H]
[E I H]
[B F J E I H]
[B F J E I H]
A
B C D
E F G
H I J
Backtrack Search - Ví dụ
30
Bài tập Chương 2

 Biểu diễn không gian trạng thái cho các bài toán đơn 
giản.

 Lấy ví dụ và minh họa các thuật toán BFS, DFS, 
DFIDS, Backtrack Search.

 Cài đặt các thuật toán BFS, DFS, DFIDS, Backtrack 
Search.
LOGO
31
Bùi Đức Dương
Khoa Công nghệ Thông tin