TRÍ TUỆ NHÂN TẠO
ThS. Nguyễn Thị Thúy Loan
6/8/2010
Nguyễn Thị Thúy Loan 2
Cách đánh giá
 Thực hành: 30%
 Bài tập: 20%
 Lý thuyết: 50%
6/8/2010
Nguyễn Thị Thúy Loan 3
Tài liệu tham khảo
[1]. Bài giảng của Nguyễn Thị Thúy Loan
[2]. Trí tuệ nhân tạo, Đỗ Trung Tuấn, NXB Giáo
dục, 1998.
[3]. Bạch Hưng Khang – Hoàng Kiếm, Trí tuệ nhân
tạo, NXB KHKT - 1989.
[4]. Lập trình C cho TTNT, 3C soft (dịch), NXB Đại
học và Trung học chuyên nghiệp Hà nội –
1990.
[5]. Trang web
/>Engineering-and-Computer-Science/index.htm
6/8/2010
Nguyễn Thị Thúy Loan 4
NỘI DUNG
 Các thuật giải tô màu đồ thị.
 Các thuật giải tìm kiếm trên đồ thị.
 Biểu diễn và xử lý tri thức.
 Phân lớp.
ThS. Nguyễn Thị Thúy Loan
Chương I
CÁC THUẬT GIẢI TÔ

8
Thuật giải tô màu “Tối ưu”
Bước 1: [Tô màu] Tô màu i (i bắt đầu xét từ 1) cho đỉnh
có bậc lớn nhất.
Bước 2: [Hạ bậc & cấm tô]
2.1. Bậc của đỉnh được tô màu i thì bậc:=0.
2.2. Bậc của đỉnh có quan hệ với đỉnh được tô màu i thì
bậc:= bâc – 1.
2.3. Cấm tô màu i cho đỉnh có quan hệ với đỉnh được tô
màu i.
Bước 3: Lặp lại bước 1 cho đến khi tất cả các đỉnh đều
được tô màu.
8
6/8/2010
Nguyễn Thị Thúy Loan 9
9
Minh họa
9
d
b
p
c
e
h
aa
b
c
d
p
h

E 0 200 120 120
F 0 180 150
G 0 50
H 0
Giải quyết
6/8/2010
Nguyễn Thị Thúy Loan 12
12
2. Áp dụng thuật giải
để tô màu
12
Kết quả:
Giải quyết
6/8/2010
Nguyễn Thị Thúy Loan 13
13
Thuật giải tham lam (Greedy)
Bước 1:
i := 0
Bước 2:
i := i+1
Tô màu i cho tất cả các đỉnh có thể tô được.
Bước 3:
Lặp lại bước 2 cho đến khi tất cả các đỉnh
đều được tô màu.
13 14
Ví dụ
Cho ma trận bên

14

AF BE CE DE DF
i=3 3

i=3 3 3
  
CE DE DF
i=4 4

i=4 4

4
DE
i=5 5
6/8/2010
Nguyễn Thị Thúy Loan 15
15
Thuật giải sắp thứ tự +
tham lam
Bước 1:
Sắp xếp các đỉnh theo chiều giảm dần của
bậc.
i := 0
Bước 2:
i := i+1
Tô màu i cho tất cả các đỉnh có thể tô được (xét
từ trái sang).
Bước 3:
Lặp lại bước 2 cho đến khi tất cả các đỉnh đều
được tô màu.
15 16

i=3 3
 
i=3 3 3
  
i=3 3 3
 
3

DF EF BC
i=4 4

i=4 4

4
EF
i=5 5
6/8/2010
Nguyễn Thị Thúy Loan 17
17
Ví dụ
Một cuộc hội thảo có 9 chủ đề a, b, c, d, e, f, g,
h, i biết rằng các chủ đề sau không được phép
diễn ra trong cùng một buổi: ac, bde, adg, cdf,
dfg, egh, ghi.
Hãy sắp xếp các chủ đề vào các buổi sao cho số
buổi diễn ra là ít nhất.
17
6/8/2010
Nguyễn Thị Thúy Loan 18
18

Ref: />Phần 1
6/8/2010
Nguyễn Thị Thúy Loan 21
Nội dung
 Bài toán tìm kiếm
 Tìm kiếm Theo chiều Rộng
 Tìm kiếm Theo chiều Sâu
