Các chiến lược tìm kiếm mù
Vương Trần Nguyên Khôi – 08110161
Trần Ngọc Long - 08110154
Trần Thanh Phong - 08110226
Nội dung
•
Biểu diễn vấn đề trong không gian trạng thái
•
Phát triển trạng thái và cây tìm kiếm
•
Các chiến lược tìm kiếm
•
Các chiến lược tìm kiếm mù
o
Tìm kiếm theo bề rộng
o
Tìm kiếm theo bề sâu
o
Tìm kiếm sâu lặp
•
Quy vấn đề về các vấn đề con. Tìm kiếm trên đồ thị và/hoặc
o
Quy vấn đề về các vấn đề con
o
Đồ thị và/hoặc
o
Tìm kiếm trên đồ thị và/hoặc
Biểu diễn vấn đề TRONG KHÔNG GIAN
TRẠNG THÁI (KGTT)
Tìm kiếm mù
Định nghĩa biểu diễn vấn đề trong KGTT

Một không gian trạng thái (state space) được biểu diễn bằng một nhóm gồm bốn
yếu tố [N, A, S, GD], trong đó:
N (node) là tập hợp các nút hay các trạng thái của đồ thị. Tập này tương ứng với
các trạng thái trong quá trình giải bài toán.
A (arc) là tập các cung (hay các liên kết) giữa các nút. Tập này tương ứng với
các bước trong quá trình giải bài toán.
S (Start) là một tập con không rỗng của N, chứa (các) trạng thái ban đầu của bài
toán.
GD (Goal Description) là một tập con không rỗng của N, chứa (các) trạng thái
đích của bài toán. Các trạng thái trong GD được mô tả theo một trong hai đặc
tính:
o
Đặc tính có thể đo lường được các trạng thái gặp trong quá trình
tìm kiếm.
o
Đặc tính của đường đi được hình thành trong quá trình tìm kiếm.
Đường đi của lời giải (solution path) là đường đi qua đồ thị này từ một nút trong
S đến một nút trong GD.
Bài toán đường đi của người đưa hàng
A
E
D
A
B
A
D
E
C
D
C

E
A
E
C
E
B
C
D
E
D
E
Path:
ABCDEA
Path:
ABCEDA
Path:
ABDCEA
Cost:
375
Cost:
425
Cost:
475
100
75
125
100
175
225
250150

175
225
225
400400325300
375 425 475
Phát triển trạng thái và cây tìm kiếm
Tìm kiếm mù
Phát triển không gian trạng thái
•
Giả sử u là một trạng thái nào đó và R là một là một toán tử biến đổi u
thành trạng thái v. Ta sẽ gọi v là trạng kề của u, hoặc v được sinh ra từ
trạng thái u bởi toán tử R. Quá trình áp dụng các toán tử để sinh ra
trạng thái kề u được gọi là phát triển trạng thái u.
Trò chơi tic-tac-toe
0 0 0
0
0
0
0
0
0 0
0 0
Bài toán trò chơi n2 -1
15 - puzzles 8 - puzzles
Bài toán trò chơi n2 -1
Không gian trạng thái trong trò chơi n2 -1
Cây tìm kiếm
Cây tìm kiếm là cây mà các đỉnh được gắn nhãn bởi các trạng thái của
không gian trạng thái. Gốc của cây tìm kiếm tương ứng với trạng thái
ban đầu. Nếu một đỉnh ứng với trạng thái u, thì các đỉnh con của nó ứng

với các trạng thái v kề u. Chúng ta có thể xem quá trình tìm kiếm như
quá trình xây dựng cây tìm kiếm.
Cây tìm kiếm
•
Ví dụ: hình sau đây minh họa một đồ thị biểu diễn không gian trạng thái
với trạng thái ban đầu là A và cây tìm kiếm ứng với không gian trạng
thái đó.
A
B
G
I
E
C
F
K
D
Đồ thị không gian
trạng thái
A
D
C
F
C B
G I
I
E
I K
F
K
E

