Mục lục
Ph n I : Gi i quy t v n đ b ng tìm ki mầ ả ế ấ ề ằ ế
1.1 Ch ng I - Các chi n l c tìm ki m mùươ ế ượ ế
1.1 Bi u di n v n đ trong không gian tr ng tháiể ễ ấ ề ạ
1.2 Các chi n l c tìm ki mế ượ ế
1.3 Các chi n l c tìm ki m mùế ượ ế
1.3.1 Tìm ki m theo b r ngế ề ộ
1.3.2 Tìm ki m theo sâuế độ
1.3.3 Các tr ng thái l pạ ặ
1.3.4 Tìm ki m sâu l pế ặ
1.4 Quy v n v các v n con. Tìm ki m trên th v /ho cấ đề ề ấ đề ế đồ ị à ặ
1.4.1 Quy v n v các v n conấ đề ề ấ đề
1.4.2 th v /ho cĐồ ị à ặ
1.4.3 Tìm ki m trên th v /ho cế đồ ị à ặ
Ch ng II - Các chi n l c tìm ki m kinh nghi mươ ế ượ ế ệ
2.1 H m ánh giá v tìm ki m kinh nghi mà đ à ế ệ
2.2 Tìm ki m t t nh t - u tiênế ố ấ đầ
2.3 Tìm ki m leo iế đồ
2.4 Tìm ki m beamế
1.2 Ch ng III - Các chi n l c tìm ki m t i uươ ế ượ ế ố ư
3.1 Tìm ng i ng n nh tđườ đ ắ ấ
3.1.1 Thu t toán A*ậ
3.1.2 Thu t toán tìm ki m Nhánh-v -C nậ ế à ậ
1.2.1 3.2 Tìm i t ng t t nh tđố ượ ố ấ
1.2.1.1 3.2.1 Tìm ki m leo iế đồ
3.2.2 Tìm ki m gradientế
3.2.3 Tìm ki m mô ph ng luy n kimế ỏ ệ
1.2.2 3.3 Tìm ki m mô ph ng s ti n hóa. Thu t toán di truy nế ỏ ự ế ậ ề
1.3 Ch ng IV - Tìm ki m có i thươ ế đố ủ
4.1 Cây trò ch i v tìm ki m trên cây trò ch iơ à ế ơ

• Các k thu t tìm ki m mù, trong ó chúng ta không có hi u bi t gì v các iỹ ậ ế đ ể ế ề đố
t ng h ng d n tìm ki m m ch n thu n l xem xét theo m t h th ng n o ó t tượ để ướ ẫ ế à ỉ đơ ầ à ộ ệ ố à đ ấ
c các i t ng phát hi n ra i t ng c n tìm.ả đố ượ để ệ đố ượ ầ
• Các k thu t tìm ki m kinh nghi m (tìm ki m heuristic) trong ó chúng ta d aỹ ậ ế ệ ế đ ự
v o kinh nghi m v s hi u bi t c a chúng ta v v n c n gi i quy t xây d ng nênà ệ à ự ể ế ủ ề ấ đề ầ ả ế để ự
h m ánh giá h ng d n s tìm ki m.à đ ướ ẫ ự ế
• Các k thu t tìm ki m t i u.ỹ ậ ế ố ư
• Các ph ng pháp tìm ki m có i th , t c l các chi n l c tìm ki m n c iươ ế đố ủ ứ à ế ượ ế ướ đ
trong các trò ch i hai ng i, ch ng h n c vua, c t ng, c carô.ơ ườ ẳ ạ ờ ờ ướ ờ
Đinh Mạnh Tường Trang 3

Ch ng Iươ
Các chi n l c tìm ki m mùế ượ ế

Trong ch ng n y, chúng tôi s nghiên c u các chi n l c tìm ki m mù (blindươ à ẽ ứ ế ượ ế
search): tìm ki m theo b r ng (breadth-first search) v tìm ki m theo sâu (depth-ế ề ộ à ế độ
first search). Hi u qu c a các ph ng pháp tìm ki m n y c ng s c ánh giá.ệ ả ủ ươ ế à ũ ẽđượ đ
1.4 Bi u di n v n trong không gian tr ng tháiể ễ ấ đề ạ
M t khi chúng ta mu n gi i quy t m t v n n o ó b ng tìm ki m, u tiên taộ ố ả ế ộ ấ đề à đ ằ ế đầ
ph i xác nh không gian tìm ki m. ả đị ế Không gian tìm ki m bao g m t t c các i t ngế ồ ấ ả đố ượ
m ta c n quan tâm tìm ki m. Nó có th l không gian liên t c, ch ng h n không gianà ầ ế ể à ụ ẳ ạ
các véct th c n chi u; nó c ng có th l không gian các i t ng r i r c.ơ ự ề ũ ể à đố ượ ờ ạ
Trong m c n y ta s xét vi c bi u di n m t v n trong không gian tr ng tháiụ à ẽ ệ ể ễ ộ ấ đề ạ
sao cho vi c gi i quy t v n c quy v vi c tìm ki m trong không gian tr ng thái.ệ ả ế ấ đềđượ ề ệ ế ạ
M t ph m vi r ng l n các v n , c bi t các câu , các trò ch i, có th mô tộ ạ ộ ớ ấ đề đặ ệ đố ơ ể ả
b ng cách s d ng khái ni m tr ng thái v toán t (phép bi n i tr ng thái). Ch ngằ ử ụ ệ ạ à ử ế đổ ạ ẳ
h n, m t khách du l ch có trong tay b n m ng l i giao thông n i các th nh ph trongạ ộ ị ả đồ ạ ướ ố à ố
m t vùng lãnh th (hình 1.1), du khách ang th nh ph A v anh ta mu n tìm ngộ ổ đ ở à ố à ố đườ
i t i th m th nh ph B. Trong b i toán n y, các th nh ph có trong các b n l cácđ ớ ă à ố à à à ố ả đồ à
tr ng thái, th nh ph A l tr ng thái ban u, B l tr ng thái k t thúc. Khi ang m tạ à ố à ạ đầ à ạ ế đ ở ộ