6/8/2010
Nguyễn Thị Thúy Loan 22
Bài toán tìm kiếm
Làm sao đi từ S đến G? Số bước đi ít nhất có thể
là bao nhiêu? Đi qua các đỉnh nào?
S
G
d
b
p
q
c
e
h
a
f
r
START
GOAL
6/8/2010
Nguyễn Thị Thúy Loan 23
Bài toán tìm kiếm
Một bài toán tìm kiếm gồm năm thành phần:

b
p
q
c
e
h
a
f
r
START
GOAL
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) = {}
cost(s,s’) = 1 cho tất cả các biến đổi
START
GOAL
d
b
p
q
c
e
h
a
f


n
à
o

g
i
ố
n
g

n
h
ư

v
ậ
y
?
Bài toán tìm kiếm
Các bài toán tìm kiếm
6/8/2010
Nguyễn Thị Thúy Loan 28
Các bài toán tìm kiếm
Lập lịch
8-Hậu
Gì nữa?
Giải toán
6/8/2010
Nguyễn Thị Thúy Loan 29

 v.v… cho đến khi đạt được trạng thái G hoặc
không còn đi tiếp được nữa.
6/8/2010
Nguyễn Thị Thúy Loan 32
Tìm kiếm theo chiều rộng
START
GOAL
d
b
p
q
c
e
h
a
f
r
0 bước từ
start
6/8/2010
Nguyễn Thị Thúy Loan 33
START
GOAL
d
b
p
q
c
e
h

Nguyễn Thị Thúy Loan 35
START
GOAL
d
b
p
q
c
e
h
a
f
r
0 bước từ
start
1 bước từ
start
2 bước từ
start
3 bước từ
start
Tìm kiếm theo chiều rộng
6/8/2010
Nguyễn Thị Thúy Loan 36
START
GOAL
d
b
p
q

r
6/8/2010
Nguyễn Thị Thúy Loan 38
Ghi nhớ đường đi!
Khi gán nhãn một trạng thái, ghi nhận trạng thái
trước đó. Ghi nhận này được gọi là con trỏ quay
lui. Lịch sử trước đó được dùng để phát sinh con
đường lời giải, khi đã tìm được đích:
“Tôi đã đến đích. Tôi thấy mình đã ở f trước đó.
Và tôi đã ở r trước khi tới f. Và…
…. do đó con đường lời giải là S  e  r  f 
G”
6/8/2010
Nguyễn Thị Thúy Loan 39
Con trỏ quay lui
START
GOAL
d
b
p
q
c
e
h
a
f
r
0 bước từ
start
1 bước từ

6/8/2010
Nguyễn Thị Thúy Loan 41
Tìm kiếm theo chiều rộng
Với bất kỳ trạng thái s nào đã gán nhãn, ghi nhớ:
 previous(s) là trạng thái trước đó trên đường đi
ngắn nhất từ trạng thái START đến s.
 Trong vòng lặp thứ k của thuật toán ta bắt đầu
với V
k
được định nghĩa là tập các trạng thái mà
từ trạng thái START đi đến có đúng k bước
6/8/2010
Nguyễn Thị Thúy Loan 42
 Sau đó, trong suốt vòng lặp, ta sẽ tính V
k+1
,
được định nghĩa là tập các trạng thái mà từ
trạng thái START đi đến có đúng k+1 bước
 Chúng ta bắt đầu với k = 0, V
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.
Tìm kiếm theo chiều rộng
6/8/2010
Nguyễn Thị Thúy Loan 43
START

V
1
BFS
6/8/2010
Nguyễn Thị Thúy Loan 45
START
GOAL
d
b
p
q
c
e
h
a
f
r
V
0
V
1
V
2
BFS
6/8/2010
Nguyễn Thị Thúy Loan 46
START
GOAL
d
b

r
V
4
V
0
V
1
V
2
V
3
BFS
6/8/2010
Nguyễn Thị Thúy Loan 48
START
GOAL
d
b
p
q
c
e
h
a
f
r
V
4
V
0

hú
n
g

t
a

l
ấ
y

đư
ợ
c

tr
ạ
ng

th
á
i

t
r
ư
ớ
c

m

h

k
há
c

c
h
o