I K
F
K
K
Cây tìm kiếm tương ứng
Các chiến lược tìm kiếm
Tìm kiếm mù
Các chiến lược tìm kiếm
•
Có thể phân các chiến lược tìm kiếm thành 2 loại:
•
Các chiến lược tìm kiếm mù (blind search). Trong các chiến lược
tìm kiếm này, không có một sự hướng dẫn nào cho tìm kiếm, ta chỉ
phát triển các trạng thái ban đầu cho tới khi gặp một trạng thái đích
nào đó.
•
Các chiến lược tìm kiếm kinh nghiệm (tìm kiếm hueristic). Trong các
chiến lược tìm kiếm này, chúng ta có thể dựa vào sự hiểu biết, dựa
vào kinh nghiệm, dựa vào trực giác để đánh giá các trạng thái, sau
đó sử dụng sự đánh giá này để hướng dẫn sự tìm kiếm: trong quá
trình phát triển các trạng thái, ta sẽ chọn một trong số các trạng thái
chờ phát triển, trạng thái được đánh giá là tốt nhất để phát triển. Do
đó tốc độ tìm kiếm nhanh hơn.
Các CHIẾN LƯỢC TÌM KiẾM MÙ
Tìm kiếm mù
Tìm kiếm theo chiều rộng
Tư tưởng của chiến lược tìm kiếm theo chiều rộng là tại mỗi bước ta sẽ chọn
trạng thái để phát triển là trạng thái được sinh ra trước các trạng thái chờ phát
triển khác.
Chúng ta sử dụng 1 danh sách để lưu cái trạng thái được sinh ra và chờ phát

triển.
Để lưu vết đường đi ta dùng thêm mảng phụ để truy vết sau khi hoàn tất.
Thuật toán tìm kiếm theo chiều rộng
void Breadth_First_Search (){
<list> OPEN // Lưu trạng thái được sinh và chờ phát triển
<list> CLOSE // Lưu trạng thái đã phát triển
OPEN  u0 //uo là trạng thái bắt đầu
CLOSE = {ø}
while (OPEN != ø){
Xóa u ở đầu OPEN
Thêm u vào CLOSE
if(u là đích){
Thông báo tìm kiếm thành công;
exit;
}
for mỗi trạng thái v kề u do
if(v không có trong OPEN và CLOSE)
Thêm v vào cuối OPEN
father(v)  u; // Cha của đỉnh v
}
Thông báo tìm thất bại;
}
Thuật toán tìm kiếm theo chiều rộng
VD: Xét đồ thị không gian trạng thái ban đầu là A, trạng thái kết thúc là F
A
B
G I E
C
F
K

D
Hoạt động của thuật toán:
Lần
lặp
Đỉnh Open Close
0 [A] [ ]
1 A [B, C, D] [A]
2 B [C, D, G, I] [A, B]
3 C [D, G, I, E, F] [A, B, C]
4 D [G, I, E, F] [A, B, C, D]
5 G [I, E, F] [A, B, C, D, G]
6 I [E, F] [A, B, C, D, G, I]
7 E [F, K] [A, B, C, D, G, I, E]
8 F [K] [A, B, C, D, G, I, E, F]
Thuật toán tìm kiếm theo chiều rộng
Nhận xét:
Trạng thái nào được sinh ra trước sẽ được phát triển trước, do đó danh sách L
được xử lý như hàng đợi.
Nếu bài toán có nghiệm (tồn tại đường đi từ trạng thái ban đầu đến trạng thái
đích) thì thuật toán này sẽ tìm được nghiệm, đồng thời đường đi tìm được sẽ là
ngắn nhất.
Nếu bài toán vô nghiệm không gian trạng thái hữu hạn, thuật toán sẽ dừng và
cho kết quả vô nghiệm.
Độ phức tạp tính toán
Giả sử mỗi trạng thái khi được phát triển sẽ sinh ra b trạng thái kề. Ta sẽ gọi b là
nhân tố nhánh. Ta cũng giả sử rằng, nghiệm của bài toán là đường đi có độ dài
d. Khi đó độ phức tạp thời gian là O(bd) và độ phức tạp không gian cũng là
O(bd).
Tìm kiếm theo chiều sâu
Tư tưởng của chiến lược tìm kiếm theo chiều sâu là tại mỗi bước ta sẽ chọn

