Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
Đề 1
Câu 1.(3đ)
Trình bày sự khác nhau giữa thuật toán và thuật giải Heuristics. Hãy nêu 1 ví dụ về
thuật giải Heuristics
Câu 2.(7đ)
a. Trình bày thuật giải Robinson.
b. Áp dụng thuật giải Robinson, chứng minh bài toán sau:
¬p ∨ q , (s ∨ ¬ q) ∧ (r ∨ ¬s) , p ∧ u ⇒ r, u
c. Hãy xây dựng cây định danh và tìm luật theo phương pháp vector đặc trưng của
Quinlan để xác định một loại quả độc hay không độc theo bảng số liệu sau.
Tên Vị Màu Vỏ Độc
A Ngọt Đỏ Nhẵn không
B Cay Đỏ Nhẵn không
C Chua Vàng Có gai Không
D Cay Vàng có gai Độc
E Ngọt Tím Có gai Không
F Chua Vàng Nhẵn Không
G Ngọt Tím Nhẵn Không
H Cay Tím có gai Độc
Đề 2 (có giải) trang 13)
Câu 1(3 đ)
Trình bày khái niệm hàm heuristics.: Xây dựng hàm đánh giá h cho bài toán ở bảng
1 để giải bài toán TACI sau:
3 2 6 1 2 3
1 5 4 8 4
7 8 7 6 5
T
i
T
G

20
12
14
13
17
9
20
11
9
17
10
16
5
7
6
18
12
15
10
8
13
12
12
8
10
Hình 1
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
Đề 3
Câu 1 (3đ)
a. Trình bày thuật giải Vương Hạo.