Khi chúng ta bi u di n m t v n thông qua các tr ng thái v các toán t , thìể ễ ộ ấ đề ạ à ử
vi c tìm nghi m c a b i toán c quy v vi c tìm ng i t tr ng thái ban u t iệ ệ ủ à đượ ề ệ đườ đ ừ ạ đầ ớ
tr ng thái ích. (M t ng i trong không gian tr ng thái l m t dãy toán t d n m tạ đ ộ đườ đ ạ à ộ ử ẫ ộ
tr ng thái t i m t tr ng thái khác).ạ ớ ộ ạ
Chúng ta có th bi u di n không gian tr ng thái b ng th nh h ng, trong óể ể ễ ạ ằ đồ ị đị ướ đ
m i nh c a th t ng ng v i m t tr ng thái. N u có toán t R bi n i tr ng thái uỗ đỉ ủ đồ ị ươ ứ ớ ộ ạ ế ử ế đổ ạ
th nh tr ng thái v, thì có cung gán nhãn R i t nh u t i nh v. Khi ó m t ng ià ạ đ ừ đỉ ớ đỉ đ ộ đườ đ
trong không gian tr ng thái s l m t ng i trong th n y.ạ ẽ à ộ đườ đ đồ ị à
Sau ây chúng ta s xét m t s ví d v các không gian tr ng thái c xây d ngđ ẽ ộ ố ụ ề ạ đượ ự
cho m t s v n .ộ ố ấ đề
Ví d 1:ụ B i toán 8 s . Chúng ta có b ng 3x3 ô v tám quân mang s hi u t 1à ố ả à ố ệ ừ
n 8 c x p v o tám ô, còn l i m t ô tr ng, ch ng h n nh trong hình 2 bên trái.đế đượ ế à ạ ộ ố ẳ ạ ư
Trong trò ch i n y, b n có th chuy n d ch các quân c ch ô tr ng t i ô tr ng ó. V nơ à ạ ể ể ị ở ạ ố ớ ố đ ấ
c a b n l tìm ra m t dãy các chuy n d ch bi n i c nh hu ng ban u (hình 1.2đề ủ ạ à ộ ể ị để ế đổ ả ố đầ
bên trái) th nh m t c nh hu ng xác nh n o ó, ch ng h n c nh hu ng trong hình 1.2à ộ ả ố đị à đ ẳ ạ ả ố
bên ph i.ả
Trong b i toán n y, tr ng thái ban u l c nh hu ng bên trái hình 1.2, cònà à ạ đầ à ả ố ở
tr ng thái k t thúc bên ph i hình 1.2. T ng ng v i các quy t c chuy n d ch cácạ ế ở ả ươ ứ ớ ắ ể ị
quân, ta có b n toán t : ố ử up ( y quân lên trên), đẩ down ( y quân xu ng d i), đẩ ố ướ left ( yđẩ
quân sang trái), right ( y quân sang ph i). Rõ r ng l , các toán t n y ch l các toánđẩ ả à à ử à ỉ à
t b ph n; ch ng h n, t tr ng thái ban u (hình 1.2 bên trái), ta ch có th áp d ngử ộ ậ ẳ ạ ừ ạ đầ ỉ ể ụ
các toán t ửdown, left, right.
Trong các ví d trên vi c tìm ra m t bi u di n thích h p mô t các tr ng tháiụ ệ ộ ể ễ ợ để ả ạ
c a v n l khá d d ng v t nhiên. Song trong nhi u v n vi c tìm hi u c bi uủ ấ đề à ễ à à ự ề ấ đề ệ ể đượ ể
di n thích h p cho các tr ng thái c a v n l ho n to n không n gi n. Vi c tìm raễ ợ ạ ủ ấ đề à à à đơ ả ệ
d ng bi u di n t t cho các tr ng thái óng vai trò h t s c quan tr ng trong quá trìnhạ ể ễ ố ạ đ ế ứ ọ
Đinh Mạnh Tường Trang 5

gi i quy t m t v n . Có th nói r ng, n u ta tìm c d ng bi u di n t t cho cácả ế ộ ấ đề ể ằ ế đượ ạ ể ễ ố

trong b i toán toán s , phát tri n tr ng thái ban u (hình 2 bên trái), ta nh n c baà ố ể ạ đầ ậ đượ
tr ng thái k (hình 1.3).ạ ề
Khi chúng ta bi u di n m t v n c n gi i quy t thông qua các tr ng thái v cácể ễ ộ ấ đề ầ ả ế ạ à
toán t thì vi c tìm l i gi i c a v n c quy v vi c tìm ng i t tr ng thái banử ệ ờ ả ủ ấ đềđượ ề ệ đườ đ ừ ạ
u t i m t tr ng thái k t thúc n o ó.đầ ớ ộ ạ ế à đ
Có th phân các chi n l c tìm ki m th nh hai lo i:ể ế ượ ế à ạ
• Các chi n l c tìm ki m mù. Trong các chi n l c tìm ki m n y, không có m tế ượ ế ế ượ ế à ộ
s h ng d n n o cho s tìm ki m, m ta ch phát tri n các tr ng thái ban u cho t iự ướ ẫ à ự ế à ỉ ể ạ đầ ớ
khi g p m t tr ng thái ích n o ó. Có hai k thu t tìm ki m mù, ó l tìm ki m theoặ ộ ạ đ à đ ỹ ậ ế đ à ế
b r ng v tìm ki m theo sâu.ề ộ à ế độ
Đinh Mạnh Tường Trang 6

