1
Tìm kiếm
Tìm kiếm
Ref:
Tô Hoài Việt
Khoa Công nghệ Thông tin
Đại học Khoa học Tự nhiên TPHCM

2
Tổng quát
•
Bài toán tìm kiếm
•
Tìm kiếm Theo chiều Rộng
•
Tính tối ưu, Tính đầy đủ, Độ phức tạp thời
gian và không gian
•
Cây Tìm kiếm
•
Tìm kiếm Theo chiều Sâu
3
Một bài toán Tìm kiếm
Làm sao để đi từ S đến G? Và số biến đổi có thể
ít nhất là gì?
START
GOAL
d
b
p
q

S = { START }
G = { GOAL }
succs(b) = { a }
succs(e) = { h , r }
succs(a) = NULL … etc.
cost(s,s’) = 1 cho tất cả các biến đổi
START
GOAL
d
b
p
q
c
e
h
a
f
r
6
Bài toán Tìm kiếm
Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL}
S = { START }
G = { GOAL }
succs(b) = { a }
succs(e) = { h , r }
succs(a) = NULL … etc.
cost(s,s’) = 1 cho tất cả các biến đổi
START
GOAL
d

B
à
i

t
o
á
n

n
à
o

g
i
ố
n
g

n
h
ư

v
ậ
y
?
7
Các Bài toán Tìm kiếm
8

b
p
q
c
e
h
a
f
r
Tìm kiếm Theo Chiều Rộng
0 bước từ
start
11
START
GOAL
d
b
p
q
c
e
h
a
f
r
Tìm kiếm Theo Chiều Rộng
0 bước từ
start
1 bước từ
start

a
f
r
Tìm kiếm Theo Chiều Rộng
0 bước từ
start
1 bước từ
start
2 bước từ
start
3 bước từ
start
14
START
GOAL
d
b
p
q
c
e
h
a
f
r
Tìm kiếm Theo Chiều Rộng
0 bước từ
start
1 bước từ
start

d
b
p
q
c
e
h
a
f
r
Con trỏ quay lui
0 bước từ
start
1 bước từ
start
2 bước từ
start
3 bước từ
start
4 bước từ
start
17
START
GOAL
d
b
p
q
c
e

0
= {START} và định nghĩa,
previous(START) = NULL
Sau đó ta sẽ thêm vào những trạng thái một bước từ START vào V
1
.
Và tiếp tục.
19
START
GOAL
d
b
p
q
c
e
h
a
f
r
BFS
V
0
20
START
GOAL
d
b
p
q

2
22
START
GOAL
d
b
p
q
c
e
h
a
f
r
BFS
V
0
V
1
V
2
V
3
23
START
GOAL
d
b
p
q

k+1
:= tập rỗng
Với mỗi trạng thái s trong V
k

Với mỗi trạng thái s’ trong succs(s)
Nếu s’ chưa gán nhãn
Đặt previous(s’) := s
Thêm s’ vào V
k+1
k := k+1
If V
k
rỗng thì FAILURE
Else xây dựng lời giải: Đặt S
i
là trạng thái thứ i trên đường đi ngắn
nhất. Định nghĩa S
k
= GOAL, và với mọi i <= k, định nghĩa S
i-1
=
previous(S
i
).
25
START
GOAL
d
b

g

g
i
a
n

t
ì
m

k
i
ế
m

c
h
o

p
h
é
p

b
ạ
n

l

á
c
h

t
h
u
ậ
n

t
i
ệ
n
•
B
ạ
n

c
ó

t
h
ể

n
g
h
ĩ


b
ạ
n

c
ó

t
h
ể

k
h
ô
n
g

c
ầ
n

p
h
ả
i

l
ư
u

u
?