1 Nắng Cao Nhẹ Không
2 Mưa Thấp Mạnh Không
3 Râm mát TB Nhẹ Được
4 Nắng TB Mạnh Không
5 Mưa Cao Mạnh Không
6 Râm mát Thấp Mạnh Được
- k2cn4.n-stars.org – 4rum K2CN4
L E Y
O U
Q D N
L E
Q U Y
D O N
2
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
7 Mưa TB Nhẹ Không
8 Nắng TB Nhẹ Được
9 Mưa Thấp Nhẹ Không
Xác định điều kiện như thế nào để tổ chức Được hay Không buổi picnic ?(Dùng thuật
toán Quinlan)
Đề 5:
BÀI 1:(3 ĐIỂM)
Giả sử có 9 cuộc minting a,b,c,d,e,f,g,h,i được tổ chức. Mỗi cuộc mitting được tổ chức
trong một buổi. Các cuộc mitting sau không được diễn ra đồng thời:
ae,bc,cd,ed,abd,ahi,bhi,dfi,dhi,fgh. Hãy sử dụng thuật toán tô màu tối ưu để bố trí các
cuộc mitting vào các buổi sao cho số buổi diễn ra là ít nhất.
BÀI 2: (3 ĐIỂM)
Cho đồ thị có ma trận chi phí như sau
Hãy sử dụng thuật giải GTS2 để tìm hành trình tốt nhất với p = 4 (v1=1, v2=2, v3=4,
v4=6.

∞
31 15
14 7 21 15
∞
45
6 36 15 16 5 205
∞
3
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
8 To Trung bình Nữ Châu Âu
- k2cn4.n-stars.org – 4rum K2CN4 4
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
Đề 6
BÀI 1.:(3 ĐIỂM)
Sử dụng Thuật giải A
KT
– Tìm kiếm với tri thức bổ sung (Algorthm for
Knowled geable Tree Search) để giải bài toán Taci theo các trạng thái:
2 8 3
1 6 4
7 5
Trạng thái đầu Trạng thái đích
BÀI 2.:(3 ĐIỂM)
Hãy sử dụng thuật giải A* để tìm đường đi ngắn nhất từ thành phố A đến
thành phố B biết khoảng cách ước lượng từ các thành phố đến thành phố B
được cho như sau:
Đỉnh khoảng cách ước lượng
Z 374
A 366
T 329

B
F
R
S
75
118
70
151
99
120
100
146
80
140
110
60
97
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
Đề 7
BÀI 1:(3 ĐIỂM)
Sử dụng thuật toán A* cho bài toán tháp Hà Nội:
Cho 3 cọc A,B,C. ở cọc A ban đầu có n đĩa sắp xếp theo thứ tự có kích
thước lớn dần từ trên xuống. Hãy dịch chuyển n đĩa đó sang cọc C sao cho:
-Mỗi lần chỉ được di chuyển chỉ 1 đĩa.
-Trong mỗi cọc không cho phép đĩa có kích thước lớn trên đĩa có kích thước
nhỏ hơn.
BÀI 2: (3 ĐIỂM)
Sử dụng Thuật toán Vương Hạo giải bài toán sau:
Ví dụ: Chứng minh rằng: Minh là sinh viên của ĐHKHTN. Biết:
- Minh là sinh viên ngành công nghệ thông tin.

(i) {p->q,q->r,r->s,p}
Hỏi: p^s?
(ii) {a^b->c,b^c->d,a^b}
Hỏi d?
BÀI 3.:(4 ĐIỂM)
Sử dụng phương pháp độ đo hỗn loạn để giải bài toán sau:
Theo bảng dữ liệu xác định hiệu quả của việc sử dụng kem cháy nắng
Tên Màu tóc Chiều cao Cân nặng Dùng kem Kết quả
1. Sarah Vàng Trung bình Nhẹ Không Cháy nắng
2. Dana Vàng Cao Trung bình Có Không cháy nắng
3. Alex Nâu Lùn Trung bình Có Không cháy nắng
4. Annie Vàng Lùn Trung bình Không Cháy nắng
5. Emily Đỏ Trung bình Nặng Không Cháy nắng
6. Pete Nâu Cao Nặng Không Không cháy nắng
7. John Nâu Trung bình Nặng Không Không cháy nắng
8. Katie Vàng Lùn Nhẹ Có Không cháy nắng
- k2cn4.n-stars.org – 4rum K2CN4
1 2 3
5 7 6
4 8
7
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
ĐỀ 9
BÀI 1:(3 ĐIỂM)
(1) Phân công, lịch công tác, lịch thi đấu:
- Có một cuộc hội thảo khoa học với 9 chủ đề khác nhau, mỗi chủ đề diễn ra
trong một buổi.
- Các chủ đề sau không được đồng thời: AE, BC, CD, ED, ABD, AHI, BHI,
DFI, DHI, FGH.
- Xây dựng lịch sao cho số buổi diễn ra là ít nhất.

thành 3 nhóm, các vật có trọng lượng như sau:
n1 = 28, n2 = 12, n3 = 36, n4 = 16, n5 = 23, n6 = 32, n7= 21, n8 = 15.
c. Trình bày tư tưởng và mã giả của thuật giải leo đồi.
d. Giải bài toán tìm đường
đi từ điểm A đến điểm B
trong đồ thị cho ở hình 1
theo thuật giải leo đồi dốc
đứng.
Câu 2.
a. Trình bày thuật giải Robinson.
b. Áp dụng thuật giải Robinson, chứng minh tập mệnh đề sau:
¬p ∨ q , (s ∨ ¬ q) ∧ (r ∨ ¬s) , p ∧ u ⇒ r, u
c. Hãy xây dựng cây định danh và tìm luật theo phương pháp vector đặc trưng của
Quinlan để xác định một loại quả độc hay không độc theo bảng số liệu sau.
Tên Vị Màu Vỏ Độc
A Ngọt Đỏ Nhẵn không
B Cay Đỏ Nhẵn không
C Chua Vàng Có gai Không
D Cay Vàng có gai Độc
E Ngọt Tím Có gai Không
F Chua Vàng Nhẵn Không
G Ngọt Tím Nhẵn Không
H Cay Tím có gai Độc
- k2cn4.n-stars.org – 4rum K2CN4 9
B
C
F
D
IE
K

heuristics, đó là các quy tắc thô, phương pháp, chiến lược hay mẹo rút ra từ kinh nghiệm
để giải quyết một vấn đề. Giải bài toán bằng thuật giải heuristics dễ dàng đưa ra lời giải
nhưng có thể không phải là lời giải tối ưu.
b. Chia N vật có khối lượng khác nhau thành M nhóm có khối lượng đều nhau bằng
nguyên lý thứ tự. (1,0 điểm)
* Tư tưởng: ( 0,25điểm)
1. Sắp xếp N vật theo thứ tự có khối lượng giảm dần;
2. Lặp lại cho đến khi không còn vật nào
2.1. Chọn nhóm M
i
có khối lượng các vật là nhỏ nhất
2.2. Đặt vật N
j
có khối lượng lớn nhất vào nhóm M
i
.
2.3. Tính lại khối lượng của các nhóm.
* Áp dụng: (0,75 điểm)
1. Sắp xếp các vật theo thứ tự trọng lượng giảm dần.
n3=36, n6 = 32, n1 = 28, n5 =23, n7=21, n4=16, n8=15, n2=12.
2. Chọn
Lần lặp 1:
- Chọn nhóm M1, đặt n3 vào nhóm M1
- Tính khối lượng của các nhóm: M1:36, M2:0, M3:0.
Lần lặp 2:
- Chọn nhóm M2, đặt n6 vào nhóm M2
- Tính khối lượng của các nhóm: M1:36, M2:32, M3:0.
Lần lặp 3:
- Chọn nhóm M3, đặt n1 vào nhóm M3
- Tính khối lượng của các nhóm: M1:36, M2:32, M3:28.

2.2.2. Nếu T
k
không phải là trạng thái kết thúc nhưng tốt hơn trạng thái
hiện hành thì cập nhật T
k
thành trạng thái hiện hành.
2.2.3. Nếu T
k
không tốt hơn trạng thái hiện hành thì tiếp tục vòng lặp.
* Mã giả (0,5 điểm):
T
i
:= T
0
; stop:=false;
While stop = false do
Begin
If T
i
≡T
G
then Begin <tìm được kết quả>; stop:=true; End
else
Begin
Better:=false;
While (Better=false) And (stop=false) do
Begin
If <không tồn tại trạng thái kế tiếp hợp lệ của T
i
> then

Bước 3> Chọn I để phát tiển được B, G. Trong
2 trạng thái hợp lệ của I, B là trạng thái tốt
hơn, đồng thời B là tạng thái đích nên thuật
giải kết thúc. Cây tìm kiếm như hình bên.
- k2cn4.n-stars.org – 4rum K2CN4 11
B
C
F
D
I
E
K
G
H
I
A
G
E
10
12
11
9
13
15
0
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
Câu 2 (2,0 điểm)
a. Phát biểu thuật giải Robinson. (0,5 điểm)
Thuật giải Robinson hành động dựa trên phương pháp chứng minh bằng phản
chứng.

, GT
2
, ,GT
n
,¬ KL
1
, ¬KL
2
, , ¬KL
m

b4: Nếu trong danh sách mệnh đề ở b3 có mệnh đề đối ngẫu thì mệnh đề được
chứng minh. Ngược lại thì chuyển sang b5.
b5: Xây dựng một mệnh đề mới bằng cách tuyển một cặp mệnh đề trong danh sách
mệnh đề. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu thì loại bỏ các biến đó.
b6. Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng mệnh đề mới.
b7. Nếu không xây dựng được thêm một mệnh đề mới nào và trong danh sách mệnh
đề không có hai mệnh đề nào đối ngẫu nhau thì vấn đề không được chứng minh. Nếu
danh sách mệnh đề không còn mệnh đề nào (danh sách rỗng:Φ), vấn đề được chứng
minh.
b. Áp dụng thuật giải, chứng minh tập mệnh đề sau: (0,5 điểm)
¬p ∨ q , (s ∨ ¬ q) ∧ (r ∨ ¬s) , p ∧ u ⇒ r, u
¬p ∨ q , s ∨ ¬ q, r ∨ ¬s , p , u ⇒ r, u
¬p ∨ q , s ∨ ¬ q, r ∨ ¬s , p , u, ¬r,¬ u
(¬p ∨ q , s ∨ ¬ q), r ∨ ¬s , p , u, ¬r,¬ u
(¬p ∨ s, r ∨ ¬s) , p , u, ¬r,¬ u
(¬p ∨ r , p) , u, ¬r,¬ u
(r ∨ ¬r), u, ¬ u
u, ¬ u = Φ
Danh sách mệnh đề trở thành danh sách rỗng, vấn đề được chứmg minh.

Vỏ
(gai)=(T(gai, độc), T(gai, không độc)) = (3/4, 1/4).
Các thuộc tính vỏ, thuộc tính màu có 1 vector đơn vị, thuộc tính vị có 2 vector đơn
vị vậy ta chọn thuộc tính vị là thộc tính phân hoạch, quả gạch chân là quả có độc (hình a).
Còn lại tập P
Cay
còn lẫn lộn quả độc và không độc, tiếp tục phân hoạch thành các
tập con theo hai thuộc tính màu và vỏ:
- Thuộc tính màu: V
Màu
(đỏ) = (T(đỏ, độc), T(đỏ, không độc)) = (0/1, 1/1).
V
Màu
(vàng) = (T(vàng, độc), T(vàng, không độc)) = (1/1,
0/1).
V
Màu
(tím) = (T(tím, độc), T(tím, không độc)) = (1/1, 0/1).
- Thuộc tính vỏ: V
Vỏ
(Có gai)=(T(Có gai, độc), T(Có gai , không độc)=(2/2, 0/2)
V
Vỏ
(Nhẵn)=(T(Nhẵn, độc), T(nhẵn , không độc)=(0/1, 1/1)
Thuộc tính vỏ có 2 vector đơn vị, vậy ta chon thuộc tính này làm vector phân hoạch
tiếp được cây định danh như (hình b).
Từ cây đinh danh ta có thể suy ra hệ luật như sau:
1. Quả có vị ngọt và quả có vị chua không độc;
2. Quả có vị cay vỏ nhẵn không độc;
3. Quả có vị cay và có gai độc.

) là
số đo sự đánh giá về trạng thái T
i
, hay chi phí để đi từ trạng thái T
0
đến trạng thái đích T
G
.
Hàm h(T
i
) là hàm thực dương, trong quá trình tìm kiếm giá trị hàm h(T
i
) sẽ giảm dần. Tại
trạng thái đích h(T
G
) = 0.
Trong bài toán Tacanh (8 số) có 2 cách xây dựng hàm đánh gía h(T
i
).
3 2 6 1 2 3
1 5 4 8 4
7 8 7 6 5
T
i
T
G
Hàm h
1
: với mỗi trạng thái T
i

max
trong OPEN sao cho f(T
max
) là nhỏ nhất.
2.2.1. Lấy T
max
ra khỏi OPEN và đưa T
max
vào CLOSE.
2.2.2. Nếu T
max
là

T
G
thì thoát, thông báo lời giải là T
max
2.2.3. Nếu T
max
không phải T
G
, tạo danh sách tất cả các trạng thái kế tiếp của
T
max
. Gọi một trạng thái này là T
k
. vơi mỗi T
k
thực hiện các bước sau:
2.2.3.1. Tính g(T

k'
trong CLOSE trùng T
k
Nếu g(T
k
)<g(T
k'
) thì
Đặt g(T
k'
)=g(T
k
)
Tính lại f(T
k'
)
Đặt Cha(T
k'
) = T
max
Lan truyền sự thay đổi giá trị g, f cho tất cả các trạng thái
kế tiếp của T
i
(ở tất cả các cấp) đã được lưu trữ trong
CLOSE và OPEN.
2.3.3.4. Nếu T
k
chưa xuất hiện trong cả OPEN và CLOSE thì
Thêm T
k

OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42), (E, 20, 24, 44), (K, 33,
14,47), (B,31,0, 31)}
B4: Trong OPEN B là đỉnh tốt nhất, nên đặt B vào CLOSE, loại B khỏi OPEN.
OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42), (E, 20, 24, 44), (K, 33,
14,47)}
CLOSE = {(A, g=0, h=0, f=0), (D, 12, 20, 32 ), (H, 22, 16, 38), (B,31,0, 31) cha(B)
= H }
Vậy đường đi ngắn nhất từ A đến B tìm được là A
→
D→H→B với g(B) = 31.
Cây tìm kiếm có dạng như sau:
Câu 2. (2điểm)
a. Thuật giải Vương Hạo (0,5 điểm).
b1: Phát biểu lại giả thiết và kết luận của vấn đề theo dạng chuẩn sau:
GT
1
, GT
2
, ,GT
n
⇒ KL
1
, KL
2
, ,KL
m
Trong đó các GT
i
và KL
j