T t ng c a tìm ki m theo b r ng l các tr ng thái c phát tri n theo th tư ưở ủ ế ề ộ à ạ đượ ể ứ ự
m chúng c sinh ra, t c l tr ng thái n o c sinh ra tr c s c phát tri n tr c.à đượ ứ à ạ à đượ ướ ẽđượ ể ướ
Trong nhi u v n , dù chúng ta phát tri n các tr ng thái theo h th ng n o (theoề ấ đề ể ạ ệ ố à
b r ng ho c theo sâu) thì s l ng các tr ng thái c sinh ra tr c khi ta g p tr ngề ộ ặ độ ố ượ ạ đượ ướ ặ ạ
thái ích th ng l c c k l n. Do ó các thu t toán tìm ki m mù kém hi u qu , òiđ ườ à ự ỳ ớ đ ậ ế ệ ả đ
h i r t nhi u không gian v th i gian. Trong th c t , nhi u v n không th gi i quy tỏ ấ ề à ờ ự ế ề ấ đề ể ả ế
c b ng tìm ki m mù.đượ ằ ế
• Tìm ki m kinh nghi m (tìm ki m heuristic). Trong r t nhi u v n , chúng ta cóế ệ ế ấ ề ấ đề
th d a v o s hi u bi t c a chúng ta v v n , d a v o kinh nghi m, tr c giác, ể ự à ự ể ế ủ ề ấ đề ự à ệ ự để
ánh giá các tr ng thái. S d ng s ánh giá các tr ng thái h ng d n s tìm ki m:đ ạ ử ụ ựđ ạ để ướ ẫ ự ế
trong quá trình phát tri n các tr ng thái, ta s ch n trong s các tr ng thái ch phátể ạ ẽ ọ ố ạ ờ
tri n, tr ng thái c ánh giá l t t nh t phát tri n. Do ó t c tìm ki m s nhanhể ạ đượ đ à ố ấ để ể đ ố độ ế ẽ
h n. Các ph ng pháp tìm ki m d a v o s ánh giá các tr ng thái h ng d n sơ ươ ế ự à ự đ ạ để ướ ẫ ự
tìm ki m g i chung l các ph ng pháp tìm ki m kinh nghi m.ế ọ à ươ ế ệ
Nh v y chi n l c tìm ki m c xác nh b i chi n l c ch n tr ng thái ư ậ ế ượ ế đượ đị ở ế ượ ọ ạ để
phát tri n m i b c. Trong tìm ki m mù, ta ch n tr ng thái phát tri n theo th tể ở ỗ ướ ế ọ ạ để ể ứ ự
m úng c sinh ra; còn trong tìm ki m kinh nghi m ta ch n tr ng thái d a v o sà đ đượ ế ệ ọ ạ ự à ự
ánh giá các tr ng thái.đ ạ

procedure
Breadth_First_Search
;
begin
1. Kh i t o danh sách L ch ch a tr ng thái ban u;ở ạ ỉ ứ ạ đầ
2.
loop do
2.1
if
L r ngỗ
then
{
thông báo tìm ki m th t b iế ấ ạ
;

stop};
Đinh Mạnh Tường Trang 8

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 tìm ki m thành côngế
; stop};
2.4

d
. Do ó s l n nh t các nh c n xem xét l :đ ố ớ ấ đỉ ầ à
1 + b + b
2
+ + b
d
Nh v y, ph c t p th i gian c a thu t toán tìm ki m theo b r ng l O(bư ậ độ ứ ạ ờ ủ ậ ế ề ộ à
d
). Độ
ph c t p không gian c ng l O(bứ ạ ũ à
d
), b i vì ta c n l u v o danh sách L t t c các nhở ầ ư à ấ ả đỉ
c a cây tìm ki m m c d, s các nh n y l bủ ế ở ứ ố đỉ à à
d
.
th y rõ tìm ki m theo b r ng òi h i th i gian v không gian l n t i m c n o,Để ấ ế ề ộ đ ỏ ờ à ớ ớ ứ à
ta xét tr ng h p nhân t nhánh b = 10 v sâu d thay i. Gi s phát hi n vườ ợ ố à độ đổ ả ử để ệ à
ki m tra 1000 tr ng thái c n 1 giây, v l u gi 1 tr ng thái c n 100 bytes. Khi ó th iể ạ ầ à ư ữ ạ ầ đ ờ
gian v không gian m thu t toán òi h i c cho trong b ng sau:à à ậ đ ỏ đượ ả
sâu dĐộ Th i gianờ Không gian
4 11 giây 1 megabyte
6 18 giây 111 megabytes
8 31 giờ 11 gigabytes
10 128 ng yà 1 terabyte
12 35 n mă 111 terabytes
14 3500 n mă 11.111 terabytes
Đinh Mạnh Tường Trang 9

1.6.2 Tìm ki m theo sâuế độ
Nh ta ã bi t, t t ng c a chi n l c tìm ki m theo sâu l , t i m i b cư đ ế ư ưở ủ ế ượ ế độ à ạ ỗ ướ

