BÀI TẬP TỰ HỌC
(Ơn tập thi kết thúc mơn)
Câu 1: Tính chi phí hành trình tốt nhất: (Thuật tốn GTS2)
1 2 3 4 5 6
1
∞
20 42 3
0
6 25
2 12
∞
1
6
7 33 19
3 23 5
∞
28 14 9
4 12 9 24
∞
31 15
5 1
4
7 21 15
∞
45
6 3
6
15 1
6
5 205
∞

Xanh đi
Đỏ đi
- Lưu ý: tuyến EC là một chiều.
Câu 5: Thuật tốn TACI (A
KT
)
Start
Tính vị trí sai trạng thái hiện tại so với trạng thái đích
Câu 6: Sử dụng giải thuật A
KT
để giải bài tốn tháp Hà Nội trong trường hợp n=3 với trạng
thái ban đầu và trạng thái kết thúc như sau:
A B C A B C
Câu 7: (Thuật tốn Vương Hạo)
a. Cho {p→q, q→r}. Kết luận: {p→r}
b. Cho {(a∧b) →c, (b∧c) →d, ¬d. CM: a→b
1 2 3
5 7 6
4 8
1 2 3
4 5 6
7 8
2
Goal
Câu 8: (Thuật tốn Robinson) (Mệnh đề đối ngẫu: P và ¬P)
a, Cho {p→q, q→r, r→s, p} Hỏi p∧s ?
b, Cho{a ∧ b →c, b ∧ c →d, a ∧ b}. Hỏi d ?
Câu 9:
Sử dụng thuật toán QuinLan để giải quyết bài toán sau:
Để xác đònh người châu Á hay người châu Âu khi xem xét một nhóm người căn cứ

Hình dáng Quyết đònh
1 Trung bình Đỏ Cầu Mua
2 Lớn Vàng Hộp Mua
3 Trung bình Xanh Trụ Không mua
4 Nhỏ Xanh Cầu Mua
5 Trung bình Xanh Nón Không mua
3
6 Nhoỷ Xanh Noựn Khoõng mua
7 Trung bỡnh ẹoỷ Truù Mua
Cõu 12 :
+ Cho mng ng ngha ỏp dng c ch suy din gii bi toỏn tam giỏc sau: Tớnh S
bit , , C
Xõy dng bng kớch hot ban u (1) Kớch hot cỏc yu t ó bit , , c (2)
Cõu 13:
Trỡnh by s khỏc nhau gia thut toỏn v thut gii Heuristics. Cho vớ d.
Cõu 14:
p dng nguyờn lý th t ca k thut heuristics trỡnh by t tng ca bi toỏn chia N
vt cú khi lng khỏc nhau thnh M nhúm u nhau. Gii bi toỏn chia 8 vt thnh 3 nhúm,
cỏc vt cú trng lng nh sau:
n1 = 28, n2 = 12, n3 = 36, n4 = 16, n5 = 23, n6 = 32, n7= 21, n8 = 15.
Cõu 15:
0
=++

=

sin
b
sin
a

a
b
c
P
S
h
c
4







=
j
j
ji
R
R
RX
i
i
X if 1
X if 0
Giải bài toán tìm đường đi từ điểm A đến điểm B trong đồ thị cho ở hình theo thuật giải leo
đồi dốc đứng.
Câu 16:
Áp dụng thuật giải Robinson, chứng minh tập mệnh đề sau:

G
E
K
14
10
12
11
9
13
15
8
0

Câu 19:
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
Bảng 1
Câu 20:
Áp dụng thuật toán Vương hạo, chứng minh bài toán sau:
p ∨ ¬q , (¬s ∨ ¬q) ∧ (r ∨s) , ¬p ∧ u ⇒ r ∨ u
6
0
E

16
5
7
6
18
12 15
10
8
13
12
12
8
10
Hình 1