B
FS
?
•
C
ó
thể
kh
ôn
g

c
ầ
n

ph
ả
i

l

Chi phí chuyển đổi
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
9
81
1
2
3
5
34
4
15
1
5
5
2
6/8/2010
Nguyễn Thị Thúy Loan 50

Rất nhỏ
(dù không tuyệt đối)
O(log(số mục trong hàng đợi ưu tiên))
6/8/2010
Nguyễn Thị Thúy Loan 53
UCS
 Một cách tiếp cận BFS đơn giản về mặt khái
niệm khi có chi phí chuyển đổi
 Dùng hàng đợi ưu tiên
PQ = Tập trạng thái đã được mở
Độ ưu tiên của trạng thái s là g(s) = chi phí đến
s sử dụng đường đi được cho bởi con trỏ quay
lui.
6/8/2010
Nguyễn Thị Thúy Loan 54
Bắt đầu UCS
PQ = { (s,0, null) }
START
GOAL
d
b
p
q
c
e
h
a
f
r
2

81
1
2
3
5
34
4
15
1
2
5
2
Lặp:
1. Lấy trạng thái có chi phí thấp
nhất từ PQ
2. Thêm các con vào PQ
Lặp UCS
n = (s,0)
PQ = { (p,1,s), (d,3,s), (e,9,s) }
START
GOAL
d
b
p
q
c
e
h
a
f

e
h
a
f
r
2
9
9
81
1
2
3
5
34
4
15
1
2
5
2
Lặp UCS
Lặp:
1. Lấy trạng thái có chi
phí thấp nhất từ PQ
2. Thêm các con vào PQ
n = (d,3)
PQ = { (b,4,d), (e,5,d), (c,11,d), (q,16,p) }
START
GOAL
d

1. Lấy trạng thái chi phí
thấp nhất từ PQ
2. Thêm các con
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
9
81
1
2
3
5
34
4
15
1
2
5
2

Lặp:
1. Lấy trạng thái chi phí
thấp nhất từ PQ
2. Thêm các con
n = (b,4)
PQ = { (e,5,d), (a,6,b), (c,11,d), (q,16,p) }
Lặp UCS
n = (e,5)
PQ = { (a,6,b),(h,6,e),(c,11,e),(r,14,e),(q,16,p) }
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
9
81
1
2
3
5
34

2
3
5
34
4
15
1
2
5
2
Lặp:
1. Lấy trạng thái chi phí
thấp nhất từ PQ
2. Thêm các con
Lặp UCS
n = (h,6)
PQ = {
(q,10,h), (c,11,e),(r,14,e) }
START
GOAL
d
b
p
q
c
e
h
a
f
r

e
h
a
f
r
2
9
9
81
1
2
3
5
34
4
15
1
2
5
2
Lặp:
1. Lấy trạng thái chi phí
thấp nhất từ PQ
2. Thêm các con
Lặp UCS
n = (q,10)
PQ = { (c,11,d),(r,14,e) }
START
GOAL
d

PQ = {(r,13,q) }
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
9
81
1
2
3
5
34
4
15
1
2
5
2
Lặp:
1. Lấy trạng thái chi phí thấp

5
2
Lặp:
1. Lấy trạng thái chi phí thấp
nhất từ PQ
2. Thêm các con
Lặp UCS
n =(f,18)
PQ = { (G,23,f) }
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
9
81
1
2
3
5
34

2
3
5
34
4
15
1
2
5
2
Lặp UCS
Lặp:
1. Lấy trạng thái chi phí thấp
nhất từ PQ
2. Thêm các con
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
9

f
r
2
9
9
81
1
2
3
5
34
4
15
1
2
5
2
Kết thúc UCS
Lặp:
1. Lấy trạng thái chi phí thấp
nhất từ PQ
2. Thêm các con
Biểu diễn cây tìm
kiếm
START
GOAL
d
b
p
q

iế
m

v
ớ
i
BF
S

t
h
e
o

t
h
ứ
t
ự
n
à
o
?
START
GOAL
d
b
p
q
c