c n l u ít h n db nh. Do ó ph c t p không gian c a tìm ki m theo sâu lầ ư ơ đỉ đ độ ứ ạ ủ ế độ à
O(db), trong khi ó tìm ki m theo b r ng òi h i không gian nh O(bđ ế ề ộ đ ỏ ớ
d
)!
1.6.3 Các tr ng thái l pạ ặ
Nh ta th y trong m c 1.2, cây tìm ki m có th ch a nhi u nh ng v i cùng m tư ấ ụ ế ể ứ ề đỉ ứ ớ ộ
tr ng thái, các tr ng thái n y c g i l tr ng thái l p. Ch ng h n, trong cây tìm ki mạ ạ à đượ ọ à ạ ặ ẳ ạ ế
hình 4b, các tr ng thái C, E, F l các tr ng thái l p. Trong th bi u di n không gianạ à ạ ặ đồ ị ể ễ
tr ng thái, các tr ng thái l p ng v i các nh có nhi u ng i d n t i nó t tr ng tháiạ ạ ặ ứ ớ đỉ ề đườ đ ẫ ớ ừ ạ
ban u. N u th có chu trình thì cây tìm ki m s ch a các nhánh v i m t s nhđầ ế đồ ị ế ẽ ứ ớ ộ ố đỉ
l p l i vô h n l n. Trong các thu t toán tìm ki m s lãng phí r t nhi u th i gian ậ ạ ạ ầ ậ ế ẽ ấ ề ờ để
phát tri n l i các tr ng thái m ta ã g p v ã phát tri n. ể ạ ạ à đ ặ à đ ể Vì v y trong quá trình tìmậ
ki m ta c n tránh phát sinh ra các tr ng thái m ta ã phát tri n. Chúng ta có th ápế ầ ạ à đ ể ể
d ng m t trong các gi i pháp sau ây:ụ ộ ả đ
1. Khi phát tri n nh u, không sinh ra các nh trùng v i cha c a u.ể đỉ đỉ ớ ủ
2. Khi phát tri n nh u, không sinh ra các nh trùng v i m t nh n o ó n m trênể đỉ đỉ ớ ộ đỉ à đ ằ
ng i d n t i u.đườ đ ẫ ớ
3. Không sinh ra các nh m nó ã c sinh ra, t c l ch sinh ra các nh m i.đỉ à đ đượ ứ à ỉ đỉ ớ
Hai gi i pháp u d c i t v không t n nhi u không gian nh , tuy nhiên cácả đầ ễ à đặ à ố ề ớ
gi i pháp n y không tránh c h t các tr ng thái l p.ả à đượ ế ạ ặ
Đinh Mạnh Tường Trang 10

th c hi n gi i pháp th 3 ta c n l u các tr ng thái ã phát tri n v o t p Q, l uĐể ự ệ ả ứ ầ ư ạ đ ể à ậ ư
các tr ng thái ch phát tri n v o danh sách L. ng nhiên, tr ng thái v l n u cạ ờ ể à Đươ ạ ầ đầ đượ
sinh ra n u nó không có trong Q v L. Vi c l u các tr ng thái ã phát tri n v ki m traế à ệ ư ạ đ ể à ể
xem m t tr ng thái có ph i l n u c sinh ra không òi h i r t nhi u không gian vộ ạ ả ầ đầ đượ đ ỏ ấ ề à
th i gian. Chúng ta có th c i t t p Q b i b ng b m (xem [ ]).ờ ể à đặ ậ ở ả ă
1.6.4 Tìm ki m sâu l pế ặ
Nh chúng ta ã nh n xét, n u cây tìm ki m ch a nhánh vô h n, khi s d ng tìmư đ ậ ế ế ứ ạ ử ụ
ki m theo sâu, ta có th m c k t nhánh ó v không tìm ra nghi m. kh c ph cế độ ể ắ ẹ ở đ à ệ Để ắ ụ

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
if
depth(u) <= d
then
for
m i tr ng thái v k uỗ ạ ề
do
{
t v vào u danh sách LĐặ đầ
;
depth(v) depth(u) + 1
};
end;
procedure
Depth_Deepening_Search
;
begin
for
d  0
to
max

+ + 2b
d-1
+ 1b
d
Do ó th i gian tìm ki m sâu l p l O(bđ ờ ế ặ à
d
).
Tóm l i, tìm ki m sâu l p có ph c t p th i gian l O(bạ ế ặ độ ứ ạ ờ à
d
) (nh tìm ki m theoư ế
b r ng), v có ph c t p không gian l O(bi u di n) (nh tìm ki m theo sâu). Nóiề ộ à độ ứ ạ à ể ễ ư ế độ
chung, chúng ta nên áp d ng tìm ki m sâu l p cho các v n có không gian tr ng tháiụ ế ặ ấ đề ạ
l n v sâu c a nghi m không bi t tr c.ớ àđộ ủ ệ ế ướ
1.7 Quy v n v các v n con. Tìm ki m trên th v /ho c.ấ đề ề ấ đề ế đồ ị à ặ
1.7.1 Quy v n v các v n con:ấ đề ề ấ đề
Trong m c 1.1, chúng ta ã nghiên c u vi c bi u di n v n thông qua các tr ngụ đ ứ ệ ể ễ ấ đề ạ
thái v các toán t . Khi ó vi c tìm nghi m c a v n c quy v vi c tìm ngà ử đ ệ ệ ủ ấ đề đượ ề ệ đườ
trong không gian tr ng thái. Trong m c n y chúng ta s nghiên c u m t ph ng phápạ ụ à ẽ ứ ộ ươ
lu n khác gi i quy t v n , d a trên vi c quy v n v các v n con. Quy v n ậ để ả ế ấ đề ự ệ ấ đề ề ấ đề ấ đề
v các v n con (còn g i l rút g n v n ) l m t ph ng pháp c s d ng r ng rãiề ấ đề ọ à ọ ấ đề à ộ ươ đượ ử ụ ộ
nh t gi i quy t các v n . Trong i s ng h ng ng y, c ng nh trong khoa h c kấ để ả ế ấ đề đờ ố à à ũ ư ọ ỹ
thu t, m i khi g p m t v n c n gi i quy t, ta v n th ng c g ng tìm cách a nó vậ ỗ ặ ộ ấ đề ầ ả ế ẫ ườ ố ắ đư ề
các v n n gi n h n. Quá trình rút g n v n s c ti p t c cho t i khi ta d n t iấ đềđơ ả ơ ọ ấ đề ẽđượ ế ụ ớ ẫ ớ
các v n con có th gi i quy t c d d ng. ấ đề ể ả ế đượ ễ à Sau ây chúng ta xét m t s v n .đ ộ ố ấ đề
V n đ tính tích phân b t đ nhấ ề ấ ị
Gi s ta c n tính m t tích phân b t nh, ch ng h n ả ử ầ ộ ấ đị ẳ ạ ∫ (xe
x
+ x
3
) dx. Quá trình

