Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang
[email protected]
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
 Logic và suy diễn
 Biểu diễn tri thức
 Biểu diễn tri thức không chắc chắn

Họcmáy

Học

máy
2
Trí tuệ nhân tạo
Ràn
g
bu
ộ
c
g ộ
 Một ràng buộc (constraint) là một quan hệ trên một tập các biến
 Mỗi biến có
(g
ắn với


gán

giá

trị

phù

hợp

cho

các

biến
 Ví dụ về ràng buộc
 Tổng các góc trong một tam giác là 180
o

Đ
ộ dài của từ W là 10 ký tự
 X nhỏ hơn Y
 Tuấn có thể tham dự buổi seminar vào thứ 4 sau 14h
 …
3
Trí tuệ nhân tạo
Bài toán thỏa mãn ràn
g
bu

bài

toán

thỏa mãn ràng buộc là một phép
gán đầy đủ các giá trị của các
biến sao cho thỏa mãn tất cả các
Ví
dụ:
Các biến x1,…,x6.
Miềngiátrị {0,1}.
Các
ràng
buộc
:
ràng buộc
 Một bài toán thỏa mãn ràng buộc
thườn
g
được biểu diễn bằn
g
một
Các

ràng
buộc
:
•x
1
+x

 Các biến: WA, NT, Q, NSW,
V, SA, T
V,

SA,

T
 Các miềngiátrị: D
i
= {red,
green, blue}

Các
ràng
buộc
:Các
vùng
liền

Các

ràng
buộc
:

Các

vùng
liền
kề nhau phải có màu khác

gán

đầy

đủ
và

chính

xác
(thỏa mãn tất cả các ràng
buộc)
 Ví dụ: WA=red,
NT=green, Q=red,
S
N
S
W=green, V=red,
SA=blue, T=green
Đồ thị các ràn
g
buộc
g

Đ
ối với bài toán thỏa mãn
ràng buộc nhị phân (binary
CSP): Mỗi ràng buộc chỉ
liên quan đến2biến
liên

)
 Ví dụ: Các bài toán thỏa mãn ràng buộc nhị phân (Boolean CSPs)
Các miềngiátrị vô hạn

Các

miền

giá

trị

vô

hạn
 Miền giá trị các số nguyên, các chuỗi,
 Ví dụ: Trong bài toán xếp lịch công việc, các biến là các ngày bắt
đầu và kết thúc đối với mỗi côn
g
vi
ệ
c
g ệ
 Cần một ngôn ngữ biểu diễn ràng buộc (constraint language), ví dụ:
StartJob
1
+ 5 ≤ StartJob
3
 Các biến liên tục
 Ví dụ: Các mốc thời gian bắt đầu và kết thúc đối với các quan


constraint)

liên

quan

đến

2

biến
 Ví dụ: SA ≠ WA
 Ràng buộc bậc cao (higher-order constraint) liên quan
đến nhiều hơn 2 biến
ố
 Ví dụ: Các ràng buộc trong bài toán mật mã s
ố
học (trình bày ở
slide tiếp theo)
9
Trí tuệ nhân tạo
Ví dụ: Bài toán mật mã số học
 Các biến: F T U W R O X
1
X
2
X
3
(các nhớ của các phép +)

3
 X
3
= F
 T ≠ 0

F
≠
0

F
≠
0
10
Trí tuệ nhân tạo
Các bài toán CSP tron
g
thực
t
ế
g
 Các bài toán giao nhiệm vụ
 Ví
dụ
:
G
i
áo
vi
ê

tế

liên

quan

đến

các

biến có giá trị thực (liên tục)
11
Trí tuệ nhân tạo
Tìm kiếm bằn
g
kiểm thử
(
1
)
g ()
 Là phương pháp giải quyếtvấn đề tổng quát nhất
 Phương pháp giải quyếtbằng kiểmthử (Generate and
Test)
Sinh
ra
một
khả
năng
(candidate)
của

d
ụng p
h
ương p
há
p
kiể
m
thử
đối
v
ới
bài
t
o
á
n
CSP
 Bước 1. Gán các giá trị cho tấtcả các biến
 Bước 2. Kiểmtraxemtấtcả các ràn
g
bu
ộ
c đư
ợ
cthỏa mãn ha
y

g
ộ

nhiều

các

khả

năng

gán