b3: Nếu GT
i
có phép ∧ thì thay bằng dấu",". Nếu KL
j
có dấu ∨ thì thay bằng dấu
",".
b4: Nếu GT
i
có phép ∨ thì tách thành 2 dòng con. Nếu KL
j
có phép ∧ thì tách thành
2 dòng con.
b5: Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở cả hai phía.
b6a: Nếu một dòng không còn phép nối ∧ hoặc phép hoặc ∨ ở cả hai vế và ở cả hai
vế không có chung một biến mệnh đề, thì dòng đó không được chứng minh.
b6b: một vấn đề được chứng minh nếu tất cả các dòng dẫn xuất từ dạng chuẩn ban
đầu đều được chứng minh.
b. Chứng minh tập mệnh đề: (0,5 điểm)
p ∨ ¬q , (¬s ∨q) ∧ (r ∨s) , ¬p ∧ u ⇒ r ∨ u
⇔ p ∨ ¬q , ¬s ∨ q, r ∨s , ¬p , u ⇒ r, u
⇔ p ∨ ¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p
⇔ p ∨ ¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p
Tách phép ∨: (p ∨ ¬q) thành 2 dòng con
1: p, ¬s ∨ q, r ∨s , u ⇒ r , u, p (đcm vì có mệnh đề p ở hai phía)
2:¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p ⇔ ¬s ∨ q, r ∨s , u ⇒ r , u, p, q
Tách phép ∨ : ¬s ∨ q thành 2 dòng con
2.1: q, r ∨s , u ⇒ r , u, p, q (đcm vì có mệnh đề q ở hai phía)
2.2: ¬s , r ∨s , u ⇒ r , u, p, q ⇔ r ∨s , u ⇒ r , u, p, q, s
Tách phép ∨: r ∨ s thành 2 dòng con
2.2.1: s , u ⇒ r , u, p, q, s (đcm vì có s, u ở cả hai phía)

A
(j) được gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần
có giá trị 1 và các thành phần khác có giá trị 0.
Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất.
Sau khi phân hoạch xong, ta xây dựng cây định danh. Căn cứ vào cây định danh,
phát sinh và ối ưu tập luật.
- k2cn4.n-stars.org – 4rum K2CN4 16
(tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất
A là j và có giá trị thuộc tính mục tiêu là r
i
)
T(j,r
i
)=
(tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j)
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4
Luật Morgan
Phủ định của phủ định
¬ (¬P) ≡ P
(P⇒Q) ≡ (¬P ∨ Q)
Tương phản
(P⇒Q) ≡ (¬ P⇒ ¬ Q)
De Morgan
¬(P ∨ Q) ≡ (¬P ∧ ¬Q)
¬ (P ∧ Q) ≡ (¬P ∨ ¬ Q)
Giao hoán
(P ∧ Q) ≡ (Q ∧ P)
(P ∨ Q) ≡ (Q ∨ P)
Kết hợp
(P ∧ Q) ∧ R ≡ (P ∧(Q ∧ R))