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

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

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

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

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

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(){