thái v các toán t . à ử ở ây, b i toán c n gi i l tr ng thái ban u. M i cách quy b iđ à ầ ả à ạ đầ ỗ à
toán v các b i toán con c bi u di n b i m t toán t , toán t Aề à đượ ể ễ ở ộ ử ử →B, C bi u di n vi cể ễ ệ
quy b i toán A v hai b i toán B v C. Ch ng h n, i v i b i toán tính tích phân b tà ề à à ẳ ạ đố ớ à ấ
nh, ta có th xác nh các toán t d ng:đị ể đị ử ạ
∫ (f
1
+ f
2
) dx → ∫ f
1
dx, ∫ f
2
dx và ∫ u dv → ∫ v du
Các tr ng thái k t thúc l các b i toán s c p (các b i toán ã bi t cách gi i).ạ ế à à ơ ấ à đ ế ả
Ch ng h n, trong b i toán tính tích phân, các tích phân c b n l các tr ng thái k tẳ ạ à ơ ả à ạ ế
thúc. M t i u c n l u ý l , trong không gian tr ng thái bi u di n vi c quy v n vộ đề ầ ư à ạ ể ễ ệ ấ đề ề
các v n con, các toán t có th l a tr , nó bi n i m t tr ng thái th nh nhi u tr ngấ đề ử ể àđ ị ế đổ ộ ạ à ề ạ
thái khác.
V n đ tìm đ ng đi trên b n đ giao thôngấ ề ườ ả ồ
B i toán n y ã c phát tri n nh b i toán tìm ng i trong không gian tr ngà à đ đượ ể ư à đườ đ ạ
thái (xem 1.1), trong ó m i tr ng thái ng v i m t th nh ph , m i toán t ng v i m tđ ỗ ạ ứ ớ ộ à ố ỗ ửứ ớ ộ
con ng n i, n i th nh ph n y v i th nh ph khác. Bây gi ta a ra m t cách bi uđườ ố ố à ố à ớ à ố ờ đư ộ ể
di n khác d a trên vi c quy v n v các v n con. Gi s ta có b n giao thôngễ ự ệ ấ đề ề ấ đề ả ử ả đồ
trong m t vùng lãnh th (xem hình 1.6). Gi s ta c n tìm ng i t th nh ph A t iộ ổ ả ử ầ đườ đ ừ à ố ớ
th nh ph B. Có con sông ch y qua hai th nh ph E v G v có c u qua sông m ià ố ả à ố à à ầ ở ỗ
th nh ph ó. M i ng i t A n B ch có th qua E ho c G. Nh v y b i toán tìmà ốđ ọ đườ đ ừ đế ỉ ể ặ ư ậ à
ng i t A n B c quy v :đườ đ ừ đế đượ ề
1) B i toán tìm ng i t A n B qua E (ho c)à đườ đ ừ đế ặ
2) B i toán tìm ng i t A n b qua G.à đườ đ ừ đế
M i m t trong hai b i toán trên l i có th phân nh nh sauỗ ộ à ạ ể ỏ ư

R
2
: a →d, k
R
3
: a →g, h
Đinh Mạnh Tường Trang 14

R
4
: d →b, c
R
5
: f →i
R
6
: f →c, j
R
7
: k →e, l
R
8
: k →h
• T p các tr ng thái k t thúc (các b i toán s c p) l T = {b, c, e, j, l}.ậ ạ ế à ơ ấ à
Không gian tr ng thái trên có th bi u di n b i th v /ho c trong hình 1.9.ạ ể ể ễ ở đồ ị à ặ
Trong th ó, các nh, ch ng h n ađồ ị đ đỉ ẳ ạ
1
, a
2
, a


Khi ã có các toán t rút g n v n , thì b ng cách áp d ng liên ti p các toán t ,đ ử ọ ấ đề ằ ụ ế ử
ta có th a b i toán c n gi i v m t t p các b i toán con. Ch ng h n, trong ví d trênểđư à ầ ả ề ộ ậ à ẳ ạ ụ
n u ta áp d ng các toán t Rế ụ ử
1
, R
4
, R
6
, ta s quy b i toán a v t p các b i toán con {b, c,ẽ à ề ậ à
e, f}, t t c các b i toán con n y u l s c p. ấ ả à à đề à ơ ấ T các toán t Rừ ử
1
, R
4
v Rà
6
ta xây d ngự
c m t cây trong hình 1.11a, cây n y c g i l cây nghi m. Cây nghi m cđượ ộ à đượ ọ à ệ ệ đượ
nh ngh a nh sau:đị ĩ ư
Cây nghi mệ l m t cây, trong ó:à ộ đ
• G c c a cây ng v i b i toán c n gi i.ố ủ ứ ớ à ầ ả
• T t c các lá c a cây l các nh k t thúc ( nh ng v i các b i toán s c p).ấ ả ủ à đỉ ế đỉ ứ ớ à ơ ấ
• N u u l nh trong c a cây, thì các nh con c a u l các nh k u theo m tế à đỉ ủ đỉ ủ à đỉ ề ộ
toán t n o ó.ử à đ
Các nh c a th v /ho c s c g n nhãn gi i c ho c không gi i c.đỉ ủ đồ ị à ặ ẽđượ ắ ả đượ ặ ả đượ
Các nh đỉ gi i cả đượ c xác nh quy nh sau:đượ đị đệ ư
• Các nh k t thúc l các nh đỉ ế à đỉ gi i cả đượ .
• N u u không ph i l nh k t thúc, nh ng có m t toán t R sao cho t t c cácế ả à đỉ ế ư ộ ử ấ ả
nh k u theo R u gi i c thì u đỉ ề đề ả đượ gi i cả đượ .
Các nh đỉ không gi i cả đượ c xác nh quy nh sau:đượ đị đệ ư

