Bài giảng Trí tuệ nhân tạo - Bài 5: Tìm kiếm tối ưu. Tìm kiếm có đối thủ

Lec 5. p.1
Lec 5
Tìm kiếm tối ưu –
Tìm kiếm có đối thủ
Lec 5. p.2
Nội Dung
 Các kỹ thuật tìm đường đi ngắn nhất
– Thuật toán A*
– Thuật toán nhánh-cận
 Các kỹ thuật tìm kiếm đối tượng tốt nhất
– Tìm kiếm leo đồi
– Tìm kiếm Gradient
– Tìm kiếm mô phỏng luyện kim
 Tìm kiếm bắt chước sự tiến hoá: thuật toán di 
truyền
Lec 5. p.3
Tìm đường đi ngắn nhất
Trạng thái u gọi là trạng thái đạt tới nếu có đường 
đi từ trạng thái ban đầu u0 tới u .
 Hàm đánh giá:
– Độ dài đường đi ngắn nhất từ u0 tới u: g(u)
• Nếu u không phải trạng thái đích thì đường đi từ u0 tới u 
gọi là đường đi một phần
• Nếu u là trạng thái đích thì đường đi từ u0 tới u gọi là 
đường đi đầy đủ
– Độ dài đường đi ngắn nhất từ u tới trạng thái đích: 
h(u)
hàm đánh giá: f(u) = g(u) + h(u)
Lec 5. p.4
Cài Đặt Hàm Đánh Giá 
(Evaluation Function)
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
1 2 3
8 4
7 6 5
goal
g(n) = 0
g(n) = 1
6 4 6
Xét trò chơi 8-puzzle. Cho mỗi trạng thái n một giá trị f(n):
f(n) = g(n) + h(n)
g(n) = khoảng cách thực sự từ n đến trạng thái bắt đầu
h(n) = hàm heuristic đánh giá khoảng cách từ trạng thái n đến 
mục tiêu. 
f(n) = 
h(n): số lượng các vị trí còn sai
Lec 5. p.5
Thuật toán A*
 Tìm kiếm tốt nhất đầu tiên + hàm đánh giá f(u)
Procedure A*;
Begin
1. Khởi tạo danh sách L chỉ chứa trạng thái đầu;
2. Loop do
2.1 If L rỗng then {thông báo thất bại; stop};
2.2 Loại trạng thái u ở đầu danh sách L;
2.3 If u là trạng thái kết thúc then
{thông báo thành công; stop};
2.4 For mỗi trạng thái v kề u do
{g(v)g(u)+k(u,v)
f(v)g(v)+h(v);
đặt v vào danh sách L;}
2.5 Sắp xếp L theo thứ tự tăng dần của hàm f;
End;
Lec 5. p.6
Ví dụ: thuật toán A*
Đồ thị không gian trạng thái với hàm đánh giá
10
Cây tìm kiếm theo thuật toán A*
A
H
C
D
E
K
B
I
G
F
14
6
7
8
4
0
2
15
20
9
4
8
6
7 13
4
5 4
56
9
6
3
12
B
I
K
K
E
A
14
D13
21
E 19
25 1921
17
C24
H25
F
27
B
18
Lec 5. p.7
Nhận xét về thuật toán A*
 Nếu h(u) là đánh giá thấp (đặc biệt h(u)=0 với 
mọi trạng thái u), thì A* là thuật toán tối ưu, tức 
là nghiệm tìm được là tối ưu.
 Nếu độ dài các cung không nhỏ hơn một số 
dương δ nào đó thì A* là thuật toán đầy đủ, tức là
nó luôn dừng và tìm ra nghiệm.
Lec 5. p.8
Thuật toán tìm kiếm nhánh-cận
 Tìm kiếm leo đồi + hàm đánh giá f(u)
