Bài giảng Trí tuệ nhân tạo - Chương 3: Tìm kiếm Heuristic - Bùi Đức Dương

 0 352 475
F 655 285 348 147 352 0 548
G 472 328 226 630 475 548 0
 Greedy 1: A→ B→ E→ F→ D→ C→ G→ A 
 Greedy 2: A → B → E → F → D → C → G → A
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng
của các trạng thái.
 Bài toán 4 (Tô màu bản đồ). Cho n quốc gia (1, 2,...n). Hai quốc 
gia được gọi là láng giềng nếu có đường biên giới chung. Hãy tìm 
số màu ít nhất để tô cho ác quốc gia sao cho 2 quốc gia láng 
giềng bất kỳ phải khác màu.
1. Giới thiệu (tt)
A
B
C
D E
F
 Bậc của quốc gia: số QG láng giềng
QG A B C D E F
Bậc 2 3 5 2 3 3
Procedure ToMauBanDo;
Begin
m=1;
Repeat
Tìm quốc gia i thỏa Bậc[i]=max;
Mau[i]=m++;
For j=1 to n do
If (Mau[j]=null and LangGieng[i,j]=True) Bậc[j]--;
Until (m=n);
End;
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng
của các trạng thái.
 Bài toán 5 (Bài toán phân việc). Phân xưởng có n máy cưa 
công suất bằng nhau M1, M2,...Mn. Có m thanh gỗ cần được xẻ
G1, G2,...Gm, biết thời gian xẻ của thanh gỗ Gi là ti. Hãy tìm 
phương án để xẻ m thanh gỗ trong thời gian sớm nhất.
 Sắp xếp các thanh gỗ theo chiều giảm dần của thời gian xẻ.
 Lần lượt bố trí các thanh gỗ vào máy còn dư nhiều thời gian nhất.
 Ví dụ: Xét trường hợp 3 máy M1, M2,M3 và 7 thanh gỗ có thời gian xẻ
t1=1; t2=8; t3=1; t4=5; t5=4; t6=3;t7=4; 
1. Giới thiệu (tt)
t2=8 t1=1
M1
t4=5 t6=3 t3=1
M2
t5=4 t7=4
M3
LOGO
2. Thuật toán HCS (tt)

 Tìm kiếm leo đồi – Hill Climbing Search (Pearl, 1984) 
 Mở rộng trạng thái hiện tại và đánh giá các trạng thái con của nó
bằng hàm đánh giá heuristic.
 Con “tốt” sẽ được chọn để đi tiếp. Chọn một trạng thái tốt hơn: 
leo đồi đơn giản, trạng thái tốt nhất: leo đồi dốc đứng. 
 Khác với tìm kiếm sâu, leo đồi không lưu tất cả các con mà chỉ lưu
đúng một t.thái được chọn nếu có.

Giới hạn
 Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ:
 Lời giải tìm được không tối ưu
 Không tìm được lời giải mặc dù có tồn tại lời giải
 Giải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin 
về các trạng thái đã duyệt. 
LOGO
Procedure Hill_Climbing_Search;
Begin
Open:={Start}; Close:=∅;
While (Open ∅) do
Begin 
X= Get(Open,leftmost);// Chọn trạng thái ngoài cùng của Open
If (X=Goal) then Return True
Else Begin
Close = Close ∪ {X}; 
Sinh ra các nút con của X;
C=Children(X)\{Open ∪ Close}
Y = Retrieve(C);// Chọn trạng thái tốt hơn X(nhất)
Open = Open ∪ {Y}; 
End;
End;
Return False;
End;
2. Thuật toán HCS (tt)
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng
của các trạng thái.
Procedure Best_First_Search;
Begin
Open:={Start}; Clos :=∅;
While (Open ∅) do
Begin 
X= Retrieve(Open);// Chọn trạng thái tốt nhất
If (X=Goal) then Return True
Else Begin
Sinh ra các nút con của X;
For mỗi nút con Y của X do
Begin 
Gán giá trị heuristic cho Y;
Open = Open ∪ {Y}; 
End;
End;
End;
Return False;
End;
3. Tìm kiếm tối ưu (tt)
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng 
của các trạng thái.

 Best First Search vs Breath First & Depth First Search
 Best First search tương tự như Depth First & Breath First nhưng 
phần tử được xét tiếp theo là phần tử có giá trị heuristic tốt nhất.
 Cần có một hàm đánh giá các trạng thái để xác định giá trị heuristic 
cho các trạng thái.
 Không gian trạng thái vẫn không thay đổi về “toàn cục“ tuy nhiên 
