Giáo trình trí tuệ nhân tạo- chương 2-CÁC CHIẾN LƯỢC TÌM KIẾM KINH NGHIỆM
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.
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.
2.1 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 ®Ò.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 1
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¸
Trong t×m kiÕm kinh nghiÖm, hµm ®¸nh gi¸ ®ãng vai trß cùc
kú quan träng. Chóng ta cã x©y dùng ®îc hµm ®¸nh gi¸ cho ta sù
®¸nh gi¸ ®óng c¸c tr¹ng th¸i th× t×m kiÕm míi hiÖu qu¶. NÕu hµm
®¸nh gi¸ kh«ng chÝnh x¸c, nã cã thÓ dÉn ta ®i chÖch híng vµ do
®ã t×m kiÕm kÐm hiÖu qu¶.
Hµm ®¸nh gi¸ ®îc x©y dùng tïy thuéc vµo vÊn ®Ò. Sau ®©y lµ
mét sè vÝ dô vÒ hµm ®¸nh gi¸:
• Trong bµi to¸n t×m kiÕm ®êng ®i trªn b¶n ®å giao th«ng, ta
cã thÓ lÊy ®é dµi cña ®êng chim bay tõ mét thµnh phè tíi mét
thµnh phè ®Ých lµm gi¸ trÞ cña hµm ®¸nh gi¸.
• Bµi to¸n 8 sè. Chóng ta cã thÓ ®a ra hai c¸ch x©y dùng hµm
®¸nh gi¸.
Hµm h 1: Víi mçi tr¹ng th¸i u th× h 1(u) lµ sè qu©n kh«ng n»m
®óng vÞ trÝ cña nã trong tr¹ng th¸i ®Ých. Ch¼ng h¹n tr¹ng th¸i
®Ých ë bªn ph¶i h×nh 2.1, vµ u lµ tr¹ng th¸i ë bªn tr¸i h×nh 2.1,
th× h 1(u) = 4, v× c¸c qu©n kh«ng ®óng vÞ trÝ lµ 3, 8, 6 vµ 1.
Hµm h 2: h 2(u) lµ tæng kho¶ng c¸ch gi÷a vÞ trÝ cña c¸c qu©n
trong tr¹ng th¸i u vµ vÞ trÝ cña nã trong tr¹ng th¸i ®Ých. ë ®©y
kho¶ng c¸ch ®îc hiÓu lµ sè Ýt nhÊt c¸c dÞch chuyÓn theo hµng
hoÆc cét ®Ó ®a mét qu©n tíi vÞ trÝ cña nã trong tr¹ng th¸i ®Ých.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 2
Ch¼ng h¹n víi tr¹ng th¸i u vµ tr¹ng th¸i ®Ých nh trong h×nh 2.1, ta
cã:
h 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.
2.2 T×m kiÕm tèt nhÊt - ®Çu tiªn:
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 3
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¸. Nhng 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.
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 cha ®îc ph¸t
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 4
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
cha ®î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 ®Ó lu c¸c tr¹ng th¸i chê ph¸t
triÓn, danh s¸ch ®îc s¾p theo thø tù t¨ng dÇn cña hµm ®¸nh gi¸
sao cho tr¹ng th¸i cã gi¸ trÞ hµm ®¸nh gi¸ nhá nhÊt ë ®Çu danh
s¸ch.
procedure Best_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 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
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;
2.3 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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 5
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¸.
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 lu c¸c tr¹ng th¸i chê ®îc ph¸t triÓn, chóng ta sö dông
danh s¸ch L 1 ®Ó lu 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;
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};
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 6
2.3 for mçi tr¹ng th¸i v kÒ u do ®Æt v vµo L 1;
2.5 S¾p xÕp L 1 theo thø tù t¨ng dÇn cña hµm ®¸nh gi¸;
2.6 ChuyÓn danh s¸ch L 1 vµo ®Çu danh s¸ch L ;
end;
2.4 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µ bd (b
lµ nh©n tè nh¸nh).
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.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 2 - Trang 7