Procedure Branch-and-Bound;
Begin
1. Khởi tạo danh sách L chỉ chứa trạng thái đầu;
Gán giá trị ban đầu cho cost;
2. Loop do
2.1 If L rỗng then {thông báo thất bại; stop};
2.2 Loại trạng thái u ở đầu danh sách L;
2.3 If u là trạng thái kết thúc then
if g(u)<=cost then {cost g(u); quay lại 2.1};
2.4 if f(u)>cost then quay lại 2.1;
2.5 For mỗi trạng thái v kề u do 
{g(v) g(u)+k(u,v);
f(v) g(v) +h(v);
đặt v vào danh sách L1};
2.6 Sắp xếp L1 theo thứ tự tăng dần của hàm f;
2.7 Chuyển danh sách L1vào đầu danh sách L sao cho L1 ở đầu danh sách L;
End;
Lec 5. p.9
Ví dụ: thuật toán nhánh-cận
A
14
C24
F
27
B
I
K
K
ED13
21
E 19
251921
17
H25
B
18
Cây tìm kiếm nhánh-cận
A
H
C
D
E
K
B
I
G
F
14
6
7
8
4
0
2
15
20
9
4
8
6
7 13
4
5 4
56
9
6
3
12
10
Đồ thị không gian trạng thái 
với hàm đánh giá
Lec 5. p.10
Nhận xét
 Thuật toán nhánh-cận cũng là thuật toán đầy đủ 
và tối ưu nếu h(u) là hàm đánh giá thấp và độ dài 
các cung không nhỏ hơn một số dương δ nào đó.
Lec 5. p.11
Tìm đối tượng tốt nhất
Trên không gian tìm kiếm U, mỗi đối tượng x được 
xác định với một hàm giá cost(x) cần tìm đối 
tượng mà hàm giá đạt giá trị lớn nhất, gọi là đối 
tượng tốt nhất.
Lec 5. p.12
Tìm đối tượng tốt nhất
Tìm kiếm leo đồi
Tương tự kỹ thuật tìm kiếm leo đồi để tìm trạng 
thái kết thúc đã xét, tuy nhiên trong thuật toán 
này, từ một đỉnh u ta chỉ leo lên đỉnh tốt nhất v 
(được xác định bởi hàm giá cost) trong lân cận u 
nếu đỉnh này cao hơn u, tức là cost(v)>cost(u).
Thuật toán dừng ngay khi không leo lên đỉnh cao 
hơn được nữa.
Lec 5. p.13
Thuật toán di truyền
 TTDT bắt chước sự chọn lọc tự nhiên và di truyền:
– Chọn lọc tự nhiên: các cá thể khoẻ, có khả năng thích nghi tốt 
với môi trường sẽ được tái sinh và nhân bản ở các thế hệ sau
– Di truyền: Trong quá trình sinh sản, các cá thể con thừa huởng 
các phẩm chất của cha mẹ và có những đột biến.
 Mỗi cá thể được mã hoá bởi một cấu trúc DL mô tả cấu 
trúc gien của cá thể đó, gọi là nhiễm sắc thể.
 Một thế hệ là một quần thể ứng với một giai đoạn phát 
triển.
 TTDT bắt chước chọn lọc tự nhiên và di truyền để biến 
đổi các thế hệ.
Lec 5. p.14
Thuật toán di truyền
Các toán tử biến đổi các thế hệ
 Toán tử tái sinh: các cá thể tốt được lựa chọn để 
đưa vào thế hệ sau, sự chọn lọc dựa vào độ thích 
nghi với môi trường.
 Toán tử lai ghép: hai cá thể cha mẹ trao đổi gen 
để tạo ra hai cá thể con.
 Toán tử đột biến: Một cá thể thay đổi một số 
gen để tạo thành cá thể mới.
Lec 5. p.15
Thuật toán di truyền
Procedure Genetic-Algorithm;
Begin
t  0;
Khởi tạo thế hệ ban đầu P(t)
Đánh giá P(t) (dựa vào hàm thích nghi);
repeat
t  t + 1;
Sinh ra thế hệ mới P(t) từ P(t-1) bởi:
Chọn lọc
Lai ghép
Đột biến;
Đánh giá P(t);
until điều kiện kết thúc được thoả mãn;
End;
Lec 5. p.16
Tìm kiếm có đối thủ
 Bài toán tìm kiếm có đối thủ (chơi cờ) được biểu 