theo m i toán t u g p các nh k c ánh d u không gi i c, thì u c ánhọ ửđề ặ đỉ ề đượ đ ấ ả đượ đượ đ
d u không gi i c v quay lên cha c a u.ấ ả đượ à ủ
Ta s bi u di n th t c tìm ki m theo sâu v ánh d u các nh ã trình b yẽ ể ễ ủ ụ ế độ à đ ấ đỉ đ à
trên b i h m quy Solvable(u). H m n y nh n giá tr true n u u gi i c v nh n giáở à đệ à à ậ ị ế ả đượ à ậ
tr ị false n u u không gi i c. Trong h m Solvable(u), ta s s d ng:ế ả đượ à ẽ ử ụ
• Bi n Ok. V i m i toán t R áp d ng c t i u, bi n Ok nh n giá tr ế ớ ỗ ử ụ đượ ạ ế ậ ị true n u t tế ấ
c các nh v k u theo R u gi i c, v Ok nh n giá tr ả đỉ ề đề ả đượ à ậ ị false n u có m t nh v k uế ộ đỉ ề
theo R không gi i c.ả đượ
• H m Operator(u) ghi l i toán t áp d ng th nh công t i u, t c l Operator(u) = Rà ạ ử ụ à ạ ứ à
n u m i nh v k u theo R u gi i c.ế ọ đỉ ề đề ả đượ
function
Solvable(u)
;
begin
1.
if
u là nh k t thúcđỉ ế
then
{
Solvable 
true; stop};
2.
if
u không là nh k t thúc và không có nh kđỉ ế đỉ ề
then
{
Solvable(u) 
false; stop};
3.
for


nó b xa l y khi i xu ng nhánh vô h n. Trong tr ng h p n y ta nên s d ng thu t toánị ầ đ ố ạ ườ ợ à ử ụ ậ
tìm ki m sâu l p (m c 1.3.3).ế ặ ụ
N u b i toán ban u gi i c, thì b ng cách s d ng h m Operator ta s xâyế à đầ ả đượ ằ ử ụ à ẽ
d ng c cây nghi m.ự đượ ệ
Đinh Mạnh Tường Trang 18

Ch ng IIươ
Các chi n l c tìm ki m kinh nghi mế ượ ế ệ

Trong ch ng I, chúng ta ã nghiên c u vi c bi u di n v n trong không gianươ đ ứ ệ ể ễ ấ đề
tr ng thái v các k thu t tìm ki m mù. Các k thu t tìm ki m mù r t kém hi u qu vạ à ỹ ậ ế ỹ ậ ế ấ ệ ả à
trong nhi u tr ng h p không th áp d ng c. Trong ch ng n y, chúng ta s nghiênề ườ ợ ể ụ đượ ươ à ẽ
c u các ph ng pháp tìm ki m kinh nghi m (tìm ki m heuristic), ó l các ph ngứ ươ ế ệ ế đ à ươ
pháp s d ng h m ánh giá h ng d n s tìm ki m.ử ụ à đ để ướ ẫ ự ế
H m ánh giá v tìm ki m kinh nghi m:à đ à ế ệ
Trong nhi u v n , ta có th s d ng kinh nghi m, tri th c c a chúng ta v v nề ấ đề ể ử ụ ệ ứ ủ ề ấ
ánh giá các tr ng thái c a v n . V i m i tr ng thái u, chúng ta s xác nh m tđềđểđ ạ ủ ấ đề ớ ỗ ạ ẽ đị ộ
giá tr s h(u), s n y ánh giá ị ố ố à đ “s g n íchự ầ đ ” c a tr ng thái u. H m h(u) c g i lủ ạ à đượ ọ à
h m ánh giáà đ . Chúng ta s s d ng h m ánh giá h ng d n s tìm ki m. Trongẽ ử ụ à đ để ướ ẫ ự ế
quá trình tìm ki m, t i m i b c ta s ch n tr ng thái phát tri n l tr ng thái có giáế ạ ỗ ướ ẽ ọ ạ để ể à ạ
tr h m ánh giá nh nh t, tr ng thái n y c xem l tr ng thái có nhi u h a h n nh tị à đ ỏ ấ ạ à đượ à ạ ề ứ ẹ ấ
h ng t i ích.ướ ớ đ
Các k thu t tìm ki m s d ng h m ánh giá h ng d n s tìm ki m c g iỹ ậ ế ử ụ à đ để ướ ẫ ự ế đượ ọ
chung l các k thu t tìm ki m kinh nghi m (heuristic search). Các giai o n c b n à ỹ ậ ế ệ đ ạ ơ ả để
gi i quy t v n b ng tìm ki m kinh nghi m nh sau:ả ế ấ đề ằ ế ệ ư
1. Tìm bi u di n thích h p mô t các tr ng thái v các toán t c a v n .ể ễ ợ ả ạ à ử ủ ấ đề
2. Xây d ng h m ánh giá.ự à đ
3. Thi t k chi n l c ch n tr ng thái phát tri n m i b c. ế ế ế ượ ọ ạ để ể ở ỗ ướ
H m đánh giáà