trạng thái để phát triển là trạng thái được sinh ra sau cùng trong các trạng thái
chờ phát triển khác.
Chúng ta sử dụng 1 danh sách để lưu các trạng thái được sinh ra và chờ phát
triển.
Để lưu vết đường đi ta dùng thêm mảng phụ để truy vết sau khi hoàn tất.
Thuật toán tìm kiếm theo chiều sâu
void Depth_First_Search (){
<list> OPEN // Lưu trạng thái được sinh và chờ phát triển
<list> CLOSE // Lưu trạng thái đã phát triển
OPEN  u0 //uo là trạng thái bắt đầu
CLOSE = {ø}
while (OPEN != ø){
Xóa u ở đầu OPEN
Thêm u vào CLOSE
if(u là đích){
Thông báo tìm kiếm thành công;
exit;
}
for mỗi trạng thái v kề u do
if(v không có trong OPEN và CLOSE)
Thêm v vào đầu OPEN
father(v)  u; // Cha cua đỉnh v
}
Thông báo tìm thất bại;
}
Thuật toán tìm kiếm theo chiều sâu
VD: Xét đồ thị không gian trạng thái ban đầu là A, trạng thái kết thúc là F
A
B
G I E

C
F
K
D
Lần lặp Đỉnh Open Close
0 [A] []
1 A [B, C, D] [A]
2 B [G, I, C, D] [A, B]
3 G [I, C, D] [A, B, G]
4 I [C, D] [A, B, G, I]
5 C [E, F, D] [A, B, G, I, C]
6 E [K, F, D] [A, B, G, I, C, E]
7 K [F, D] [A, B, G, I, C, E, K]
8 F [D] [A, B, G, I, C, E, K, F]
Hoạt động của thuật toán:
Thuật toán tìm kiếm theo chiều sâu
Nhận xét
Trạng thái nào được sinh ra sau sẽ được phát triển trước, do đó danh sách L
được xử lý như ngăn xếp.
Nếu bài toán có nghiệm và không gian trạng thái hữu hạn, thì thuật toán tìm kiếm
theo chiều sâu sẽ tìm ra nghiệm tuy nhiên đường đi tìm được không nhất thiết là
ngắn nhất.
Trong trường hợp không gian trạng thái vô hạn thì tìm kiếm theo chiều sâu có thể
lặp đến vô hạn ngay cả khi bài toán có nghiệm.
Độ phức tạp tính toán
Giả sử mỗi trạng thái khi được phát triển sẽ sinh ra b trạng thái kề. Ta sẽ gọi b là
nhân tố nhánh và giả sử nghiệm của bài toán có độ dài d. Khi đó đồ phức tạp
thời gian trong trường hợp xấu nhất là O(bd), độ phức tạp không gian là O(bd).
Thuật toán tìm kiếm sâu lặp
Tìm kiếm sâu lặp được đưa ra nhằm khắc phục tình

trạng có thể không dừng của tìm kiếm sâu khi cây
tìm kiếm chứa nhánh vô hạn. Trong cách tìm kiếm
này ta tìm kiếm theo độ sâu chỉ ở mức d nào đó,
nếu không tìm ra nghiệm, ta tăng độ sâu lên d+1
đến một độ xâu max nào đó.
Thuật toán tìm kiếm sâu lặp
void Depth_Limited_Search (int d){ // d là độ sâu tối đa
<list> OPEN // Lưu trạng thái được sinh và chờ phát triển
<list> CLOSE // Lưu trạng thái đã phát triển
OPEN u0 //uo là trạng thái bắt đầu
CLOSE = {ø}
depth(u0)  0 // ghi lại độ sâu của mỗi đỉnh
while (OPEN != ø){
Xóa u ở đầu OPEN
if(depth(u) <= d) {
Thêm u vào CLOSE
if(u là đích){
Thông báo tìm kiếm thành công;
exit;
}
for (mỗi trạng thái v kề u)
if(v không có trong OPEN và CLOSE)
Thêm v vào đầu OPEN
father(v)  u; // Cha cua đỉnh v
depth(v)  depth(u) + 1
}
}
Thông báo tìm thất bại;
}
void Iterrative_Deepening_Search(){

for (d: 0  max ) {
Depth_Limited_Search(d);
if(thành công) then exit;
}
}