diễn trong không gian trạng thái:
– Trạng thái ban đầu: sự sắp xếp các quân cờ của hai 
bên lúc bắt đầu chơi.
– Các toán tử: các nước đi hợp lệ
– Các trạng thái kết thúc: các tình thế mà cuộc chơi 
dừng.
– Hàm kết cuộc: ứng mỗi trạng thái kết thúc với một giá 
trị nào đó.
Lec 5. p.17
Tìm kiếm có đối thủ
Cây trò chơi
– Gốc ứng với trạng thái đầu
– Đỉnh ứng với trạng thái mà Trắng (Đen) đưa ra nước 
đi gọi là đỉnh Trắng (Đen)
– Các đỉnh con của đỉnh Trắng (Đen) biểu diễn trạng 
thái u là tất cả các đỉnh biểu diễn trạng thái v, v nhận 
được từ u do Trắng (Đen) thực hiện nước đi hợp lệ 
nào đó.
– Lá của cây ứng với trạng thái kết thúc.
Lec 5. p.18
Tìm kiếm có đối thủ
Ví dụ: Cây trò chơi
Trò chơi Dodgem
Đen
Trắng
Đen
Cây trò chơi Dodgem với Đen đi trước
Lec 5. p.19
Heuristic trong trò chơi có đối thủ
Chiến lược min-max
– 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 cha mẹ là MIN, gán cho nó giá trị nhỏ nhất 
có trong các trạng thái con.
Lec 5. p.20
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
Lec 5. p.21
Giải thuật minimax
Function MaxVal(u);
begin
if u là đỉnh kết thúc then MinVal(u)  f(u)
else MinVal(u)  min{MaxVal(v) | v là đỉnh con của u} 
end;
Function MinVal(u);
begin
if u là đỉnh kết thúc then MaxVal(u)  f(u)
else MaxVal(u)  max{MinVal(v) | v là đỉnh con của u} 
end;
Procedure Minimax(u, v);
begin
val -;
for mỗi w là đỉnh con của u do
if val(u) <= MinVal(w) then
{val  MinVal(w); v  w} 
end;
Lec 5. p.22
Áp dụng GT Minimax vào 
trò chơi NIM
Lec 5. p.23
Heuristic trong trò chơi tic-tac-toe
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
Lec 5. p.24
Minimax 2 lớp được áp dụng vào 
nước đi mở đầu trong tic-tac-toe
Trích từ Nilsson (1971).
Lec 5. p.25
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ỏ.
Lec 5. p.26
Cắt tỉa 
S
A Z
MAX
MIN
= z
≥ 
= 
z ≤ 
 - cut
= 
Lec 5. p.27
Cắt tỉa 
S
A Z
MIN
MAX
= z
≤ 
= 
z ≥ 
 - cut
= 
Lec 5. p.28
 Function MaxVal(u, , );
begin
if u là lá của cây hạn chế hoặc đỉnh kết thúc then MaxValeval(u)
else for mỗi đỉnh v là con của u do
{  max[ ,MinVal(v, ,)];
if  then exit};
MaxVal  ;
end;
 Function MinVal(u, , );
begin
if u là lá của cây hạn chế hoặc đỉnh kết thúc then MinValeval(u)
else for mỗi đỉnh v là con của u do
{ min[,MaxVal(v, ,)];
if  then exit};
MinVal  ;
end;
Procedure Alpha_beta(u,v);
begin
 -;
;
for mỗi đỉnh w là con của u do 
if MinVal(w, , ) then
{  MinVal(w, , );
v w; }
end;
Lec 5. p.29
GT cắt tỉa - á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
Lec 5. p.30
Bài Tập Chương 4