2
(u) = 2 + 3 + 1 + 3 = 9
Vì quân 3 c n ít nh t 2 d ch chuy n, quân 8 c n ít nh t 3 d ch chuy n, quân 6ầ ấ ị ể ầ ấ ị ể
c n ít nh t 1 d ch chuy n v quân 1 c n ít nh t 3 d ch chuy n.ầ ấ ị ể à ầ ấ ị ể
Hai chi n l c tìm ki m kinh nghi m quan tr ng nh t l tìm ki m t t nh t - uế ượ ế ệ ọ ấ à ế ố ấ đầ
tiên (best-first search) v tìm ki m leo i (hill-climbing search). Có th xác nh cácà ế đồ ể đị
chi n l c n y nh sau:ế ượ à ư
Tìm ki m t t nh t u tiênế ố ấ đầ = Tìm ki m theo b r ngế ề ộ + H m ánh giáà đ
Tìm ki m leo iế đồ = Tìm ki m theo sâuế độ + H m ánh giáà đ
Chúng ta s l n l t nghiên c u các k thu t tìm ki m n y trong các m c sau.ẽ ầ ượ ứ ỹ ậ ế à ụ
Tìm ki m t t nh t - u tiên:ế ố ấ đầ
Tìm ki m t t nh t - u tiên (best-first search) l tìm ki m theo b r ng cế ố ấ đầ à ế ề ộ đượ
h ng d n b i h m ánh giá. Nh ng nó khác v i tìm ki m theo b r ng ch , trongướ ẫ ở à đ ư ớ ế ề ộ ở ỗ
tìm ki m theo b r ng ta l n l t phát tri n t t c các nh m c hi n t i sinh ra cácế ề ộ ầ ượ ể ấ ả đỉ ở ứ ệ ạ để
nh m c ti p theo, còn trong tìm ki m t t nh t - u tiên ta ch n nh phát tri nđỉ ở ứ ế ế ố ấ đầ ọ đỉ để ể
l nh t t nh t c xác nh b i h m ánh giá (t c l nh có giá tr h m ánh giá làđỉ ố ấ đượ đị ở à đ ứ à đỉ ị à đ à
nh nh t), nh n y có th m c hi n t i ho c các m c trên.ỏ ấ đỉ à ểở ứ ệ ạ ặ ở ứ
Đinh Mạnh Tường Trang 20

Ví dụ: Xét không gian tr ng thái c bi u di n b i th trong hình 2.2, trongạ đượ ể ễ ở đồ ị
ó tr ng thái ban u l A, tr ng thái k t thúc l B. Giá tr c a h m ánh giá l các sđ ạ đầ à ạ ế à ị ủ à đ à ố
ghi c nh m i nh. Quá trình tìm ki m t t nh t - u tiên di n ra nh sau: u tiênạ ỗ đỉ ế ố ấ đầ ễ ư Đầ
phát tri n nh A sinh ra các nh k l C, D v E. Trong ba nh n y, nh D có giá trể đỉ đỉ ề à à đỉ à đỉ ị
h m ánh giá nh nh t, nó c ch n phát tri n v sinh ra F, I. Trong s các nhà đ ỏ ấ đượ ọ để ể à ố đỉ
ch a c phát tri n C, E, F, I thì nh E có giá tr ánh giá nh nh t, nó c ch n ư đượ ể đỉ ị đ ỏ ấ đượ ọ để
phát tri n v sinh ra các nh G, K. Trong s các nh ch a c phát tri n thì G t tể à đỉ ố đỉ ư đượ ể ố
nh t, phát tri n G sinh ra B, H. n ây ta ã t t i tr ng thái k t thúc. Cây tìm ki mấ ể Đế đ đ đạ ớ ạ ế ế
t t nh t - u tiên c bi u di n trong hình 2.3.ố ấ đầ đượ ể ễ
Sau ây l th t c tìm ki m t t nh t - u tiên. Trong th t c n y, chúng ta sđ à ủ ụ ế ố ấ đầ ủ ụ à ử
d ng danh sách L l u các tr ng thái ch phát tri n, danh sách c s p theo th tụ để ư ạ ờ ể đượ ắ ứ ự

Xen v vào danh sách L sao cho L c s p theo th tđượ ắ ứ ự
t ng d n c a hàm ánh giáă ầ ủ đ
;
end;
Tìm ki m leo i:ế đồ
Tìm ki m leo i (hill-climbing search) l tìm ki m theo sâu c h ng d nế đồ à ế độ đượ ướ ẫ
b i h m ánh giá. Song khác v i tìm ki m theo sâu, khi ta phát tri n m t nh u thìở à đ ớ ế độ ể ộ đỉ
b c ti p theo, ta ch n trong s các nh con c a u, nh có nhi u h a h n nh t phátướ ế ọ ố đỉ ủ đỉ ề ứ ẹ ấ để
tri n, nh n y c xác nh b i h m ánh giá.ể đỉ à đượ đị ở à đ
Đinh Mạnh Tường Trang 21

Ví dụ: Ta l i xét th không gian tr ng thái trong hình 2.2. Quá trình tìm ki mạ đồ ị ạ ế
leo i c ti n h nh nh sau. u tiên phát tri n nh A sinh ra các nh con C, D, E.đồ đượ ế à ư Đầ ể đỉ đỉ
Trong các nh n y ch n D phát tri n, v nó sinh ra các nh con B, G. Quá trìnhđỉ à ọ để ể à đỉ
tìm ki m k t thúc. Cây tìm ki m leo i c cho trong hình 2.4. ế ế ế đồ đượ
Trong th t c tìm ki m leo i c trình b y d i ây, ngo i danh sách L l uủ ụ ế đồ đượ à ướ đ à ư
các tr ng thái ch c phát tri n, chúng ta s d ng danh sách Lạ ờ đượ ể ử ụ
1
l u gi t m th iđể ư ữ ạ ờ
các tr ng thái k tr ng thái u, khi ta phát tri n u. Danh sách Lạ ề ạ ể
1
c s p x p theo th tđượ ắ ế ứ ự
t ng d n c a h m ánh giá, r i c chuy n v o danh sách L sao tr ng thái t t nh t kă ầ ủ à đ ồ đượ ể à ạ ố ấ ề
u ng danh sách L.đứ ở
procedure
Hill_Climbing_Search
;
begin
1. Kh i t o danh sách L ch ch a tr ng thái ban uở ạ ỉ ứ ạ đầ
;