(hiển nhiên) không thỏa mãn các ràng buộc

Ví dụ

Ví

dụ
 Các biến X,Y,Z lấy các giá trị {1,2}
Các ràng b ộcXYX
ZY>Z

Các

ràng

b
u
ộc
:
X

,
2
,
1)
13
Trí tuệ nhân tạo
Tìm kiếm bằn
g
kiểm thử
(
3
)
g ()
 Làm thế nào để cải thiện phương pháp kiểm thử?
Si h á khả ă (á hé á iátị) ộtáh

Si
n
h
ra c
á
c
khả
n
ă
ng
(
c
á
c p

tự
 Sử dụng các kết quả (thông tin) thu được từ bước
kiểm tra (bước 2)
 Phát hiện sớm (từ trước) các mâu thuẫn
 Các ràng buộc được kiểm tra ngay sau khi mỗi biến
được gán giá trị (chứ không phải đợi đến khi tất cả
các biến được gán giá trị)
14
Trí tuệ nhân tạo
Tìm kiếm
q
ua
y
lui
(
1
)
qy ()
 Tìm kiếm quay lui (backtracking) là giải thuật tìm kiếm
đượcsử dụng phổ biếnnhất trong CSP
được

sử

dụng

phổ

biến


h
c
á
c g
iá

t
r
ị
c
h
o
tất

cả các biến)

Phương pháp tìm kiếm quay lui đốivới bài toán CSP

Phương

pháp

tìm

kiếm

quay

lui


, ki
ể
m tra c
á
c r
à
ng
buộc có được thỏa mãn bởi tất cả các biến đã được gán giá trị
cho đến thời điểm hiện tại – Quay lui (backtrack) nếu có lỗi
(không thỏa mãn các ràng buộc)
(không

thỏa

mãn

các

ràng

buộc)
15
Trí tuệ nhân tạo
Tìm kiếm
q
ua
y
lui
(
2

(
được
định
nghĩa
tùy
vào
bài
toán cụ thể)
 Ưutiênxéttrước các biến có ít giá trị (miềngiátrị nhỏ)
Ưu
tiên
xét
trước
các
biến
tham
gia
vào
nhiều
ràng
buộc

Ưu

tiên
xét
trước
các
biến


i
ế
n
được
đị
nh n
g
hĩ
a
tùy
ứ
tự
ưu
tê
của
các
gá
t ị
ớ
ỗ
b ế
được
đị
g a
tùy
thuộc vào bài toán cụ thể
16
Trí tuệ nhân tạo
Giải thuật tìm kiếm
q

Trí tuệ nhân tạo
T
ìm kiếm
q
uay lui
–
Ví dụ (4)
q
21
Trí tuệ nhân tạo
Tìm kiếm quay lui – Các vấn đề (1)
 Lặp đi lặp lại lỗi
Lý d Bỏ (khô kh i thá ) lý d ủ âthẫ

Lý

d
o:
Bỏ
qua
(khô
ng
kh
a
i

thá
c
)


y c
á
c g
iá

t
r
ị

t
rong m
iề
n
1

10
 Ràng buộc: A>E

Phương pháp tìm kiếm quay lui thử tấtcả các khả

Phương

pháp

tìm

kiếm

quay


 Các ràng buộc: B+8<D; C=5*E
Khi gán giá trị cho các biếnCE thìcácgiátrị 19

Khi

gán

giá

trị

cho

các

biến

C
,
E
,
thì

các

giá

trị

1

 Các vi phạm ràng buộc chỉ được phát hiện sau khi các
giá trị được gán
Ví d

Ví

d
ụ:
 Các biến A,B,C,D,E lấy các giá trị trong miền 1 10

Ràng buộc: A=3
*
E

Ràng

buộc:

A=3 E
 Chỉ đến khi gán giá trị cho biến E thì mới phát hiện
ra rằng A>2
 Giải pháp: Phương pháp Forward checking (kiểm tra
trước các ràng buộc)
24
Trí tuệ nhân tạo
Tìm kiếm quay lui – Cải thiện
 Hiệu quả của phương pháp tìm kiếm quay lui trong CSP
có thể đượccảithiệnbằng
có


ị

đối
v
ới
m
ỗi

biế
n
 Phát hiện sớm các lỗi (vi phạm ràng buộc) sẽ xảy ra
25
Trí tuệ nhân tạo