thường Heuristic search có không gian trạng thái làm việc nhỏ hơn 
Depth First và Breath First. Tại sao??
 Do sự định hướng các trạng thái kế tiếp theo hướng có khả năng 
tìm ra nghiệm nhanh hơn nên số trạng thái xét dư thừa sẽ hạn 
chế -> sinh ít trạng thái con hơn
 Điều này cũng là nguyên nhân làm cho Best First Search có thể
dẫn đến kết quả là “nghiêm phụ” thay vì “nghiệm tối ưu”.
3. Tìm kiếm tối ưu (tt)
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng 
của các trạng thái.
Procedure AT;
Begin
Open:={Start}; 
While (Open ∅) do
Begin 
X= Retrieve(Open);// Chọn X sao cho g(X) đạt min(Open)
If (X=Goal) then Return True
Else Begin
Sinh ra các nút con của X;
For mỗi nút con Y của X do
If(Y∉Open)
Begin 
g(Y):=g(X)+cost(X,Y);
Open = Open ∪ {Y}; 
End;
Else So sánh g(Y) với gNew(Y) và cập nhật
End;
End;
Return False;
End;
3. Tìm kiếm tối ưu (tt)
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng 
của các trạng thái.
Procedure AKT;
Begin
Open:={Start}; 
While (Open ∅) do
Begin 
X= Retrieve(Open);// Chọn X sao cho f(X) đạt min(Open)
If (X=Goal) then Return True
Else Begin
Sinh ra các nút con của X;
For mỗi nút con Y của X do
Begin 
g(Y)=g(X)+cost(X,Y);
f(Y)=g(Y)+h’(Y);
Open = Open ∪ {Y}; 
End;
End;
End;
Return False;
End;
3. Tìm kiếm tối ưu (tt)
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng 
của các trạng thái.
Procedure A*;
Begin
Open:={Start}; Close:= ∅; 
While (Open∅) do
Begin 
X= Retrieve(Open);// Chọn X sao cho h(X)-heuristic đạt
min(Open)
If (X=Goal) then Return True
Else Begin
Sinh ra các nút con của X;
For mỗi nút con Y của X do
If (Y∉Open) và (Y∉Close) 
Begin 
Gán heuristic - h(Y);
Open = Open ∪ {Y}; 
End;
3. Tìm kiếm tối ưu (tt)
LOGO
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng
của các trạng thái.
If (Y∈Open) 
If (hnew(Y)<hold(Y)) cập nhật lại Y trong Open;
If (Y∈Close) 
If (hnew(Y)<hold(Y))
Begin
Close=Close \ {Y};
Open = Open ∪ {Y}; 
End;
End;
Close=Close ∪ {X}; 
End;
Return False;
End;
3. Tìm kiếm tối ưu (tt)
LOGO
4. Hàm lượng giá heuristic
Trong đó:
f(n): Hàm lượng giá heuristic tại trạng thái n
g(n): Khoảng cách từ n đến trạng thái bắt đầu
h(n): Hàm heuristic đánh giá khoảng cách từ t.thái n đến mục tiêu
f(n) = g(n) + h(n)f( ) ( ) ( )
Ví dụ: Xét trò chơi 8-puzzle
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
start
g(n) = 0
g(n) = 1
goal
LOGO
4. Hàm lượng giá heuristic
5 6
3 4
5 6
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
Heuristic 1: Tổng số miếng 
sai vị trí
Heuristic 2: Tổng khoảng 
cách sai vị trí của từng 
miếng.
1 2 3
8 4
7 6 5
goal
LOGO
4. Hàm lượng giá heuristic
Trong đó:
f(n): Hàm lượng giá heuristic tại trạng thái n
g(n): Khoảng cách từ n đến trạng thái bắt đầu
h(n): Hàm heuristic đánh giá khoảng cách từ t.thái n đến mục tiêu
f(n) = g(n) + h(n)f( ) ( ) ( )
Ví dụ: Xét trò chơi 8-puzzle.
h(n): số lượng các vị trí sai
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
start
g(n) = 0
g(n) = 1
6 4 6f(n) = 
goal
LOGO
4. Hàm lượng giá heuristic (tt)
57
461
382
1
State A
F(a) =0+4=4
57
461
382
x
State B
F(b) =1+5=6
567
41
382
2
State C
F(c) =1+3=4
57
461
382
x
State D
F(c) =1+5=6
567
41
382
3
State E
F(e) =2+3=5
567
481
32
4
State F
F(f) =2+3=5
567
41
382
x
State G
F(g) 
=2+4=6
567
412
38
x
State H
F(h) =3+3=6
56
417
382
x
State I
F(i) =3+4=7
LOGO
4. Hàm lượng giá heuristic (tt)
567
481
324 State F
F(f) =2+3=5
567
481
325 State J
F(j) =3+2=5 567
481
32x State K
F(k) =3+4=7 567
41
382y State 
Close
567
481
32y State 
Close567
48
3216 State L
F(l) =4+1=5
567
481
32y State Close
567
48
3217 State M
F(m) =5+0=5 56
487
321x State N
F(n) 
=5+1=7
LOGO
4. Hàm lượng giá heuristic (tt)
Laàn X Open Close
0
1
2
3
4
5
6
7
A4
C4
E5
F5
J5
l5
m5
[a4]
[c4,b6,d6]
[e5,f5,g6,b6,d6]
[f5,h6,g6,b6,d6,i7]
[j5,h6,g6,b6,d6,k7,i7]
[l5,h6,g6,b6,d6,k7,i7]
[m5,h6,g6,b6,d6,k7,i7,n7]
[]
[a4]
[a4,c4]
[a4,c4,e5]
[a4,c4,e5,f5]
[a4,c4,e5,f5,j5]
[a4,c4,e5,f5,j5,l5]
LOGO
5. Heuristic trong trò chơi đối kháng