a
f
r
Biểu diễn cây tìm
kiếm
START
GOAL
d
b
p
q
c
e
h
a
f
r
Là đích, dừng
Biểu diễn cây tìm
kiếm
Tìm kiếm theo chiều sâu
Một thay thế cho BFS. Luôn mở từ node vừa mới
mở nhất, nếu nó có bất kỳ node con nào chưa thử.
Ngược lại quay lại node trước đó trên đường đi.
START
GOAL
d
b
p
q

START d e r f
START d e r f c
START d e r f c a
START d e r f
GOAL
START
GOAL
d
b
p
q
c
e
h
a
f
r
Duyệt cây tìm kiếm DFS
Thứ tự mà trong đó các node của cây tìm kiếm
được viếng?
Là đích, dừng
6/8/2010
Nguyễn Thị Thúy Loan 80
Bài tập
ABCDEFG
A0100002
B0040030
C0008030
D3000300
E00000012

0
o Gán g(S
0
) = 0
2. Chọn đỉnh mở với hàm g là nhỏ nhất và
gọi là đỉnh n.
o Nếu u là đích thì đường đi từ S
0
 u là
đường đi ngắn nhất.
6/8/2010
Nguyễn Thị Thúy Loan 85
o Nếu tồn tại nhiều hơn một đỉnh n có hàm g
là nhỏ nhất thì ta kiểm tra xem trong đócó
đỉnh nào là đích hay không, nếu có dừng.
Nếu không thì chọn ngẫu nhiên 1 đỉnh gọi
là đỉnh u.
o Nếu không tồn tại đỉnh mở tương ứng thì
cây biểu diễn vấn đề không có đường đi
ngắn nhất đến đích. Dừng lại.
AT (Algorithm for Tree Search)
6/8/2010
Nguyễn Thị Thúy Loan 86
3. Đóng n và mở mọi đỉnh sau n (có cùng
hướng từ u đến)
o  đỉnh S sau n:
o G(s) = g(u) + giá thành (u s)// cost(u,s)
4. Lặp lại bước 2.
AT (Algorithm for Tree Search)
6/8/2010

0
Gán g(S
0
) = 0
Sử dụng tri thức bổ sung ước lượng h(S
0
)
F(S
0
) = h(S
0
)
6/8/2010
Nguyễn Thị Thúy Loan 89
Thuật giải A
KT
B2: Chọn đỉnh mở tương ứng với hàm f là
nhỏ nhất và gọi đỉnh này là đỉnh n.
 Nếu n là đích thì đường đi từ S
0
 n là
đường đi ngắn nhất đến đích nên dừng
(thành công).
 Nếu không tồn tại đỉnh mở tương ứng nào
thì cây biểu diễn vấn đề không có đường
đi đến đích nên dừng (thất bại).
6/8/2010
Nguyễn Thị Thúy Loan 90
Thuật giải A
KT

Nguyễn Thị Thúy Loan 94
g = 0
h = 3
f = 3
g = 1
h = 3
f = 4
g = 1
h = 4
f = 5
g = 2
h = 4
f = 6
g = 2
h = 4
f = 6
X
Với N = 3
6/8/2010
Nguyễn Thị Thúy Loan 95
g = 0
h = 3
f = 3
g = 1
h = 3
f = 4
g = 1
h = 4
f = 5
g = 2, h = 4,f = 6

B2: Chọn đỉnh trong O với hàm f là n hỏ
nhất và gọi là đỉnh n.
 Nếu n là đích thì đường đi từ S
0
 n là
đường đi ngắn nhất đến đích nên dừng
(thành công).
 Nếu không tồn tại đỉnh mở tương ứng nào
thì cây biểu diễn vấn đề không có đường
đi đến đích nên dừng (thất bại).
6/8/2010
Nguyễn Thị Thúy Loan 98
Thuật giải A
*
 Nếu tồn tại nhiều hơn 1 đỉnh mở cùng
hàm f là nhỏ nhất thì kiểm tra xem trong
số này có đỉnh nào là đích hay không?
Nếu có thì dừng, nếu không thì chọn ngẫu
nhiên 1 đỉnh gọi là đỉnh n.
 O = O – {n}
 C = C + {n}
6/8/2010
Nguyễn Thị Thúy Loan 99
Thuật giải A
*
B3:
đỉnh S sau n:
 g(S) = g(n) + chi phí từ n đến S
 Sử dụng tri thức bổ sung ước lượng h(S)
 f(S) = g(S) + h(S)