Hoàng Kiếm Thuật toán thuật giải
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.73 MB, 99 trang )
"Don't study, don't know - Studying you will know!"
NGUYEN TRUNG HOA
GS.TSKH HOÀNG KI M
GIÁO TRÌNH MÔN H C
THU T TOÁN THU T GI I
CHƯƠNG 1 : THU T TOÁN – THU T GI I
I. KHÁI NI M THU T TOÁN – THU T GI I
II. THU T GI I HEURISTIC
III. CÁC PHƯƠNG PHÁP TÌM KI M HEURISTIC
III.1. C u trúc chung c$a bài toán tìm ki.m
III.2. Tìm ki.m chi0u sâu và tìm ki.m chi0u r4ng
III.3. Tìm ki.m leo ñ9i
III.4. Tìm ki.m ưu tiên t=i ưu (best?first search)
III.5. ThuCt giDi AT
III.6. ThuCt giDi AKT
III.7. ThuCt giDi A*
III.8. Ví dM minh hNa hoOt ñ4ng c$a thuCt giDi A*
III.9. Bàn luCn v0 A*
III.10. Sng dMng A* ñT giDi bài toán Ta?canh
III.11. Các chi.n lưUc tìm ki.m lai
I. T NG QUAN THU T TOÁN – THU T GI I
Trong quá trình nghiên cWu giDi quy.t các v n ñ0 – bài toán, ngưZi ta ñã ñưa ra
nh\ng nhCn xét như sau:
Có nhi0u bài toán cho ñ.n nay van chưa tìm ra m4t cách giDi theo kiTu thuCt
toán và cũng không bi.t là có t9n tOi thuCt toán hay không.
Có nhi0u bài toán ñã có thuCt toán ñT giDi nhưng không ch p nhCn ñưUc vì
thZi gian giDi theo thuCt toán ñó quá len hofc các ñi0u kign cho thuCt toán
khó ñáp Wng.
Có nh\ng bài toán ñưUc giDi theo nh\ng cách giDi vi phOm thuCt toán nhưng
van ch p nhCn ñưUc.
Th nh\ng nhCn ñinh trên, ngưZi ta th y rjng ckn phDi có nh\ng ñli mei cho khái
nigm thuCt toán. NgưZi ta ñã mm r4ng hai tiêu chunn c$a thuCt toán: tính xác ñinh
và tính ñúng ñon. Vigc mm r4ng tính xác ñinh ñ=i vei thuCt toán ñã ñưUc thT hign qua
các giDi thuCt ñg quy và ngau nhiên. Tính ñúng c$a thuCt toán bây giZ không còn bot
bu4c ñ=i vei m4t s= cách giDi bài toán, nh t là các cách giDi gkn ñúng. Trong thqc
tirn có nhi0u trưZng hUp ngưZi ta ch p nhCn các cách giDi thưZng cho k.t quD t=t
(nhưng không phDi lúc nào cũng t=t) nhưng ít phWc tOp và higu quD. Chsng hOn n.u
giDi m4t bài toán bjng thuCt toán t=i ưu ñòi hti máy tính thqc hiên nhi0u năm thì
chúng ta có thT svn lòng ch p nhCn m4t giDi pháp gkn t=i ưu mà chw ckn máy tính
chOy trong vài ngày hofc vài giZ.
Các cách giDi ch p nhCn ñưUc nhưng không hoàn toàn ñáp Wng ñky ñ$ các tiêu chunn
c$a thuCt toán thưZng ñưUc gNi là các thuCt giDi. Khái nigm mm r4ng này c$a thuCt
toán ñã mm cxa cho chúng ta trong vigc tìm ki.m phương pháp ñT giDi quy.t các bài
toán ñưUc ñft ra.
M4t trong nh\ng thuCt giDi thưZng ñưUc ñ0 cCp ñ.n và sx dMng trong khoa hNc trí
tug nhân tOo là các cách giDi theo kiTu Heuristic
II. THU T GI I HEURISTIC
ThuCt giDi Heuristic là m4t sq mm r4ng khái nigm thuCt toán. Nó thT hign cách giDi
bài toán vei các ñfc tính sau:
ThưZng tìm ñưUc lZi giDi t=t (nhưng không choc là lZi giDi t=t nh t)
GiDi bài toán theo thuCt giDi Heuristic thưZng dr dàng và nhanh chóng
ñưa ra k.t quD hơn so vei giDi thuCt t=i ưu, vì vCy chi phí th p hơn.
ThuCt giDi Heuristic thưZng thT hign khá tq nhiên, gkn gũi vei cách
suy nghĩ và hành ñ4ng c$a con ngưZi.
Có nhi0u phương pháp ñT xây dqng m4t thuCt giDi Heuristic, trong ñó ngưZi ta
thưZng dqa vào m4t s= nguyên lý cơ bDn như sau:
Nguyên lý vét c$n thông minh: Trong m4t bài toán tìm ki.m nào ñó, khi
không gian tìm ki.m len, ta thưZng tìm cách giei hOn lOi không gian tìm ki.m
hofc thqc hign m4t kiTu dò tìm ñfc bigt dqa vào ñfc thù c$a bài toán ñT
nhanh chóng tìm ra mMc tiêu.
Nguyên lý tham lam (Greedy): L y tiêu chunn t=i ưu (trên phOm vi toàn
cMc) c$a bài toán ñT làm tiêu chunn chNn lqa hành ñ4ng cho phOm vi cMc b4
c$a thng bưec (hay thng giai ñoOn) trong quá trình tìm ki.m lZi giDi.
Nguyên lý th/ t0: Thqc hign hành ñ4ng dqa trên m4t c u trúc thW tq hUp
lý c$a không gian khDo sát nhjm nhanh chóng ñOt ñưUc m4t lZi giDi t=t.
Hàm Heuristic: Trong vigc xây dqng các thuCt giDi Heuristic, ngưZi ta
thưZng dùng các hàm Heuristic. Đó là các hàm ñánh già thô, giá tri c$a hàm
phM thu4c vào trOng thái hign tOi c$a bài toán tOi m•i bưec giDi. NhZ giá tri
này, ta có thT chNn ñưUc cách hành ñ4ng tương ñ=i hUp lý trong thng bưec
c$a thuCt giDi.
Bài toán hành trình ng7n nh8t – /ng d9ng nguyên lý Greedy
Bài toán: Hãy tìm m4t hành trình cho m4t ngưZi giao hàng ñi qua n ñiTm khác
nhau, m•i ñiTm ñi qua m4t lkn và trm v0 ñiTm xu t phát sao cho tlng chi0u dài ñoOn
ñưZng ckn ñi là ngon nh t. GiD sx rjng có con ñưZng n=i trqc ti.p th gi\a hai ñiTm
b t kỳ.
T t nhiên ta có thT giDi bài toán này bjng cách ligt kê t t cD con ñưZng có thT ñi,
tính chi0u dài c$a m•i con ñưZng ñó r9i tìm con ñưZng có chi0u dài ngon nh t. Tuy
nhiên, cách giDi này lOi có ñ4 phWc tOp 0(n!) (m4t hành trình là m4t hoán v c$a n
ñiTm, do ñó, tlng s= hành trình là s= lưUng hoán vi c$a m4t tCp n phkn tx là n!). Do
ñó, khi s= ñOi lý tăng thì s= con ñưZng phDi xét sƒ tăng lên r t nhanh.
M4t cách giDi ñơn giDn hơn nhi0u và thưZng cho k.t quD tương ñ=i t=t là dùng m4t
thuCt giDi Heuristic Wng dMng nguyên lý Greedy. Tư tưmng c$a thuCt giDi như sau:
Th ñiTm khmi ñku, ta ligt kê t t cD quãng ñưZng th ñiTm xu t phát cho ñ.n n
ñOi lý r9i chNn ñi theo con ñưZng ngon nh t.
Khi ñã ñi ñ.n m4t ñOi lý, chNn ñi ñ.n ñOi lý k. ti.p cũng theo nguyên toc
trên. Nghĩa là ligt kê t t cD con ñưZng th ñOi lý ta ñang ñWng ñ.n nh\ng ñOi lý
chưa ñi ñ.n. ChNn con ñưZng ngon nh t. Lfp lOi quá trình này cho ñ.n lúc
không còn ñOi lý nào ñT ñi.
BOn có thT quan sát hình sau ñT th y ñưUc quá trình chNn lqa. Theo nguyên lý
Greedy, ta l y tiêu chunn hành trình ngon nh t c$a bài toán làm tiêu chunn cho chNn
lqa cMc b4. Ta hy v ng r ng, khi ñi trên n ño n ñư ng ng n nh t thì cu i cùng ta s
có m#t hành trình ng n nh t. Đi0u này không phDi lúc nào cũng ñúng. Vei ñi0u kign
trong hình ti.p theo thì thuCt giDi cho chúng ta m4t hành trình có chi0u dài là 14
trong khi hành trình t=i ưu là 13. K.t quD c$a thuCt giDi Heuristic trong trưZng hUp
này chw lgch 1 ñơn vi so vei k.t quD t=i ưu. Trong khi ñó, ñ4 phWc tOp c$a thuCt giDi
Heuristic này chw là 0(n2).
Hình : GiDi bài toán sx dMng nguyên lý Greedy
T t nhiên, thuCt giDi theo kiTu Heuristic ñôi lúc lOi ñưa ra k.t quD không t=t, thCm chí
r t tg như trưZng hUp m hình sau.
Bài toán phân vi
máy gia công lkn lưUt là P1, P2, … Pn. MNi chi ti.t ñ0u có thT ñưUc gia công trên b t
kỳ máy nào. M4t khi ñã gia công m4t chi ti.t trên m4t máy, công vig sƒ ti.p tMc cho
ñ.n lúc hoàn thành, không thT bi cot ngang. ĐT gia công m4t vigc J1 trên m4t máy
b t kỳ ta ckn dùng m4t thZi gian tương Wng là t1. Nhigm vM c$a công ty là phDi làm
sao gia công xong toàn b4 n chi ti.t trong thZi gian sem nh t.
Chúng ta xét bài toán trong trưZng hUp có 3 máy P1, P2, P3 và 6 công vigc vei thZi
gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. ta có m4t phương án phân công (L) như
hình sau:
Theo hình này, tOi thZi ñiTm t=0, ta ti.n hành gia công chi ti.t J2 trên máy P1, J5 trên
P2 và J1 tOi P3. TOi thZi ñiTm t=2, công vigc J1 ñưUc hoàn thành, trên máy P3 ta gia
công ti.p chi ti.t J4. Trong lúc ñó, hai máy P1 và P2 van ñang thqc hign công vigc ñku
tiên mình … Sơ ñ9 phân vigc theo hình m trên ñưUc gNi là lưUc ñ9 GANTT. Theo lưUc
ñ9 này, ta th y thZi gian ñT hoàn thành toàn b4 6 công vigc là 12. NhCn xét m4t
cách cDm tính ta th y rjng phương án (L) vha thqc hign là m4t phương án không t=t.
Các máy P1 và P2 có quá nhi0u thZi gian rãnh.
ThuCt toán tìm phương án t=i ưu L0 cho bài toán này theo kiTu vét cOn có ñ4 phWc
tOp c‡ O(mn) (vei m là s= máy và n là s= công vigc). Bây giZ ta xét ñ.n m4t thuCt
giDi Heuristic r t ñơn giDn (ñ4 phWc tOp O(n)) ñT giDi bài toán này.
Sop x.p các công vigc theo thW tq giDm dkn v0 thZi gian gia công.
Lkn lưUt sop x.p các vigc theo thW tq ñó vào máy còn dư nhi0u thZi
gian nh t.
Vei tư tưmng như vCy, ta sƒ có m4t phương án L* như sau:
Rõ ràng phương án L* vha thqc hign cũng chính là phương án t=i ưu c$a trưZng hUp
này vì thZi gian hoàn thành là 8, ñúng bjng thZi gian c$a công vigc J3. Ta hy vNng
rjng m4t giDi Heuristic ñơn giDn như vCy sƒ là m4t thuCt giDi t=i ưu. Nhưng ti.c thay,
ta dr dàng ñưa ra ñưUc m4t trưZng hUp mà thuCt giDi Heuristic không ñưa ra ñưUc
k.t quD t=i ưu.
N.u gNi T* là thZi gian ñT gia công xong n chi ti.t máy do thuCt giDi Heuristic ñưa ra
và T0 là thZi gian t=i ưu thì ngưZi ta ñã chWng minh ñưUc rjng
, M là s= máy
Vei k.t quD này, ta có thT xác lCp ñưUc sai s= mà chúng ta phDi gánh chiu n.u dùng
Heuristic thay vì tìm m4t lZi giDi t=i ưu. Chsng hOn vei s= máy là 2 (M=2) ta có
, và ñó chính là sai s= cqc ñOi mà trưZng hUp m trên ñã gánh chiu. Theo công
thWc này, s= máy càng len thì sai s= càng len.
Trong trưZng hUp M len thì t‰ s= 1/M xem như bjng 0 . Như vCy, sai s= t=i ña mà ta
phDi chiu là T* 4/3 T0, nghĩa là sai s= t=i ña là 33%. Tuy nhiên, khó tìm ra ñưUc
nh\ng trưZng hUp mà sai s= ñúng bjng giá tri cqc ñOi, dù trong trưZng hUp x u
nh t. ThuCt giDi Heuristic trong trưZng hUp này rõ ràng ñã cho chúng ta nh\ng lZi
giDi tương ñ=i t=t.
III. CÁC PHƯƠNG PHÁP TÌM KIBM HEURISTIC
Qua các phkn trưec chúng ta tìm hiTu tlng quan v0 ý tưmng c$a thuCt giDi Heuristic
(nguyên lý Greedy và sop thW tq). Trong mMc này, chúng ta sƒ ñi sâu vào tìm hiTu
m4t s= kŽ thuCt tìm ki.m Heuristic – m4t lep bài toán r t quan trNng và có nhi0u Wng
dMng trong thqc t..
III.1. C8u trúc chung c=a bài toán tìm kiFm
ĐT tign lUi cho vigc trình bày, ta hãy dành chút thZi gian ñT làm rõ hơn "ñ=i tưUng"
quan tâm c$a chúng ta trong mMc này. M4t cách chung nh t, nhi0u v n ñ0?bài toán
phWc tOp ñ0u có dOng "tìm ñưZng ñi trong ñ9 thi" hay nói m4t cách hình thWc hơn là
"xu t phát t) m#t ñ*nh c+a m#t ñ, th , tìm ñư ng ñi hi-u qu/ nh t ñ0n m#t ñ*nh nào
ñó". M4t phát biTu khác thưZng gfp c$a dOng bài toán này là :
Cho trưec hai trOng thái T0 và TG hãy xây dqng chu•i trOng thái T0, T1, T2, ..., TnI1,
Tn = TG sao cho :
thta mãn m4t ñi0u kign cho trưec (thưZng là nht nh t).
Trong ñó, Ti thu4c tCp hUp S (gNi là không gian trOng thái – state space) bao g9m t t
cD các trOng thái có thT có c$a bài toán và cost(TiI1, Ti) là chi phí ñT bi0n ñ3i th
trOng thái Ti?1 sang trOng thái Ti. Dĩ nhiên, th m4t trOng thái Ti ta có nhi0u cách ñT
bi.n ñli sang trOng thái Ti+1. Khi nói ñ.n m4t bi.n ñli cM thT th Ti?1 sang Ti ta sƒ
dùng thuCt ng\ hư4ng ñi (vei ngM ý nói v0 sq lqa chNn).
Hình : Mô hình chung c$a các v n ñ0?bài toán phDi giDi quy.t bjng phương pháp tìm
ki.m lZi giDi. Không gian tìm ki.m là m4t tCp hUp trOng thái ? tCp các nút c$a ñ9 thi.
Chi phí ckn thi.t ñT chuyTn th trOng thái T này sang trOng thái Tk ñưUc biTu dirn
dưei dOng các con s= njm trên cung n=i gi\a hai nút tưUng trưng cho hai trOng thái.
Đa s= các bài toán thu4c dOng mà chúng ta ñang mô tD ñ0u có thT ñưUc biTu dirn
dưei dOng ñ9 thi. Trong ñó, m4t trOng thái là m4t ñwnh c$a ñ9 thi. TCp hUp S bao
g9m t t cD các trOng thái chính là tCp hUp bao g9m t t cD ñwnh c$a ñ9 thi. Vigc bi.n
ñli th trOng thái Ti?1 sang trOng thái Ti là vigc ñi th ñwnh ñOi dign cho Ti?1 sang ñwnh
ñOi dign cho Ti theo cung n=i gi\a hai ñwnh này.
III.2. Tìm kiFm chiJu sâu và tìm kiFm chiJu rKng
ĐT bOn ñNc có thT hình dung m4t cách cM thT bDn ch t c$a thuCt giDi Heuristic,
chúng ta nh t thi.t phDi nom v\ng hai chi0n lư7c tìm ki.m cơ bDn là tìm ki.m theo
chi0u sâu (Depth First Search) và tìm ki.m theo chi0u r4ng (Breath First Search). Sm
dĩ chúng ta dùng th chi0n lư7c mà không phDi là phương pháp là bmi vì trong thqc t.,
ngưZi ta hku như chsng bao giZ vCn dMng m4t trong hai kiTm tìm ki.m này m4t cách
trqc ti.p mà không phDi sxa ñli gì.
III.2.1. Tìm kiFm chiJu sâu (DepthIFirst Search)
Trong tìm ki.m theo chi0u sâu, tOi trOng thái (ñwnh) hign hành, ta chNn m4t trOng
thái k. ti.p (trong tCp các trOng thái có thT bi.n ñli thành th trOng thái hign tOi) làm
trOng thái hign hành cho ñ.n lúc trOng thái hign hành là trOng thái ñích. Trong
trưZng hUp tOi trOng thái hign hành, ta không thT bi.n ñli thành trOng thái k. ti.p
thì ta sƒ quay lui (back?tracking) lOi trOng thái trưec trOng thái hign hành (trOng thái
bi.n ñli thành trOng thái hign hành) ñT chNn ñưZng khác. N.u m trOng thái trưec này
mà cũng không thT bi.n ñli ñưUc n\a thì ta quay lui lOi trOng thái trưec n\a và cW
th.. N.u ñã quay lui ñ.n trOng thái khmi ñku mà van th t bOi thì k.t luCn là không có
lZi giDi. Hình Dnh sau minh hNa hoOt ñ4ng c$a tìm ki.m theo chi0u sâu.
Hình : Hình Dnh c$a tìm ki.m chi0u sâu. Nó chw lưu ý "mm r4ng" trOng thái ñưUc chNn
mà không "mm r4ng" các trOng thái khác (nút màu trong trong hình vƒ).
III.2.2. Tìm kiFm chiJu rKng (BreathIFirst Search)
NgưUc lOi vei tìm ki.m theo kiTu chi0u sâu, tìm ki.m chi0u r4ng mang hình Dnh c$a
v.t dku loang. Th trOng thái ban ñku, ta xây dqng tCp hUp S bao g9m các trOng thái
k. ti.p (mà th trOng thái ban ñku có thT bi.n ñli thành). Sau ñó, 9ng v4i m:i trOng
thái Tk trong tCp S, ta xây dqng tCp Sk bao g9m các trOng thái k. ti.p c$a Tk r9i lkn
lưUt bl sung các Sk vào S. Quá trình này cW lfp lOi cho ñ.n lúc S có chWa trOng thái
k.t thúc hofc S không thay ñli sau khi ñã bl sung t t cD Sk.
Hình : Hình Dnh c$a tìm ki.m chi0u r4ng. TOi m4t bưec, mNi trOng thái ñ0u ñưUc mm
r4ng, không bt sót trOng thái nào.
Chi0u sâu
Chi0u r4ng
Tính higu quD
Higu quD khi lZi giDi njm
sâu trong cây tìm ki.m và
có m4t phương án chNn
hưeng ñi chính xác. Higu
quD c$a chi.n lưUc phM
thu4c vào phương án chNn
hưeng ñi. Phương án càng
kém higu quD thì higu quD
c$a chi.n lưUc càng giDm.
ThuCn lUi khi mu=n tìm chw
m4t lZi giDi.
Higu quD khi lZi giDi
njm gkn g=c c$a cây
tìm ki.m. Higu quD
c$a chi.n lưUc phM
thu4c vào ñ4 sâu c$a
lZi giDi. LZi giDi càng
xa g=c thì higu quD
c$a chi.n lưUc càng
giDm. ThuCn lUi khi
mu=n tìm nhi0u lZi
giDi.
LưUng b4 nhe sx
dMng ñT lưu tr\ các
trOng thái
Chw lưu lOi các trOng thái
chưa xét ñ.n.
PhDi lưu toàn b4 các
trOng thái.
TrưZng hUp x u
nh t
Vét cOn toàn b4
Vét cOn toàn b4.
TrưZng hUp t=t nh t
Phương án chNn hưeng ñi
tuy-t ñ i chính xác. LZi giDi
ñưUc xác ñinh m4t cách
trqc ti.p.
Vét cOn toàn b4.
Tìm ki.m chi0u sâu và tìm ki.m chi0u r4ng ñ0u là các phương pháp tìm ki.m có hg
th=ng và choc chon tìm ra lZi giDi. Tuy nhiên, do bDn ch t là vét cOn nên vei nh\ng
bài toán có không gian len thì ta không thT dùng hai chi.n lưUc này ñưUc. Hơn n\a,
hai chi.n lưUc này ñ0u có tính ch t "mù quáng" vì chúng không chú ý ñ.n nh\ng
thông tin (tri thWc) m trOng thái hign thZi và thông tin v0 ñích ckn ñOt tei cùng m=i
quan hg gi\a chúng. Các tri thWc này vô cùng quan trNng và r t có ý nghĩa ñT thi.t
k. các thuCt giDi higu quD hơn mà ta sop sxa bàn ñ.n.
III.3. Tìm kiFm leo ñPi
III.3.1. Leo ñPi ñơn giSn
Tìm ki.m leo ñ9i theo ñúng nghĩa, nói chung, thqc ch t chw là m4t trưZng hUp ñfc
bigt c$a tìm ki.m theo chi0u sâu nhưng không thT quay lui. Trong tìm ki.m leo ñ9i,
vigc lqa chNn trOng thái ti.p theo ñưUc quy.t ñinh dqa trên m4t hàm Heuristic.
Hàm Heuristic là gì ?
ThuCt ng\ "hàm Heuristic" mu=n nói lên ñi0u gì? Chsng có gì ghê gem. BOn ñã quen
vei nó r9i! Đó ñơn giDn chw là m4t ư c lư ng v kh năng d n ñ n l i gi i tính th
trOng thái ñó (kho/ng cách gi\a trOng thái hign tOi và trOng thái ñích). Ta sƒ quy ưec
gNi hàm này là h trong su=t giáo trình này. Đôi lúc ta cũng ñ0 cCp ñ.n chi phí t i
ưu th c s th m4t trOng thái dan ñ.n lZi giDi. Thông thưZng, giá tri này là không
thT tính toán ñưUc (vì tính ñưUc ñ9ng nghĩa là ñã bi.t con ñưZng ñ.n lZi giDi !) mà ta
chw dùng nó như m4t cơ sm ñT suy luCn v0 mft lý thuy.t mà thôi ! Hàm h, ta quy ưec
rjng, luôn trD ra k.t quD là m4t s= không âm. ĐT bOn ñNc thqc sq nom ñưUc ý nghĩa
c$a hai hàm này, hãy quan sát hình sau trong ñó minh hNa chi phí t=i ưu thqc sq và
chi phí ưec lưUng.
Hình Chi phí ưec lưUng h’ = 6 và chi phí t=i ưu thqc sq h = 4+5 = 9 (ñi theo ñưZng
1?3?7)
BOn ñang m trong m4t thành ph= xa lO mà không có bDn ñ9 trong tay và ta
mu=n ñi vào khu trung tâm? M4t cách suy nghĩ ñơn giDn, chúng ta sƒ nhom
vào hư4ng nh\ng tòa cao =c c$a khu trung tâm!
Tư tưVng
1) N.u trOng thái bot ñku cũng là trOng thái ñích thì thoát và báo là ñã tìm ñưUc lZi
giDi. NgưUc lOi, ñft trOng thái hign hành (Ti) là trOng thái khmi ñku (T0)
2) Lfp lOi cho ñ.n khi ñOt ñ.n trOng thái k.t thúc hofc cho ñ.n khi không t9n tOi
m4t trOng thái ti.p theo hUp lg (Tk) c$a trOng thái hign hành :
a. Đft Tk là m4t trOng thái ti.p theo hUp lg c$a trOng thái hign hành Ti.
b. Đánh giá trOng thái Tk mei :
b.1. N.u là trOng thái k.t thúc thì trD v0 tri này và thoát.
b.2. N.u không phDi là trOng thái k.t thúc nhưng tWt hơn trOng
thái hign hành thì cCp nhCt nó thành trOng thái hign hành.
b.3. N.u nó không t=t hơn trOng thái hign hành thì ti.p tMc
vòng lfp.
Mã giS
Ti := T0; Stop :=FALSE;
WHILE Stop=FALSE DO BEGIN
IF Ti TG THEN BEGIN
<tìm ñưUc k.t quD >; Stop:=TRUE;
END;
ELSE BEGIN
Better:=FALSE;
WHILE (Better=FALSE) AND (STOP=FALSE) DO BEGIN
IF <không t9n tOi trOng thái k. ti.p h7p l- c$a Ti>
THEN BEGIN
<không tìm ñưUc k.t quD >; Stop:=TRUE; END;
ELSE BEGIN
Tk := <m4t trOng thái k. ti.p h7p l- c$a Ti>;
IF <h(Tk) t=t hơn h(Ti)> THEN BEGIN
Ti :=Tk; Better:=TRUE;
END;
END;
END; {WHILE}
END; {ELSE}
END;{WHILE}
Mgnh ñ0 "h’(Tk) t=t hơn h’(Ti)" nghĩa là gì? Đây là m4t khái nigm chung chung. Khi
cài ñft thuCt giDi, ta phDi cung c p m4t ñinh nghĩa tưZng minh v0 t t hơn. Trong m4t
s= trưZng hUp, t=t hơn là nht hơn : h’(Tk) < h’(Ti); m4t s= trưZng hUp khác t=t hơn
là len hơn h’(Tk) > h’(Ti)...Chsng hOn, ñ=i vei bài toán tìm ñưZng ñi ngon nh t gi\a
hai ñiTm. N.u dùng hàm h’ là hàm cho ra kho/ng cách theo ñư ng chim bay gi\a vi
trí hign tOi (trOng thái hign tOi) và ñích ñ.n (trOng thái ñích) thì t=t hơn nghĩa là nht
hơn.
V n ñ0 ckn làm rõ k. ti.p là th. nào là <m4t trOng thái k. ti.p hUp lg c$a Ti>? M4t
trOng thái k. ti.p hUp lg là trOng thái chưa ñưUc xét ñ.n. GiD sx h c$a trOng thái hign
tOi Ti có giá tri là h(Ti) = 1.23 và th Ti ta có thT bi.n ñli sang m4t trong 3 trOng thái
k. ti.p lkn lưUt là Tk1, Tk2, Tk3 vei giá tri các hàm h tương Wng là h(Tk1) = 1.67,
h(Tk2) = 2.52, h’(Tk3) = 1.04. Đku tiên, Tk sƒ ñưUc gán bjng Tk1, nhưng vì h’(Tk) =
h’(Tk1) > h’(Ti) nên Tk không ñưUc chNn. K. ti.p là Tk sƒ ñưUc gán bjng Tk2 và cũng
không ñưUc chNn. Cu=i cùng thì Tk3 ñưUc chNn. Nhưng giD sx h’(Tk3) = 1.3 thì cD Tk3
cũng không ñưUc chNn và mgnh ñ0 <không th> sinh ra tr ng thái k0 ti0p c+a Ti> sƒ
có giá tri TRUE. GiDi thích này có v— hiTn nhiên nhưng có lƒ ckn thi.t ñT tránh nhkm
lan cho bOn ñNc.
ĐT th y rõ hoOt ñ4ng c$a thuCt giDi leo ñ9i. Ta hãy xét m4t bài toán minh hNa sau.
Cho 4 kh=i lCp phương gi ng nhau A, B, C, D. Trong ñó các mft (M1), (M2), (M3),
(M4), (M5), (M6) có thT ñưUc tô bjng 1 trong 6 màu (1), (2), (3), (4), (5), (6). Ban
ñku các kh=i lCp phương ñưUc x.p vào m4t hàng. M•i m4t bưec, ta chw ñưUc xoay
m4t kh=i lCp phương quanh m4t trMc (X,Y,Z) 900 theo chi0u b t kỳ (nghĩa là ngưUc
chi0u hay thuCn chi0u kim ñ9ng h9 cũng ñưUc). Hãy xác ñinh s= bưec quay ít nh t
sao cho t t cD các mft c$a kh=i lCp phương trên 4 mft c$a hàng là có cùng màu như
hình vƒ.
Hình : Bài toán 4 kh=i lCp phương
ĐT giDi quy.t v n ñ0, trưec h.t ta ckn ñinh nghĩa m4t hàm G dùng ñT ñánh giá m4t
tình trOng cM thT có phDi là lZi giDi hay không? BOn ñNc có thT dr dàng ñưa ra m4t
cài ñft c$a hàm G như sau :
IF (Gtrái + GphDi + Gtrên + Gdưei + Gtrưec + Gsau) = 16 THEN
G:=TRUE
ELSE
G:=FALSE;
Trong ñó, GphDi là s lư7ng các m@t có cùng màu c$a mft bên phDi c$a hàng. Tương
tq cho Gtrái, Gtrên, Ggi\a, Gtrưec, Gsau. Tuy nhiên, do các kh=i lCp phương A,B,C,D
là hoàn toàn tương tq nhau nên tương quan gi\a các mft c$a m•i kh=i là gi=ng
nhau. Do ñó, n.u có 2 mft không ñ=i nhau trên hàng ñ9ng màu thì 4 mft còn lOi c$a
hàng cũng ñ9ng màu. Th ñó ta chw ckn hàm G ñưUc ñinh nghĩa như sau là ñ$ :
IF GphDi + Gdưei = 8 THEN
G:=TRUE
ELSE
G:=FALSE;
Hàm h (ưec lưUng khD năng dan ñ.n lZi giDi c$a m4t trOng thái) sƒ ñưUc ñinh nghĩa
như sau :
h = Gtrái + GphDi + Gtrên + Gdưei
Bài toán này ñ$ ñơn giDn ñT thuCt giDi leo ñ9i có thT hoOt ñ4ng t=t. Tuy nhiên, không
phDi lúc nào ta cũng may mon như th.!
Đ.n ñây, có thT chúng ta sƒ nDy sinh m4t ý tưmng. N.u ñã chNn trOng thái t t hơn
làm trOng thái hign tOi thì tOi sao không chNn trOng thái t t nh t ? Như vCy, có l ta
sƒ nhanh chóng dan ñ.n lZi giDi hơn! Ta sƒ bàn luCn v0 v n ñ0: "ligu cDi ti.n này có
thqc sq giúp chúng ta dan ñ.n lZi giDi nhanh hơn hay không?" ngay sau khi trình bày
xong thuCt giDi leo ñ9i d=c ñWng.
III.3.2. Leo ñPi dWc ñ/ng
V0 cơ bDn, leo ñ9i d=c ñWng cũng gi=ng như leo ñ9i, chw khác m ñiTm là leo ñ9i d=c
ñWng sƒ duygt t t cD các hưeng ñi có thT và chNn ñi theo trOng thái t t nh t trong s=
các trOng thái k. ti.p có thT có (trong khi ñó leo ñ9i chw chNn ñi theo trOng thái k.
ti.p ñku tiên t t hơn trOng thái hign hành mà nó tìm th y).
Tư tưVng
1) N.u trOng thái bot ñku cũng là trOng thái ñích thì thoát và báo là ñã tìm ñưUc lZi
giDi. NgưUc lOi, ñft trOng thái hign hành (Ti) là trOng thái khmi ñku (T0)
2) Lfp lOi cho ñ.n khi ñOt ñ.n trOng thái k.t thúc hofc cho ñ.n khi (Ti) không t9n tOi
m4t trOng thái k. ti.p (Tk) nào t=t hơn trOng thái hign tOi (Ti)
a) Đft S bjng tCp t t cD trOng thái k. ti.p có thT có c$a Ti và t=t hơn
Ti.
b) Xác ñinh Tkmax là trOng thái t=t nh t trong tCp S
Đft Ti = Tkmax
Mã giS
Ti := T0;
Stop :=FALSE;
WHILE Stop=FALSE DO BEGIN
IF Ti TG THEN BEGIN
<tìm ñưUc k.t quD >;
STOP :=TRUE;
END;
ELSE BEGIN
Best:=h’(Ti);
Tmax := Ti;
WHILE <t9n tOi trOng thái k. ti.p h7p l- c$a Ti> DO BEGIN
Tk := <m4t trOng thái k. ti.p h7p l- c$a Ti>;
IF <h’(Tk) t=t hơn Best> THEN BEGIN
Best :=h’(Tk);
Tmax := Tk;
END;
END;
IF (Best>Ti) THEN
Ti := Tmax;
ELSE BEGIN
<không tìm ñưUc k.t quD >;
STOP:=TRUE;
END;
END; {ELSE IF}
END;{WHILE STOP}
III.3.3. Đánh giá
So vei leo ñ9i ñơn giDn, leo ñ9i d=c ñWng có ưu ñiTm là luôn luôn chNn hưeng có triTn
vNng nh t ñT ñi. Ligu ñi0u này có ñDm bDo leo ñ9i d=c ñWng luôn t=t hơn leo ñ9i ñơn
giDn không? Câu trD lZi là không. Leo ñ9i d=c ñWng chw t=t hơn leo ñ9i ñơn giDn trong
m4t s= trưZng hUp mà thôi. ĐT chNn ra ñưUc hưeng ñi t=t nh t, leo ñ9i d=c ñWng phDi
duygt qua t t c/ các hưeng ñi có thT có tOi trOng thái hign hành. Trong khi ñó, leo
ñ9i ñơn giDn chw chNn ñi theo trOng thái ñAu tiên t=t hơn (so vei trOng thái hign hành)
mà nó tìm ra ñưUc. Do ñó, thZi gian ckn thi.t ñT leo ñ9i d=c ñWng chNn ñưUc m4t
hưeng ñi sƒ len hơn so vei leo ñ9i ñơn giDn. Tuy vCy, do lúc nào cũng chNn hưeng ñi
t=t nh t nên leo ñ9i d=c ñWng thưZng sƒ tìm ñ.n lZi giDi sau m4t s= bưec ít hơn so
vei leo ñ9i ñơn giDn. Nói m4t cách ngon gNn, leo ñ9i d=c ñWng sƒ t=n nhi0u thZi gian
hơn cho m4t bưec nhưng lOi ñi ít bưec hơn; còn leo ñ9i ñơn giDn t=n ít thZi gian hơn
cho m4t bưec ñi nhưng lOi phDi ñi nhi0u bưec hơn. Đây chính là y.u t= ñưUc và m t
gi\a hai thuCt giDi nên ta phDi cân nhoc kŽ lư‡ng khi lqa chNn thuCt giDi.
CD hai phương pháp leo núi ñơn giDn và leo núi d=c ñWng ñ0u có khD năng th t bOi
trong vigc tìm lZi giDi c$a bài toán mfc dù lZi giDi ñó thqc sq hign h\u. CD hai giDi
thuCt ñ0u có thT k.t thúc khi ñOt ñưUc m4t trOng thái mà không còn trOng thái nào
t=t hơn n\a có thT phát sinh nhưng trOng thái này không phDi là trOng thái ñích. Đi0u
này sƒ xDy ra n.u chương trình ñOt ñ.n m4t ñiTm cqc ñOi ñia phương, m4t ñoOn ñơn
ñigu ngang.
Đi>m cCc ñ i ñ a phương (a local maximum) : là m4t trOng thái t=t hơn t t cD lân cCn
c$a nó nhưng không t=t hơn m4t s= trOng thái khác m xa hơn. Nghĩa là tOi m4t ñiTm
cqc ñOi ñia phương, mNi trOng thái trong m#t lân cEn c$a trOng thái hign tOi ñ0u x u
hơn trOng thái hign tOi. Tuy có dáng v— c$a lZi giDi nhưng các cqc ñOi ñia phương
không phDi là lZi giDi thqc sq. Trong trưZng hUp này, chúng ñưUc gNi là nh\ng ngNn
ñ9i th p.
Đo n ñơn ñi-u ngang (a plateau) : là m4t vùng bjng phsng c$a không gian tìm
ki.m, trong ñó, toàn b4 các trOng thái lân cCn ñ0u có cùng giá tri.
Hình : Các tình hu=ng khó khăn cho tìm ki.m leo ñèo.
ĐT ñ=i phó vei các các ñiTm này, ngưZi ta ñã ñưa ra m4t s= giDi pháp. Ta sƒ tìm hiTu
2 trong s= các giDi pháp này. Nh\ng giDi này, không thqc sq giDi quy.t trNn vœn v n
ñ0 mà chw là m4t phương án cWu nguy tOm thZi mà thôi.
Phương án ñku tiên là k.t hUp leo ñ9i và quay lui. Ta sƒ quay lui lOi các trOng thái
trưec ñó và thx ñi theo hưeng khác. Thao tác này hUp lý n.u tOi các trOng thái trưec
ñó có m4t hưeng ñi t=t mà ta ñã bt qua trưec ñó. Đây là m4t cách khá hay ñT ñ=i
phó vei các ñiTm cqc ñOi ñia phương. Tuy nhiên, do ñfc ñiTm c$a leo ñ9i là "bưec
sau cao hơn bưec trưec" nên phương án này sƒ th t bOi khi ta xu t phát th m4t ñiTm
quá cao hofc xu t phát th m4t ñwnh ñ9i mà ñT ñ.n ñưUc lZi giDi ckn phDi ñi qua m4t
"thung lũng" thCt sâu như trong hình sau.
Hình : M4t trưZng hUp th t bOi c$a leo ñèo k.t hUp quay lui.
Cách thW hai là thqc hign m4t bưec nh/y v t theo hưeng nào ñó ñT thx ñ.n m4t
vùng mei c$a không gian tìm ki.m. Nôm na là "bưec" liên tMc nhi0u "bưec" (chsng
hOn 5,7,10, …) mà tOm thZi "quên" ñi vigc kiTm tra "bưec sau cao hơn bưec trưec".
Ti.p cCn có v— higu quD khi ta gfp phDi m4t ñoOn ñơn ñigu ngang. Tuy nhiên, nhDy
vNt cũng có nghĩa là ta ñã bt qua cơ h4i ñT ti.n ñ.n lZi giDi thqc sq. Trong trưZng
hUp chúng ta ñang ñWng khá gkn lZi giDi, vigc nhDy vNt sƒ ñưa chúng ta sang m4t vi
trí hoàn toàn xa lO, mà th ñó, có thT sƒ dan chúng ta ñ.n m4t roc r=i kiTu khác. Hơn
n\a, s= bưec nhDy là bao nhiêu và nhDy theo hưeng nào là m4t v n ñ0 phM thu4c r t
nhi0u vào ñfc ñiTm không gian tìm ki.m c$a bài toán.
Hình M4t trưZng hUp khó khăn cho phương án "nhDy vNt".
Leo núi là m4t phương pháp cMc b4 bmi vì nó quy.t ñinh sƒ làm gì ti.p theo dqa vào
m4t ñánh giá v0 trOng thái hign tOi và các trOng thái k. ti.p có thT có (t t hơn trOng
thái hign tOi, trOng thái t t nh t t=t hơn trOng thái hign tOi) thay vì phDi xem xét m4t
cách toàn dign trên t t cD các trOng thái ñã ñi qua. ThuCn lUi c$a leo núi là ít gfp sq
bùng nl tl hUp hơn so vei các phương pháp toàn cMc. Nhưng nó cũng gi=ng như các
phương pháp cMc b4 khác m ch• là không choc chon tìm ra lZi giDi trong trưZng hUp
x u nh t.
M4t lkn n\a, ta khsng ñinh lOi vai trò quy.t ñinh c$a hàm Heuristic trong quá trình
tìm ki.m lZi giDi. Vei cùng m4t thuCt giDi (như leo ñ9i chsng hOn), n.u ta có m4t
hàm Heuristic t=t hơn thì k.t quD sƒ ñưUc tìm th y nhanh hơn. Ta hãy xét bài toán
v0 các kh=i ñưUc trình bày m hình sau. Ta có hai thao tác bi.n ñli là:
+ L y m4t kh=i m ñwnh m4t c4t b t kỳ và ñft nó lên m4t ch• tr=ng tOo thành
m4t c4t mei. Lưu ý là chw có thT tOo ra t=i ña 2 c4t mei.
+ L y m4t kh=i m ñwnh m4t c4t và ñft nó lên ñwnh m4t c4t khác
Hãy xác ñinh s= thao tác ít nh t ñT bi.n ñli c4t ñã cho thành c4t k.t quD.
Hình : TrOng thái khmi ñku và trOng thái k.t thúc
GiD sx ban ñku ta dùng m4t hàm Heuristic ñơn giDn như sau :
H1 : C4ng 1 ñiTm cho m•i kh=i m vi trí ñúng so vei trOng thái ñích. Trh 1 ñiTm
cho m•i kh=i ñft m vi trí sai so vei trOng thái ñích.
Dùng hàm này, trOng thái k.t thúc sƒ có giá tri là 8 vì cD 8 kh=i ñ0u ñưUc ñft m vi trí
ñúng. TrOng thái khmi ñku có giá tri là 4 (vì nó có 1 ñiTm c4ng cho các kh=i C, D, E,
F, G, H và 1 ñiTm trh cho các kh=i A và B). Chw có thT có m4t di chuyTn th trOng thái
khmi ñku, ñó là dich chuyTn kh=i A xu=ng tOo thành m4t c4t mei (T1).
Đi0u ñó sinh ra m4t trOng thái vei s= ñiTm là 6 (vì vi trí c$a kh=i A bây giZ sinh ra 1
ñiTm c4ng hơn là m4t ñiTm trh). Th$ tMc leo núi sƒ ch p nhCn sq dich chuyTn ñó. Th
trOng thái mei T1, có ba di chuyTn có thT thqc hign dan ñ.n ba trOng thái Ta, Tb, Tc
ñưUc minh hNa trong hình dưei. Nh\ng trOng thái này có s= ñiTm là : h’(Ta)= 4;
h’(Tb) = 4 và h’(Tc) = 4
T1
TA
TB
TC
Hình Các trOng thái có thT ñOt ñưUc th T1
Th$ tMc leo núi sƒ tOm dhng bmi vì t t cD các trOng thái này có s= ñiTm th p hơn
trOng thái hign hành. Quá trình tìm ki.m chw dhng lOi m m4t trOng thái cqc ñOi ñia
phương mà không phDi là cqc ñOi toàn cMc.
Chúng ta có thT ñl l•i cho chính giDi thuCt leo ñ9i vì ñã th t bOi do không ñ$ tkm
nhìn tlng quát ñT tìm ra lZi giDi. Nhưng chúng ta cũng có thT ñl l•i cho hàm
Heuristic và c= gong sxa ñli nó. GiD sx ta thay hàm ban ñku bjng hàm Heuristic sau
ñây :
H2 : Đ=i vei m•i kh=i phM trU ñúng (kh=i phM trU là kh=i njm bên dưei kh=i
hign tOi), c4ng 1 ñiTm, ngưUc lOi trh 1 ñiTm.
Dùng hàm này, trOng thái k.t thúc có s= ñiTm là 28 vì B njm ñúng vi trí và không có
kh=i phM trU nào, C ñúng vi trí ñưUc 1 ñiTm c4ng vei 1 ñiTm do kh=i phM trU B njm
ñúng vi trí nên C ñưUc 2 ñiTm, D ñưUc 3 ñiTm, ....TrOng thái khmi ñku có s= ñiTm là –
28. Vigc di chuyTn A xu=ng tOo thành m4t c4t mei làm sinh ra m4t trOng thái vei s=
ñiTm là h’(T1) = –21 vì A không còn 7 kh=i sai phía dưei nó n\a. Ba trOng thái có thT
phát sinh ti.p theo bây giZ có các ñiTm s= là : h’(Ta)=–28; h’(Tb)=–16 và h’(Tc) = –
15. Lúc này th$ tMc leo núi d=c ñWng sƒ chNn di chuy.n ñ.n trOng thái Tc, m ñó có
m4t kh=i ñúng. Qua hàm H2 này ta rút ra m4t nguyên toc : t t hơn không chw có
nghĩa là có nhiGu ưu ñi>m hơn mà còn phDi ít khuy0t ñi>m hơn. Hơn n\a, khuy.t
ñiTm không có nghĩa chw là sq sai bigt ngay tOi m4t vi trí mà còn là sq khác bigt
trong tương quan gi\a các vi trí. Rõ ràng là ñWng v0 mft k.t quD, cùng m4t th$ tMc
leo ñ9i nhưng hàm H1 bi th t bOi (do chw bi.t ñánh giá ưu ñiTm) còn hàm H2 mei này
lOi hoOt ñ4ng m4t cách hoàn hDo (do bi.t ñánh giá cD ưu ñiTm và khuy.t ñiTm).
Đáng ti.c, không phDi lúc nào chúng ta cũng thi.t k. ñưUc m4t hàm Heuristic hoàn
hDo như th.. Vì vigc ñánh giá ưu ñiTm ñã khó, vigc ñánh giá khuy.t ñiTm càng khó
và tinh t. hơn. Chsng hOn, xét lOi v n ñ0 mu=n ñi vào khu trung tâm c$a m4t thành
ph= xa l . ĐT hàm Heuristic higu quD, ta ckn phDi ñưa các thông tin v0 các ñưZng
m4t chi0u và các ngõ cMt, mà trong trưZng hUp m4t thành ph= hoàn toàn xa lO thì ta
khó hofc không thT bi.t ñưUc nh\ng thông tin này.
Đ.n ñây, chúng ta hiTu rõ bDn ch t c$a hai thuCt giDi ti.p cCn theo chi.n lưUc tìm
ki.m chi0u sâu. Higu quD c$a cD hai thuCt giDi leo ñ9i ñơn giDn và leo ñ9i d=c ñWng
phM thu4c vào :
+ Ch t lưUng c$a hàm Heuristic.
+ Đfc ñiTm c$a không gian trOng thái.
+ TrOng thái khmi ñku.
Sau ñây, chúng ta sƒ tìm hiTu m4t ti.p cCn theo mei, k.t hUp ñưUc sWc mOnh c$a cD
tìm ki.m chi0u sâu và tìm ki.m chi0u r4ng. M4t thuCt giDi r t linh ñ4ng và có thT nói
là m4t thuCt giDi kinh ñiTn c$a Heuristic.
III.4. Tìm kiFm ưu tiên tWi ưu (bestIfirst search)
Ưu ñiTm c$a tìm ki.m theo chi0u sâu là không phDi quan tâm ñ.n sq mm r4ng c$a
t t cD các nhánh. Ưu ñiTm c$a tìm ki.m chi0u r4ng là không bi sa vào các ñưZng dan
b. toc (các nhánh cMt). Tìm ki.m ưu tiên t=i ưu sƒ k.t hUp 2 phương pháp trên cho
phép ta ñi theo m4t con ñưZng duy nh t tOi m4t thZi ñiTm, nhưng ñ9ng thZi van
"quan sát" ñưUc nh\ng hưeng khác. N.u con ñưZng ñang ñi "có v—" không triTn vNng
bjng nh\ng con ñưZng ta ñang "quan sát" ta sƒ chuyTn sang ñi theo m4t trong s=
các con ñưZng này. ĐT tign lUi ta sƒ dùng ch\ vi.t tot BFS thay cho tên gNi tìm ki.m
ưu tiên t=i ưu.
M4t cách cM thT, tOi m•i bưec c$a tìm ki.m BFS, ta chNn ñi theo trOng thái có khD
năng cao nh t trong s= các trOng thái ñã ñưUc xét cho ñ0n th i ñi>m ñó. (khác vei
leo ñ9i d=c ñWng là chw chNn trOng thái có khD năng cao nh t trong s= các trOng thái
k. ti.p có thT ñ.n ñưUc th trOng thái hign tOi). Như vCy, vei ti.p cCn này, ta sƒ ưu
tiên ñi vào nh\ng nhánh tìm ki.m có khD năng nh t (gi=ng tìm ki.m leo ñ9i d=c
ñWng), nhưng ta sƒ không bi lnn qunn trong các nhánh này vì n.u càng ñi sâu vào
m4t hưeng mà ta phát hign ra rjng hưeng này càng ñi thì càng tg, ñ.n mWc nó x u
hơn cD nh\ng hưeng mà ta chưa ñi, thì ta sƒ không ñi ti.p hưeng hign tOi n\a mà
chNn ñi theo m4t hưeng t=t nh t trong s= nh\ng hưeng chưa ñi. Đó là tư tưmng ch$
ñOo c$a tìm ki.m BFS. ĐT hiTu ñưUc tư tưmng này. BOn hãy xem ví dM sau :
Hình Minh hNa thuCt giDi Best?First Search
Khmi ñku, chw có m4t nút (trOng thái) A nên nó sƒ ñưUc mm r4ng tOo ra 3 nút mei B,C
và D. Các con s= dưei nút là giá tri cho bi.t ñ4 t=t c$a nút. Con s= càng nht, nút
càng t=t. Do D là nút có khD năng nh t nên nó sƒ ñưUc mm r4ng ti.p sau nút A và
sinh ra 2 nút k. ti.p là E và F. Đ.n ñây, ta lOi th y nút B có v— có khD năng nh t
(trong các nút B,C,E,F) nên ta sƒ chNn mm r4ng nút B và tOo ra 2 nút G và H. Nhưng
lOi m4t lkn n\a, hai nút G, H này ñưUc ñánh giá ít khD năng hơn E, vì th. sq chú ý lOi
trm v0 E. E ñưUc mm r4ng và các nút ñưUc sinh ra th E là I và J. • bưec k. ti.p, J sƒ
ñưUc mm r4ng vì nó có khD năng nh t. Quá trình này ti.p tMc cho ñ.n khi tìm th y
m4t lZi giDi.
Lưu ý rjng tìm ki.m này r t gi=ng vei tìm ki.m leo ñ9i d=c ñWng, vei 2 ngoOi lg.
Trong leo núi, m4t trOng thái ñưUc chNn và t t cD các trOng thái khác bi loOi bt,
không bao giZ chúng ñưUc xem xét lOi. Cách xx lý dWt khoát này là m4t ñfc trưng
c$a leo ñ9i. Trong BFS, tOi m4t bưec, cũng có m4t di chuyTn ñưUc chNn nhưng nh\ng
cái khác van ñưUc gi\ lOi, ñT ta có thT trm lOi xét sau ñó khi trOng thái hign tOi trm
nên kém khD năng hơn nh\ng trOng thái ñã ñưUc lưu tr\. Hơn n\a, ta chNn trOng
thái t=t nh t mà không quan tâm ñ.n nó có t t hơn hay không các trOng thái trưec
ñó. Đi0u này tương phDn vei leo ñ9i vì leo ñ9i sƒ dhng n.u không có trOng thái ti.p
theo nào t=t hơn trOng thái hign hành.
ĐT cài ñft các thuCt giDi theo kiTu tìm ki.m BFS, ngưZi ta thưZng ckn dùng 2 tCp
hUp sau :
OPEN : tCp chWa các trOng thái ñã ñưUc sinh ra nhưng chưa ñưUc xét ñ.n (vì ta ñã
chNn m4t trOng thái khác). Thqc ra, OPEN là m4t loOi hàng ñUi ưu tiên (priority
queue) mà trong ñó, phkn tx có ñ4 ưu tiên cao nh t là phkn tx t t nh t. NgưZi ta
thưZng cài ñft hàng ñUi ưu tiên bjng Heap. Các bOn có thT tham khDo thêm trong
các tài ligu v0 C u trúc d\ ligu v0 loOi d\ ligu này.
CLOSE : tCp chWa các trOng thái ñã ñưUc xét ñ.n. Chúng ta ckn lưu tr\ nh\ng trOng
thái này trong b4 nhe ñT ñ0 phòng trưZng hUp khi m4t trOng thái mei ñưUc tOo ra lOi
trùng vei m4t trOng thái mà ta ñã xét ñ.n trưec ñó. Trong trưZng hUp không gian tìm
ki.m có dOng cây thì không ckn dùng tCp này.
Thuft giSi BESTIFIRST SEARCH
1. Đft OPEN chWa trOng thái khmi ñku.
2. Cho ñ.n khi tìm ñưUc trOng thái ñích hofc không còn nút nào trong OPEN,
thqc hign :
2.a. ChNn trOng thái tWt nh8t (Tmax) trong OPEN (và xóa Tmax khti
OPEN)
2.b. N.u Tmax là trOng thái k.t thúc thì thoát.
2.c. NgưUc lOi, tOo ra các trOng thái k. ti.p Tk có thT có th trOng thái
Tmax. Đ=i vei m•i trOng thái k. ti.p Tk thqc hign :
Tính f(Tk); Thêm Tk vào OPEN
BFS khá ñơn giDn. Tuy vCy, trên thqc t., cũng như tìm ki.m chi0u sâu và chi0u r4ng,
hi.m khi ta dùng BFS m4t cách trqc ti.p. Thông thưZng, ngưZi ta thưZng dùng các
phiên bDn c$a BFS là AT, AKT và A*
Thông tin vJ quá kh/ và tương lai
Thông thưZng, trong các phương án tìm ki.m theo kiTu BFS, ñ4 t=t f c$a m4t trOng
thái ñưUc tính dqa theo 2 hai giá tri mà ta gNi là là g và h’. h’ chúng ta ñã bi.t, ñó là
m4t ưec lưUng v0 chi phí th trOng thái hign hành cho ñ.n trOng thái ñích (thông tin
tương lai). Còn g là "chi0u dài quãng ñưZng" ñã ñi th trOng thái ban ñku cho ñ.n
trOng thái hign tOi (thông tin quá khW). Lưu ý rjng g là chi phí thqc sq (không phDi
chi phí ưec lưUng). ĐT dr hiTu, bOn hãy quan sát hình sau :
Hình 6.14 Phân bigt khái nigm g và h’
K.t hUp g và h’ thành f’ (f’ = g + h’) sƒ thT hign m4t ưec lưUng v0 "tlng chi phí" cho
con ñưZng th trOng thái bot ñku ñ.n trOng thái k.t thúc dNc theo con ñưZng ñi qua
trOng thái hign hành. ĐT thuCn tign cho thuCt giDi, ta quy ưec là g và h’ ñ0u không
âm và càng nht nghĩa là càng t=t.
III.5. Thuft giSi AT
ThuCt giDi AT là m4t phương pháp tìm ki.m theo kiTu BFS vei ñ4 t=t c$a nút là giá tri
hàm g – tlng chi0u dài con ñưZng ñã ñi th trOng thái bot ñku ñ.n trOng thái hign tOi.
Thuft giSi AT
1. Đft OPEN chWa trOng thái khmi ñku.
2. Cho ñ.n khi tìm ñưUc trOng thái ñích hofc không còn nút nào trong OPEN,
thqc hign :
2.a. ChNn trOng thái (Tmax) có giá trj g nhk nh8t trong OPEN (và
xóa Tmax khti OPEN)
2.b. N.u Tmax là trOng thái k.t thúc thì thoát.
2.c. NgưUc lOi, tOo ra các trOng thái k. ti.p Tk có thT có th trOng thái
Tmax. Đ=i vei m•i trOng thái k. ti.p Tk thqc hign :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Thêm Tk vào OPEN.
* Vì chw sx dMng hàm g (mà không dùng hàm ưec lưUng h’) fsñT ñánh giá ñ4 t=t c$a
m4t trOng thái nên ta cũng có thT xem AT chw là m4t thuCt toán.
III.6. Thuft giSi AKT
(Algorithm for Knowlegeable Tree Search)
ThuCt giDi AKT mm r4ng AT bjng cách sx dMng thêm thông tin ưec lưUng h’. Đ4 t=t
c$a m4t trOng thái f là tlng c$a hai hàm g và h’.
Thuft giSi AKT
1. Đft OPEN chWa trOng thái khmi ñku.
2. Cho ñ.n khi tìm ñưUc trOng thái ñích hofc không còn nút nào trong OPEN,
thqc hign :
2.a. ChNn trOng thái (Tmax) có giá trj f nhk nh8t trong OPEN (và xóa
Tmax khti OPEN)
2.b. N.u Tmax là trOng thái k.t thúc thì thoát.
2.c. NgưUc lOi, tOo ra các trOng thái k. ti.p Tk có thT có th trOng thái
Tmax. Đ=i vei m•i trOng thái k. ti.p Tk thqc hign :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Tính h’(Tk)
f(Tk) = g(Tk) + h’(Tk);
Thêm Tk vào OPEN.
III.7. Thuft giSi A*
A* là m4t phiên bDn ñfc bigt c$a AKT áp dMng cho trưZng hUp ñ9 thi. ThuCt giDi A* có
sx dMng thêm tCp hUp CLOSE ñT lưu tr\ nh\ng trưZng hUp ñã ñưUc xét ñ.n. A* mm
r4ng AKT bjng cách bl sung cách giDi quy.t trưZng hUp khi "mm" m4t nút mà nút
này ñã có svn trong OPEN hofc CLOSE. Khi xét ñ.n m4t trOng thái Ti bên cOnh vigc
lưu tr\ 3 giá tri cơ bDn g,h’, f’ ñT phDn ánh ñ4 t=t c$a trOng thái ñó, A* còn lưu tr\
thêm hai thông s= sau :
1. Tr ng thái cha c+a tr ng thái Ti (ký hi-u là Cha(Ti) : cho bi.t trOng thái dan ñ.n
trOng thái Ti. Trong trưZng hUp có nhi0u trOng thái dan ñ.n Ti thì chNn Cha(Ti) sao
cho chi phí ñi th trOng thái khmi ñku ñ.n Ti là th p nh t, nghĩa là :