Giải thuật minimax:
 Hai đấu thủ trong trò chơi được gọi là MIN và MAX.
 Mỗi nút lá có giá trị:
• 1 nếu là MAX thắng, 
• 0 nếu là MIN thắng.
 Minimax sẽ truyền các giá trị này lên cao dần trên đồ thị, 
qua các nút cha mẹ kế tiếp theo các luật sau:
• Nếu trạng thái cha mẹ là MAX, gán cho nó giá trị lớn nhất có
trong các trạng thái con.
• Nếu trạng thái bố, mẹ là MIN, gán cho nó giá trị nhỏ nhất có
trong các trạng thái con.
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
Áp dụng GT Minimax 
vào trò chơi NIM
LOGO
5. Heuristic trong trò chơi đối kháng (tt)

Minimax với độ sâu lớp cố định

Minimax đối với một KGTT giả định.

 Các nút lá được gán các giá trị heuristic

 Còn giá trị tại các nút trong là các giá trị nhận được 
dựa trên giải thuật Minimax
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
Hàm Heuristic: E(n) = M(n) – O(n)
Trong đó: M(n) là tổng số đường thắng có thể của tôi
O(n) là tổng số đường thắng có thể của đối thủ
E(n) là trị số đánh giá tổng cộng cho trạng thái n
•Heuristic trong trò chơi tic-tac-toe
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
Nilsson (1971)
Minimax 2 lớp được áp dụng vào nước đi mở đầu 
trong tic-tac-toe
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
• Giải thuật cắt tỉa α-β

 Tìm kiếm theo kiểu depth-first.

 Nút MAX có 1 giá trị α (luôn tăng)

 Nút MIN có 1 giá trị β (luôn giảm)

 TK có thể kết thúc dưới bất kỳ:
 Nút MIN nào có β ≤ α của bất kỳ nút cha MAX nào.
 Nút MAX nào có α ≥ β của bất kỳ nút cha MIN nào.

Giải thuật cắt tỉa α-β thể hiện mối quan hệ giữa các nút ở
lớp n và n+2, mà tại đó toàn bộ cây có gốc tại lớp n+1 có
thể cắt bỏ.
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
Cắt tỉa α
S
A Z
MAX
MIN
= z
≥ α
= α
z ≤ α
α - cut
= α
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
Cắt tỉa β
S
A Z
MIN
MAX
= z
≤ β
= β
z ≥ β
β - cut
= β
LOGO
5. Heuristic trong trò chơi đối kháng (tt)
• Áp dụng cho KGTT giả định
Các nút không có giá trị là
các nút không được duyệt 
qua
LOGO
Bài tập Chương 3
Tìm hiểu các bài toán
Đổi tiền
Bài toán phân việc
BFS, DFS
Tic tac toe
Trò chơi NIM
Đong dầu
Tô màu bản đồ
Bài toán TSP
Puzzle
Cờ vua
Cờ tướng
Người nông dân qua sông
Con thỏ và con cáo
Con khỉ và nải chuối
Tu sỹ và kẻ ăn thịt người
Tham luận Chi bộ Khoa Cơ khí
Bùi Đức Dương – Khoa Công nghệ Thông tin