Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang

Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ Thông tin và Truyền thông
Năm học 2012-2013
Nội dung môn học:
 Giới thiệu về Trí tuệ nhân tạo
 Tác tử
 Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc
 Tìm kiếm với tri thức bổ sung (Informed search)
 Logic và suy diễn
 Biểu diễn tri thức
 Biểu diễn tri thức khôn
g
chắc chắn
g
 Học máy
2
Trí tuệ nhân tạo
Nhắc lại: Tìm kiếm theo cấu trúc cây
 M
ộ
t chiến lư
ợ
c
(p
hươn
g

p

chứa

trong

định

nghĩa

của bài toán
 Không phù hợp với nhiều bài toán thực tế (do đòi hỏi chi phí quá
cao về thờigianvàbộ nhớ)
cao

về

thời

gian

và

bộ

nhớ)
 Các chiến lược tìm kiếm với tri thức bổ sung (informed search
strategies) sử dụng
các tri thứccụ thể của bài toán
→
Quá
strategies)

ả
i thu
ậ
t t
ì
m ki
ế
m cục b
ộ

(
Hill-climbing,
S
imulated annealing,
Local beam, Genetic algorithms)
 Các giải thuật tìm kiếm đối kháng (MiniMax, Alpha-beta pruning)
4
Trí tuệ nhân tạo
Bes
t
-first search
 Ý tưởng: Sử dụng một hàm đánh giá f(n) cho mỗi nút của
cây
tìm
kiếm
cây
tìm
kiếm
 Để đánh giá mức độ “phù hợp” của nút đó
Æ Trong quá trình tìm kiếm, ưu tiên xét các nút có mức độ phù hợp

 Ví dụ: Trong bài toán tìm đường đi từ Arad đến
Bucharest, sử dụng: h
SLD
(n) = Ước lượng khoảng cách
đường thẳng (
“
chim bay
”
)từ thành phố hiệntại
n
đến
đường

thẳng

(chim

bay )

từ

thành

phố

hiện

tại

n

Greed
y
bes
t
-first search
–
Ví dụ
(
1
)
y
()
7
Trí tuệ nhân tạo
Greedy bes
t
-first search
–
Ví dụ (2)
8
Trí tuệ nhân tạo
Greedy bes
t
-first search
–
Ví dụ (3)
9
Trí tuệ nhân tạo
Greedy bes
t

Không

–
Vì
có
thể
vư
ớng
(
chết
tắc
)

trong
các
v
òng
lặp
kiể
u
nh
ư:
Iasi Æ Neamt Æ Iasi Æ Neamt Æ…

Độ
phức
tạp
về
thời
gian

á
c
đị
n
h

(
c
h
o
đế
n
thời

điể
m
hiệ
n
t
ạ
i)

là
c
ó
c
hi
p
hí
cao

A
*
search
–
Ví dụ (2)
15
Trí tuệ nhân tạo
A
*
search
–
Ví dụ (3)
16
Trí tuệ nhân tạo
A
*
search
–
Ví dụ (4)
17
Trí tuệ nhân tạo
A
*
search
–
Ví dụ (5)
18
Trí tuệ nhân tạo
A
*

thái
,
thì

giải

thuật A* là hoàn chỉnh (tìm được lời giải) – nhưng không
đảm bảo là tối ưu
 Nếu không gian các trạng thái là hữu hạn và không có
giải pháp để tránh việc xét (lặp) lại các trạng thái, thì giải
* ỉ ( ả ả
thuật A
*
là không hoàn ch
ỉ
nh
(
không đ
ả
m b
ả
o tìm được
lời giải)
Nế
khô i á t thái là ô h
thì iảith ậtA*

Nế
u
khô

chấ
p
nhận được
g
p
 Một ướclượng (heuristic) h(n) đượcxemlàchấpnhận
được
nếu
đối
với
mọi
nút
n
:0
≤
h(n
)
≤
h
*
(n)
trong
đó
được
nếu
đối
với
mọi
nút
n

cách đường đithựctế
 Định lý: Nếu h(n) là đánh giá chấpnhận được, thì
phương pháp tìm kiếmA
*
sử dụng giảithuật TREE-
SEARCH
là
tối
ưu
SEARCH
là
tối
ưu
21
Trí tuệ nhân tạo
T
ính
t
ối ưu của A
*
-Chứn
g
minh (1)
g
 Giả sử có một đích không tối ưu (suboptimal goal) G
2
đượcsinhra
và
lưu
trong

cấu
trúc
fringe sao cho n nằmtrênmột đường đingắnnhất đếnmột đích tối
ưu (optimal goal) G

 Ta có: 1) f(G
2
) = g(G
2
)vìh(G
2
) = 0
 Ta có: 2) g(G
2
) > g(G) vì G
2
là đích không tối ưu
 Ta có: 3) f(G) = g(G) vì h(G) = 0
 Từ 1
)
+2
)
+3
)
su
y
ra: 4
)
f
(

Từ 5) suy ra: 6) g(n) + h(n) ≤ g(n) + h
*
(n)

Từ

5)

suy

ra:

6)

g(n)

+

h(n)

≤

g(n)

+

h
(n)
 Ta có: 7) g(n) + h
*

tí
ề
ị
tí
đú
c
h
uy
ể
nc
á
c
ô
c
hữ
n
ằ
msa
i
v
ị
t
r
í
v
ề
v
ị
t
r

(n) = số các ô chữ nằm ở sai vị trí (so vớivị trí củaô chữđấy ở
trạng thái đích)
 h
2
(n) = khoảng cách dịch chuyển(←,→,↑,↓) ngắnnhất để dịch
h ể
á
ô
hữ
ằ
i
ị
tí
ề
ị
tí
đú
c
h
uy
ể
nc
á
c
ô
c
hữ
n
ằ
msa

(S) = 3+1+
2+2+
2+2+
2+3+
3+2 = 18
25
Trí tuệ nhân tạo