;
end;
Tìm ki m beamế
Tìm ki m beam (beam search) gi ng nh tìm ki m theo b r ng, nó phát tri nế ố ư ế ề ộ ể
các nh m t m c r i phát tri n các nh m c ti p theo. Tuy nhiên, trong tìm ki mđỉ ở ộ ứ ồ ể đỉ ở ứ ế ế
theo b r ng, ta phát tri n t t c các nh m t m c, còn trong tìm ki m beam, ta h nề ộ ể ấ ả đỉ ở ộ ứ ế ạ
ch ch phát tri n k nh t t nh t (các nh n y c xác nh b i h m ánh giá). Do óế ỉ ể đỉ ố ấ đỉ à đượ đị ở à đ đ
trong tìm ki m beam, b t k m c n o c ng ch có nhi u nh t k nh c phát tri n,ế ở ấ ỳ ứ à ũ ỉ ề ấ đỉ đượ ể
trong khi tìm ki m theo b r ng, s nh c n phát tri n m c d l bế ề ộ ố đỉ ầ ể ở ứ à
d
(b l nhân tà ố
nhánh).
Đinh Mạnh Tường Trang 22

Ví dụ: Chúng ta l i xét th không gian tr ng thái trong hình 2.2. Ch n k = 2.ạ đồ ị ạ ọ
Khi ó cây tìm ki m beam c cho nh hình 2.5. Các nh c g ch d i l các nhđ ế đượ ư đỉ đượ ạ ướ à đỉ
c ch n phát tri n m i m c.đượ ọ để ể ở ỗ ứ
Đinh Mạnh Tường Trang 23

Ch ng IIIươ
Các chi n l c tìm ki m t i uế ượ ế ố ư

V n tìm ki m t i u, m t cách t ng quát, có th phát bi u nh sau. M i iấ đề ế ố ư ộ ổ ể ể ư ỗ đố
t ng x trong không gian tìm ki m c g n v i m t s o giá tr c a i t ng ó f(x),ượ ế đượ ắ ớ ộ ốđ ị ủ đố ượ đ
m c tiêu c a ta l tìm i t ng có giá tr f(x) l n nh t (ho c nh nh t) trong khôngụ ủ à đố ượ ị ớ ấ ặ ỏ ấ
gian tìm ki m. H m f(x) c g i l h m m c tiêu. Trong ch ng n y chúng ta sế à đượ ọ à à ụ ươ à ẽ
nghiên c u các thu t toán tìm ki m sau:ứ ậ ế
• Các k thu t tìm ng i ng n nh t trong không gian tr ng thái: Thu t toán A*,ỹ ậ đườ đ ắ ấ ạ ậ
thu t toán nhánh_v _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,ỹ ậ ế đố ượ ố ấ ế đồ ế

0
t i tr ngớ ạ
thái u không ph i l tr ng thái ích c g i l ả à ạ đ đượ ọ à ng i m t ph nđườ đ ộ ầ , phân bi t v iđể ệ ớ
ng i y đườ đ đầ đủ, l ng i t uà đườ đ ừ
0
t i tr ng thái ích).ớ ạ đ
• h(u) l ánh giá d i ng i ng n nh t t u t i tr ng thái ích.àđ độ à đườ đ ắ ấ ừ ớ ạ đ
H m h(u) c g i l à đượ ọ à ch p nh n c ấ ậ đượ (ho c ánh giá th pặ đ ấ ) n u v i m i tr ngế ớ ọ ạ
thái u, h(u) ≤ d i ng i ng n nh t th c t t u t i tr ng thái ích. Ch ng h n trongđộ à đườ đ ắ ấ ự ế ừ ớ ạ đ ẳ ạ
b i toán tìm ng i ng n nh t trên b n giao thông, ta có th xác nh h(u) l à đườ đ ắ ấ ả đồ ể đị à độ
d i ng chim bay t u t i ích.à đườ ừ ớ đ
Đinh Mạnh Tường Trang 24

Ta có th s d ng k thu t tìm ki m leo i v i h m ánh giá h(u). T t nhiênể ử ụ ỹ ậ ế đồ ớ à đ ấ
ph ng pháp n y ch cho phép ta tìm c ng i t ng i t t, ch a ch c ã lươ à ỉ đượ đườ đ ươ đố ố ư ắ đ à
ng i t i u.đườ đ ố ư
Ta c ng có th s d ng k thu t tìm ki m t t nh t u tiên v i h m ánh giá g(u).ũ ể ử ụ ỹ ậ ế ố ấ đầ ớ à đ
Ph ng pháp n y s tìm ra ng i ng n nh t, tuy nhiên nó có th kém hi u qu .ươ à ẽ đườ đ ắ ấ ể ệ ả
t ng hi u qu tìm ki m, ta s d ng h m ánh giá m i :Để ă ệ ả ế ử ụ à đ ớ
f(u) = g(u) + h(u)
T c l , f(u) l ánh giá d i ng i ng n nh t qua u t tr ng thái ban u t iứ à àđ độ à đườ đ ắ ấ ừ ạ đầ ớ
tr ng thái k t thúc.ạ ế
1.8.1 Thu t toán A*ậ
Thu t toán A* l thu t toán s d ng k thu t tìm ki m t t nh t u tiên v i h mậ à ậ ử ụ ỹ ậ ế ố ấ đầ ớ à
ánh giá f(u).đ
th y c thu t toán A* l m vi c nh th n o, ta xét th không gian tr ngĐể ấ đượ ậ à ệ ư ế à đồ ị ạ
thái trong hình 3.1. Trong ó, tr ng thái ban u l tr ng thái A, tr ng thái ích l B,đ ạ đầ à ạ ạ đ à
các s ghi c nh các cung l d i ng i, các s c nh các nh l giá tr c a h mố ạ à độ à đườ đ ố ạ đỉ à ị ủ à
h. u tiên, phát tri n nh A sinh ra các nh con C, D, E v F. Tính giá tr c a h m f t iĐầ ể đỉ đỉ à ị ủ à ạ
các nh n y ta có:đỉ à