Bài giảng Trí tuệ nhân tạo - Chương 3: Kỹ thuật giải quyết vấn đề - Lê Thanh Hương

1Chương 3 
Kỹ thuật giải quyết vấn đề
Lê Thanh Hương
1
Khoa CNTT – ĐHBKHN
3.1. Khoa học TTNT
• TTNT quan tâm đến việc tạo ra các đối 
tượng có thể
– Hành động đúng
– trên cơ sở hoàn cảnh cụ thể và những thứ 
mà nó đã biết
2Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.2. Phân loại vấn đề
• GQVĐ là quá trình xuất phát từ hình trạng đầu, tìm 
kiếm trong không gian bài toán để tìm ra dãy toán tử
hay dãy hành động cho phép dẫn tới đích.
• BT phát biểu chỉnh: là BT biết rõ đầu vào, đầu ra và 
với mỗi lời giải giả định nào đó, có thể áp dụng thuật 
toán để xác định xem đó có phải là lời giải của BT 
ban đầ ha không
3
 u y .
• BT phát biểu không chỉnh: ngược lại
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.2. Phân loại vấn đề
BT phát biểu chỉnh BT phát biểu không chỉnh
ĐPT đa thức ĐPT hàm mũ
O(nα) O(αn)
giải được ko giải được
4Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Giải thuật Mẹo giải
2Ví dụ 1. Bài toán đố chữ
• Hãy thay các chữ cái bằng các chữ số 
từ 0 đến 9 sao cho không có hai chữ cái 
nào được thay bởi cùng 1 số và thỏa 
mãn ràng buộc sau:
SEND CROSS
5
+ MORE + ROADS
MONEY DANGER
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 2. Bài toán rót nước
• Cho 2 bình A(m lít), B(n lít). Làm cách nào để đong 
được k lít ( k ≤ max(m,n) ) chỉ bằng 2 bình A, B và 1 
bình trung gian C . 
• Các thao tác rót (how):
C Æ A; C Æ B; A Æ B; A Æ C; B Æ A; B Æ C
• Điều kiện: không tràn, đổ hết
• Ví dụ: m = 5, n = 6, k = 2 (what)
Mô hì h t á h
6
• n o n ọc: 
(x, y) Æ (x’, y’)
A B A B
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 3. Bài toán trò chơi n2 – 1 số
• Trong bảng ô vuông n hàng, n cột, mỗi ô chứa 1 số 
nằm trong phạm vi từ 1 Æ n2 -1 sao cho không có 2 ô 
ó ù iá t ị Cò đú 1 ô bị t ố X ất hát từ 1c c ng g r . n ng r ng. u p 
cách sắp xếp nào đó của các đó của các số trong 
bảng, hãy dịch chuyển các ô trống sang phải, sang 
trái, lên trên, xuống dưới để đưa về bảng:
7Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 4. Bài toán tháp Hà Nội
• Cho 3 cọc 1 2 3 Ở cọc 1 ban đầu có n đĩa sắp theo , , . , 
thứ tự to dần từ trên xuống dưới. Hãy tìm cách 
chuyển n đĩa đó sang cọc 3 sao cho:
– Mỗi lần chỉ chuyển 1 đĩa
– Ở mỗi cọc không cho phép đĩa to nằm trên đĩa con
8
1 2 3 1 2 3
Bài toán tháp Hà Nội với n = 3
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3Ví dụ 5. Bài toán đố: Quan tòa - Hề - Trộm
• Có 3 người ngồi quanh 1 bàn tròn. Một người 
qua đường nghe thấy ba người này nói chuyện 
ới hv n au:
– người 1 nói 2 là quan tòa
– người 2 nói 3 là hề
– người 3 nói 1 là trộm
• Biết rằng:
– hề luôn nói đùa
9
– quan tòa nói thật
– trộm nói dối
• Hỏi ai là ai?
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Các đặc trưng cơ bản của vấn đề
• Bài toán có thể phân rã? 
• Không gian bài toán có thể đoán trước?
• Có tiêu chuẩn xác định lời giải tối ưu?
• Có cơ sở tri thức phi mâu thuẫn?
• Tri thức cần cho quá trình tìm kiếm hay
10
để điều khiển?
• Có cần tương tác người – máy?
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.3.Những yếu tố cơ bản trong GQVĐ
Bài toán
ể ễBi u di n + Tri thức
CSDL CSTT
Giải thuật 
tìm kiếm
Chiến lược 
điều khiển
Kỹ thuật 
Heuristic
Kỹ thuật 
suy diễn
Hệ thống giải quyết vấn đề
11
Cấu trúc các hệ thống giải quyết vấn đề
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.4.Các phương pháp biểu diễn vấn đề
n Biểu diễn nhờ KGTT
• Mỗi hình trạng của bài toán tương ứng với 1 trạng 
thái (state)
• Mỗi phép biến đổi từ hình trạng này sang hình trạng 
khác tương ứng với các toán tử (operator)
o Qui bài toán về bài toán con
• Phân chia bài toán thành các bài toán con, các bài 
toán con lại được phân rã tiếp cho đến khi gặp được 
ấ ả ủ
12
các bài toán sơ c p cho phép xác định lời gi i c a 
bài toán ban đầu trên cơ sở lời giải của các bài toán 
con
• VD: phương pháp tinh dần từng bước trong công 
nghệ lập trình
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
43.4.Các phương pháp biểu diễn vấn đề
p Sử dụng logic hình thức
Khi giải quyết bài toán, phải tiến hành phân tích logic 
để thu gọn quá trình tìm kiếm, nhiều khi chứng minh 
được không có lời giải.
– logic mệnh đề
– logic vị từ cấp 1
cho phép:
– kiểm tra điều kiện kết thúc trong tìm kiếm đối với KGTT
kiểm tra tính áp dụng được của các toán tử
13
– Chứng minh không tồn tại lời giải
– Mục đích: CM 1 phát biểu nào đó trên cơ sở những tiền đề 
và luật suy diễn đã có. 
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.4.Các phương pháp biểu diễn vấn đề
q Lựa chọn phương pháp biểu diễn thích hợp 
nhằm:
• chia để trị
• tinh lọc thông tin
• tận dụng các phương pháp giải đã có
14
• phát biểu mới có thể thể hiện 1 vài tương 
quan nào đó giữa các yếu tố trong bài toán 
nhằm thu gọn quá trình giải
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.4.Các phương pháp biểu diễn vấn đề
r Biểu diễn trong máy
• dùng bảng/mảng (array): ví dụ, trò chơi n2-1 số
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
11 14 4 7
10 6 5
1 2 13 15
9 12 8 3
Trạng thái đầu Trạng thái đích
15
⎩⎨
⎧
=
≠+−==
)4,4(),(0
)4,4(),()1(4
)(
ji
jiji
aA ij
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.4.Các phương pháp biểu diễn vấn đề
r Biểu diễn trong máy
• dùng xâu ký hiệu
Ví dụ: bàn cờ Châu Âu
“T, XD, x , TgD, x , VD , x , MD, XD ,
ToD,ToD,ToD, x , x ,ToD,ToD,ToD,
x , x , x ,ToD, x , x , x , x ,
x , x , x , x ,ToD, x , x , x ,
x , x ,TgT, MD ,ToT, x , x , x ,
x , x , MT, x , x , x , x , x ,
ToT,ToT ,ToT, x , x ,ToT, HD,ToT,
XT , x , x , HT , VT, x , x , XT .”
16
x: ô trống, T: quân trắng đến lượt đi
XD: xe đen, TgD: tượng đen, VD: vua đen
MD: mã đen, ToD: tốt đen, HD: hậu đen
TgT: tượng trắng, ToT: tốt trắng, MT: mã trắng,
XT:xe trắng, HT: hậu trắng, VT: vua trắng
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
53.4.Các phương pháp biểu diễn vấn đề
r Biểu diễn trong máy
• dùng cấu trúc danh sách 
Ví dụ: nghiệm của phương trình bậc 2
a
acbbx
2
)4( 2
12
1
−+−=
17Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.5. Giải quyết vấn đề
Để xây dựng các tác tử biết suy luận, ta cần sử dụng lý 
thuyết logic, xác suất, và tính hữu dụng. Các kỹ thuật tìm 
kiếm được nghiên cứu trước hết vì: 
ế ấ ề• Tìm ki m là v n đ quan trọng trong TTNT:
– Tìm chuỗi hành động nhằm tối đa kết quả trong tương 
lai (lập kế hoạch)
– Tìm kiếm trong CSTT để tìm chỗi các hành động có thể thực 
hiện trong tương lai (suy luận logic, xác suất)
– Tìm các mô hình phù hợp với các quan 
sát (trong học máy)
Tì kiế là 1 t hữ thà h ô
18
• m m rong n ng n c ng
của các nghiên cứu về TTNT giai 
đoạn đầu
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Bài toán tìm kiếm: Lập kế hoạch 
đường đi
• Kết quả: đi từ Arad 
ếđ n Bucharest trong 
thời gian ngắn nhất
• Môi trường: bản đồ 
với các thành phố, 
đường, và thời gian 
đi giữa 2 thành phố
19Lê Thanh Hương – Khoa CNTT - ĐHBKHN
c
-
T
o
e
K
G
T
T
c
ủ
a
h
ơ
i
T
i
c
-
T
a
c
20
K
T
r
ò
C
h
6Chẩn đoán trục trặc máy móc trong ô tô
21
Cây và đồ thị
B là cha của C
C là con của B
A là tổ tiên của C
C là hậu duệ của A
22
Ví dụ về đồ thị
23
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.5.1 Biểu diễn bài toán trong không 
gian tìm kiếm
Phát biểu bài toán P1:
• Cho trạng thái đầu s0
• Cho tập trạng thái đích ĐICH
Tìm dã trạng thái s s s sao cho• y 0, 1,, n 
– sn ∈ĐICH và 
– ∀i: si→si+1 nhờ áp dụng toán tử biến đổi
• Giá đường đi: (cộng gộp)
– ví dụ, tổng khoảng cách, số lượng hành động đã thực hiện, 
– c(x, a, y) là giá 1 bước, ≥ 0
• Để biểu diễn phép biến đổi trạng thái, có 2 cách viết:
1 Cách viết dùng luật sản xuất
24
. , 
• VD: VT → VP
• Bài toán Tháp Hà Nội
2. Cách viết dùng ký hiệu hàm
• VD: B = f(A)
• Bài toán n2-1 số 
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
73.5.1 Biểu diễn bài toán trong KGTK
Phát biểu lại bài toán P1 (bài toán P2):
1 Tìm dãy trạng thái s s s sao cho. 0, 1,, n 
– sn ∈ĐICH và 
– ∀i: si→si+1 (hay ∃ toán tử biến đổi O: 
O(si) = si+1)
2. Tìm dãy toán tử O1,,On-1, On sao cho:
25
On(On-1(O1(s0)..)) = sn ∈ ĐICH 
hay tìm dãy sản xuất p1,,pn sao cho
s0⇒p1s1⇒⇒pnsn ∈ ĐICH
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Các chiến lược tìm kiếm lời giải
VD1: Bài toán rót nước 
What: A(m),B(n). Đầu: (0,0). Đích (k,*) U (*,k)
How: Thao tác rót: A Æ B,
Điều kiện: không tràn, đổ hết
Biểu diễn sản xuất: (x,y) Æ (x’, y’)
m = 6, n = 5, k = 2:
26
6 – 5 = 1
2*6 - 2*5 = 2; 4*5 - 3*6 = 2.
USCLN(m,n)=d. Nếu k không chia hết cho d Æ not OK
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Các chiến lược tìm kiếm lời giải
VD2: Bài toán Tháp Hà Nội, n=3
( i , j , k ) Nếu i, j, k là 3 cọc riêng biệt
C B A i + j + k = 6 
Procedure Thap(n,i,j: integer);
//nhấc n đĩa từ cọc i sang cọc j
Var k: interger;
Begin k = 6 – i – j;
if n=1 then Nhac(i,j)
27
else begin Thap(n-1,i,k);
Nhac(i,j);
Thap(n-1,k,j);
end;
End; Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Không gian trạng thái của bài toán 
Tháp Hà Nội
111
113112
123
122
322
321
132
133
233
231
131 121
232 323
28Lê Thanh Hương – Khoa CNTT - ĐHBKHN
331
333
221
222
223 213 211 311 312 332
212 313
8Biểu diễn bằng đồ thị
Đồ thị G là cặp G = (N,A) với N - tập các nút, A - tập các 
cung và với ∀n∈N: Γ(n) = {m∈N| (n,m)∈A}
Đồ thịKGTT 
• nút (đầu, đích)
• cung
• đường đi
• Trạng thái (đầu, đích) 
S, ababb
• Toán tử (sản xuất) S →Sa
• Dãy trạng thái liên tiếp
• Dãy toán tử
29
• Tìm đường đi trên đồ thị từ 
đỉnh đầu n0 (tương ứng với 
s0) tới đỉnh ĐICH
S →Sa →aBa
• Bài toán P1,P2
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Chuyển bài toán tìm kiếm trên đồ 
thị về tìm kiếm trên cây
• Cây là đồ thị có hướng không có chu trình và các nút có 
<= 1 nút cha. 
• Chuyển TK trên đồ thị về TK trên cây: 
– thay các liên kết không định hướng bằng 2 liên kết có hướng
– tránh các vòng lặp trên đường (sử dụng biến tổng thể để lưu vết 
các nút đã thăm)
30Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Các đặc tính tìm kiếm
• Tính đầy đủ
– Khi bài toán có lời giải thì giải thuật tìm kiếm có 
thể tìm thấy lời giải không?
• Thời gian
– Thời gian cần thiết để tìm thấy lời giải
• Không gian
– Dung lượng nhớ cần thiết để tìm thấy lời giải
31
• Sự tối ưu
– Khi có hàm giá, giải thuật có đảm bảo tìm được lời 
giải tối ưu không? 
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.5.2 Các phương pháp tìm kiếm
Bất kì TK sâu Khám phá có hệ thống toàn bộ cây đến khi 
ấ
Lớp Tên Thao tác
0 biết giá TK rộng tìm th y đích
Tối ưu 
Biết giá
TK cực tiểu Sử dụng độ đo là độ dài đường đi, tìm 
đường đi ngắn nhất
Tối ưu TK cực tiểu * Sử dụng độ đo là độ dài đường đi và mẹo, 
ắ ấ
32
Biết giá tìm đường đi ng n nh t
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
9Thuật toán tìm kiếm cơ bản
Xây dựng tập Mở - tập các đỉnh sắp duyệt
Đóng - tập các đỉnh đã duyệt
n0 - trạng thái đầu 
1 Mở { } Đó ∅. = n0 ; ng = 
2. Chọn n ∈ Mở:
Đóng = Đóng ∪ {n}
Mở = Mở ∪ Γ(n) // Γ(n): tập các nút con của n
3. Lặp (2) đến khi gặp n* ∈ Đích ⇒ thành công
4. Với mỗi m ∈ Γ(n), thực hiện: cha(m) = n
p’ = g, cha(g), cha2(g),,n0
p = inverse(p’)
n0
33
In đường đi
Các quyết định quan trọng:
• Lấy n ∈ Mở
• Bổ sung Γ(n) vào Mở Đích
Đóng (đã)
Γ(n)
n
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Cài đặt các chiến lược tìm kiếm
Các quyết định quan trọng:
• Lấy n ∈ Mở
• Bổ sung Γ(n) vào Mở
Đó (đã)
n0
• Tìm kiếm sâu (Depth-first):
Vào sau ra trước 
(LIFO – Last In First Out)
• Tìm kiếm rộng (Breadth-first):
Vào trước ra trước
Đích
ng 
Γ(n)
n
Mở
vào
ra
Γ(n)
n
34
(FIFO – First In First Out)
• Tìm kiếm cực tiểu (Uniform-cost):
Lấy phần tử có giá nhỏ nhất dựa trên hàm giá
Mở vàora n Γ(n)
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
1
3
5
2
4
35
96
7 8
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm Kiếm Sâu hay Rộng?
• Có cần thiết tìm một đường đi ngắn nhất đến mục 
tiêu hay không?
• Sự phân nhánh của không gian trạng thái
• Tài nguyên về không gian và thời gian sẵn có
• Khoảng cách trung bình của đường dẫn đến trạng 
thái mục tiêu.
ầ ấ
36
• Yêu c u đưa ra t t cả các lời giải hay chỉ là lời giải 
tìm được đầu tiên.
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
10
Tìm kiếm sâu Tìm kiếm rộng
Th ật t á H à thiệ Tối Thời i Khô i
37
u o n o n n ưu g an ng g an
TKS không không O(bm) O(bm)
TKR có không O(bd+1) O(bd+1)
= 1 + b + b2 +  + bd + b(bd-1) = O(bd+1)
Tìm kiếm sâu dần
• TKS có thể cho kết quả nhưng đường đi không phải 
là ngắn nhất
• Tuy có ∃ 1 đường đi đến Đích nhưng TKS có thể 
không dừng .
⇒chọn ngưỡng sâu D, mỗi đỉnh được gán một ngưỡng 
sâu d(n) 
Lấy n ∈ Mở, d(n) ≤ D
• Vấn đề
– Nếu điểm đích n* có d(n*) > D?
38
⇒ Tìm kiếm sâu dần
Thuật toán Hoàn thiện Tối ưu Thời gian Không gian
TKSD có không O(bd) O(bm)
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Trò chơi ô đố 8-puzzle với ngưỡng sâu 5
39
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm kiếm cực tiểu
c(ni, nj): chi phí đi từ ni đến nj
Xét p = n0, n1, , nk
Hàm đánh giá
c(p) = c(n0,n1) + c(n1,n2) ++ c(nk-1,nk)
Lấy n ∈ Mở: g(n) = c(p(n0,n)) min
Nếu ∀c(ni,nj) > ε, C* là chi phí của lời giải tối ưu
40
Thuật toán Hoàn thiện Tối ưu Thời gian Không gian
TKCT có có O(bceiling(C*/ε)) O(bceiling(C*/ε))
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
11
LC
ST
LS
HB
20
5
7
17 90
15
30
QN
HN
NĐ
NB
TB
HP
1510
10
15 15
25
80
90100
10
41
Tìm đường đi ngắn nhất từ HN đến V
TH
V
15
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm kiếm cực tiểu với tri thức bổ sung 
(A*)
c(ni, nj) = chi phí đi từ ni đến nj
g(n) = chi phí thực tế đường đi từ n0 đến n
ếh(n) = chi phí ước lượng đường đi từ n đ n đích, do chuyên gia 
cung cấp
• h(n) chấp nhận được nếu với ∀n, 0 ≤ h(n) ≤ h*(n), trong đó h*(n) 
là chi phí thực để tới trạng thái đích từ n.
• h(n) càng sát với h*(n) thì thuật toán càng mạnh
f(n) = g(n) + h(n)
f(n-1) = g(n-1) + h(n-1)
n0
g(n-1)
42
g(n) = g(n-1) + c(n-1,n)
f(n) = g(n-1) + c(n-1,n) + h(n) 
= f(n-1) – h(n-1) + c(n-1,n) + h(n) 
Lấy n ∈ Mở: f(n) min đích
n
n-1
h(n-1)
h(n)
c(n-1,n)
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
n h(n)
HN 50
ST 60
LC 75
HB 65
QNLC
ST
LS
HB
20
5
7
17 90
15
30
LS 70
HP 80
QN 80
TB 55
NĐ 45
HN
NĐ
NB
TB
HP
1510
10
15 15
25
80
90100
10
43
NB 20
TH 15
V 0
h(n): khoảng cách đường chim bay HN Æ V
TH
V
15
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3.5.3 Một số dạng heuristic trong 
bài toán tìm kiếm
44Lê Thanh Hương – Khoa CNTT - ĐHBKHN
12
Bài toán đố 8 số
45
6 8
1 2 3
481
45
6 8
• VÍ dụ về heuristic
Số viên sai vị trí
Start State Goal State
27 6237 5
45
– 
– Khoảng cách Manhattan. (Khoảng cách 
Manhattan giữa (x1,y1) và (x2,y2) là |x1-x2|+|y1-y2|. 
• H1(S) = 7
• H2(S) = 2+3+3+2+4+2+0+2 = 18
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Trò chơi Tic-tac-toe
46
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng của các trạng thái
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phép đo heuristic
Chiếm 3 đường Chiếm 4 đường Chiếm 2 đường
47
Heuristic “Số đường thắng nhiều nhất” áp dụng cho các 
nút con đầu tien trong tic-tac-toe.
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phép đo heuristic
48
13
Trò chơi đối kháng MINIMAX
Có 2 đối thủ MAX và MIN
• MAX tìm cách làm cực đại 1 hàm ước lượng nào đó: Chọn nước đi 
ứng với GTLN
• MIN tìm cách làm cực tiểu và chọn nước đi ứng với GTNN
Ở mỗi thời điểm: 
• Nếu 1 đỉnh ứng với nước đi của MAX thì giá trị của nó là GT cực đại 
của các đỉnh con. 
• Nếu 1 đỉnh ứng với nước đi của MIN thì giá trị của nó là GT cực tiểu 
của các đỉnh con. 
Áp dụng vào chơi cờ caro trên bảng ô vuông (Tictactoe), kích thước 3x3. 
MAX đặt dấu x, MIN đặt dấu o. Ở mỗi nước đi, mỗi đối thủ xem trước 
2 ớ
49
 nư c. 
Ước lượng e(p) đối với mỗi thế cờ p:
E(p) = (số dòng, số cột, số đường chéo còn mở đối với MAX) 
- (số dòng, số cột, số đường chéo còn mở đối với MIN) 
• Nếu p là thế thắng đối với MAX, e(p) = +∞
• Nếu p là thế thắng đối với MIN, e(p) = -∞
• MAX đi mọi đường không có o; MIN đi mọi đường không có x
KGTT của tic-tac-toe được thu nhỏ 
nhờ tính đối xứng của các trạng thái
ầ
1
MAX đi nước đ u tiên
MIN đi
-1 -21
50
1e(p) 0 0 0 01 1 2 -2-1-1-1
Æ Tìm kiếm theo kiểu depth-first
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phương pháp cắt tỉa α-β trong trò 
chơi minimax
51Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phương pháp cắt tỉa α-β
52Lê Thanh Hương – Khoa CNTT - ĐHBKHN
14
Phương pháp cắt tỉa α-β
53Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phương pháp cắt tỉa α-β
54Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phương pháp cắt tỉa α-β
55Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phương pháp cắt tỉa α-β
• Cắt cụt không làm ảnh hưởng tới kết quả cuối cùng
• Sắp xếp thứ tự duyệt tối ưu sẽ nâng cao hiệu quả của 
quá trình cắt cụt 
• Trong trường hợp tốt nhất, độ phức tạp thời gian = 
O(bm/2)
Tại sao gọi là α-β? 
• α là giá trị của lựa chọn tốt nhất 
được tìm thấy ở thời điểm hiện tại 
56
trên đường đi của max
• Nếu v tồi hơn α, max sẽ không 
duyệt nó Æ cắt cụt nhánh đó
• Định nghĩa β tương tự đối với min
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
15
Một số trò chơi đối kháng (minimax)
57
3.5.4 Tìm kiếm lời giải trên đồ thị 
Và/Hoặc
Phân rã bài toán thành bài toán con
VD1: Tìm đường đi từ Nhà hát lớn đến Ga Hà Nội .
BT1. Đi từ Nhà hát lớn đến Hồ hoàn kiếm
BT2. Đi từ Hồ hoàn kiếm đến Cửa Nam
BT3. Đi từ Cửa Nam đến Ga Hà Nội
NHL → GHN
58
NHL → HHK HHK → CN CN → GHN
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm kiếm lời giải trên đồ thị Và/Hoặc
VD2: Tháp Hà Nội n = 3
Bài toán đầu (111) → (333) được qui về 3 bài toán con:
BT1. (111) → (122): chuyển 2 đĩa AB từ cọc 1 sang cọc 2
BT2 (122)→ (322): chuyển đĩa C từ cọc 1 sang cọc 3. 
BT3. (322) → (333): chuyển 2 đĩa AB từ cọc 2 sang cọc 3
BT2 giải được ngay, BT1 và BT3 tiếp tục phân rã
(111) → (333)
59
(111) → (122) (122) → (322) (322) → (333)
(111) → (113)
(113) → (123)
(123) → (122) (322) → (321)
(321) → (331)
(331) → (333)
Qui bài toán về BT con
• Bài toán
• Qui về BT con
– Phát biểu lại BT
P P P
Đồ thị V/H
• Đỉnh
• Cung
– Cung Hoặc P → P1
P
P1 P2 Pn. . . → 1,, n
– Phân rã P thành
P1,,Pn
• BT xuất phát
• BT sơ cấp (nguyên tử) 
(∃ thuật giải để giải
P → Pn
– Cung Và P → P1,, ,
P → Pn
• Đỉnh gốc n0
• Đỉnh kết thúc
P
P1 P2 Pn. . .
60
quyết)
• Giải BT P • XD đồ thị lời giải
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
16
Đỉnh giải được
1 Đỉnh kết thúc (⇔ bài toán sơ cấp) giải. 
được
2. Giả sử n có con n1,,nk
– n1, , nk ∈ NV
n giải được ⇔ ∀ni giải được
n
n1 n2 nk. . .
n
61
– n1, , nk ∈ NH
n giải được ⇔ ∃ni giải được n1 n2 nk. . .
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Cây lời giải T
• là cây con của đồ thị G
– n0 ∈ T
đỉ h T iải đ– ∀ n n∈ , n g ược
E
E1 E2
E E E E
62
11 12 21 22
E*111 Eo112 E*121 E*122 Eo211 E*212 E*221 E*222
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Đỉnh không giải được
1. n là lá (Γ(n) = ∅), n không kết thúc
2. n có con n1,,nk
– ni ∈ NV , nkgd⇔ ∃ ni không giải được
– ni ∈ NH , nkgd⇔ ∀ ni không giải được
Qui ước: n ∈ N là 1 bài toán nào đó
nhan(n) = true nếu đỉnh n giải được
f ế ỉ ả
n
n1 n2 nk. . .
n
63
alse n u đ nh n không gi i được
kxd nếu đỉnh n không xác định
Với bài toán P, cần xác định nhan(n0), kéo theo đồ thị 
lời giải
n1 n2 nk. . .
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Thuật toán gán nhãn đỉnh giải được
procedure GD(n)
/* n gd hay nhan(n) = true tuỳ thuộc vào thông tin gd của các 
đỉ h ủ */n con c a n 
{1 if kt(n) then nhan(n)=true
else {2
if n có các đỉnh con là đỉnh VÀ n1,,nk then
{3 gd(n1);; gd(nk);
if(nhan(n1) and  and nhan(nk) then nhan(n) = true }3
64
if n có các đỉnh con là đỉnh HOẶC n1,,nk then
{4 gd(n1);;gd(nk);
if(nhan(n1) or  or nhan(nk) then nhan(n) = true }4
}2
}1 Lê Thanh Hương – Khoa CNTT - ĐHBKHN
17
Thuật toán gán nhãn đỉnh K giải 
được
procedure KGD(n)
{1 if not kt(n) then nhan(n)=false
else {2
if n có các đỉnh con là đỉnh VÀ n1,,nk then
{3 gd(n1);; gd(nk);
if(not nhan(n1) or or not nhan(nk) then nhan(n) = 
false}3
65
if n có các đỉnh con là đỉnh HOẶC n1,,nk then
{4 gd(n1);;gd(nk);
if(not nhan(n1) and  and not nhan(nk) then nhan(n) = 
false}4
}2
}1
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Thuật toán gán nhãn đỉnh giải được
procedure GD(n)
/* n gd hay nhan(n) = true tuỳ thuộc vào thông tin gd của các 
đỉ h ủ */n con c a n 
{1 if kt(n) then nhan(n)=true
else {2
if n có các đỉnh con là đỉnh VÀ n1,,nk then
{3 gd(n1);; gd(nk);
if(nhan(n1) and  and nhan(nk) then nhan(n) = true }3
66
if n có các đỉnh con là đỉnh HOẶC n1,,nk then
{4 gd(n1);;gd(nk);
if(nhan(n1) or  or nhan(nk) then nhan(n) = true }4
}2
}1 Lê Thanh Hương – Khoa CNTT - ĐHBKHN
TK rộng mới
Vào: Cây V/H G=(N,A) với đỉnh đầu n0
Ra: cây lời giải
PP:/* sử dụng 2 d/s queue MO, DONG*/
TK sâu mới: 
MO là stack
{1 MO = {n0}; DONG = ∅;
while MO ≠ ∅ do {2
n ← get(MO); DONG ← DONG ∪ {n};
if Γ(n) ≠ ∅ then {3 MO ← MO ∪ Γ(n);
if trong Γ(n) có đỉnh m kết thúc then {4
nhan(m) = true; gd(n0);
if nhan(n0) then exit(‘thanh cong’)
ổ
67
else Loại khỏi MO các đỉnh có t tiên là đỉnh giải được 
}4 }3
else{5 nhan(n) = false; kgd(n0);
if not nhan(n0) then exit(‘khong thanh cong’)
else Loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải 
được }5 }2 }1
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm kiếm cực tiểu mới
Đặt vấn đề: Tìm cây T* để chi phí C(T*) min
Thực tiễn đưa ra 2 mô hình về giá cây T
Giá tổ ộ ∑= acTC )()(
1
2 3 4• ng c ng:
• Giá max:
Giá tối ưu để giải bài toán là h(n), h(n) có các tính chất sau:
• Nếu n là đỉnh kết thúc, h(n) = 0
• Nếu n có con là n1, , nk
∀ N h( ) i [h( ) + ( )]
∈
∑
Ta
5 6 7 8))((max)(
0:
max pcTC leavesnp →=
n
68
• ni ∈ H: n = m n ni c n,ni
• ∀ni ∈NV: 
– Giá Σ: h(n) = [ Σh(ni) + Σc(n,ni)]
– Giá max: h(n) = max[h(ni) + c(n,ni)]
• Nếu n là đỉnh không giải được, h(n) = ∞
n1 n2 nk
TkT2T1
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
18
KGTT của tic-tac-toe
ầ
1
MAX đi nước đ u tiên
MIN đi
-1 -21
69
1e(p) 0 0 0 01 1 2 -2-1-1-1
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm kiếm cực tiểu mới
• Trong quá trình tìm kiếm tại mỗi bước , 
có 1 tập các cây con gốc n0 sao cho 
chúng có thể thành phần trên của cây 
lời giải cuối - cây lời giải tiềm tàng T0. 
• Xây dựng cây T0 dựa theo h’
70Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tìm kiếm cực tiểu mới
Cách xác định cây lời giải tiềm tàng T0
1. Đỉnh đầu n0 ∈ T0
2 Nếu n ∈T có các đỉnh con n → n là:. 0 1 k
1. đỉnh HOẶC:
• chọn ni: c(n,ni) + h’(ni) min, nhan(ni) ≠ kgd
2. đỉnh VÀ: 
• chọn n1, ,nk vào T0 nếu ∀ni: nhan(ni) ≠ kgd
Nhận xét:
– Nếu cây V/H chỉ chứa đỉnh hoặcÆ TKCT 
– Nếu c = 1 và h’=0 với ∀nút và sử dụng giá max Æ
TKRM
– Nếu h’(n) ≤ h(n) với ∀n và ∃δ: ∀a ∈ A, c(a) ≥ δ thì 
TKCTM dừng và cho kết quả là cây lời giải tối ưu
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
TKCT mới
1. MO = {n0}; DONG = ∅; T0 = n0
2. Chọn n ∈ MO ∩ lá (T0):
DONG ← DONG ∪ {n};
if kt(n) then { nhan(n) = true; gd(n0);
if nhan(n0) then exit(‘thanh cong’)
else Loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được 
 } else { // n không kết thúc
if Γ(n) ≠ ∅ then { MO ← MO ∪ Γ(n);
Với mỗi m ∈Γ(n), tính h’(m)
 Với mỗi m ∈MO ∪ DONG, tính h’(m)
else{ // n không kết thúc và không có con
72
nhan(n) = false; kgd(n0);
if not nhan(n0) then exit(‘khong thanh cong’)
else Loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được 
} 
}
3. Lặp lại 2 đến khi MO =∅
19
TKCT mới
a
b c
8 9
6 3 2 1
a
9
a
9
T1 T2 T T1 T2
CΣ 23 22
d e f g
h i0 j* k* l* m*
n* o*
5 7 5 7 3 9
8 3
c
f
j* k*
2
5 7
c
g
l* m*
1
3 9
Cmax 18 19
n a b c d e f g h i j k l m n o
73
hΣ 22 ∞ 13 16 ∞ 12 12 11 ∞ 0 0 0 0 0 0
hmax 18 ∞ 9 13 ∞ 7 9 8 ∞ 0 0 0 0 0 0
h’ 4 3 3 2 2 2 2 1 ∞ 0 0 0 0 0 0
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
1
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
h’ 4 3 3 2 ∞ 2 ∞ 1 1 0 1 0 ∞ 0 0 ∞
2 3
4
50 6 70
8 9 10* 11
3 1
2 1 1 3
1 3 2 1
3
12* 130 14* 15* 160
2 1 3 1
Lê Thanh Hương – Khoa CNTT - ĐHBKHN