Đ tài: Xây d ng ch ng trình minh h a thu t toán A*ề ự ươ ọ ậ
GVHD: Nông Th Hoaị
M C L CỤ Ụ
L I NÓI Đ UỜ Ầ
M c dù trong các th k 18, 19 và đ u th k 20, s hình th c hóa trong khoa h c vàặ ế ỉ ầ ế ỉ ự ứ ọ
tính toán đã t o đi u ki n tiên quy t v m t trí tu cho vi c nghiên c u ạ ề ệ ế ề ặ ệ ệ ứ Trí tu nhânệ
t oạ, nh ng ph i cho đ n th k 20 cùng v i s ra đ i c a máy tính s thì ư ả ế ế ỉ ớ ự ờ ủ ố Trí tu nhânệ
t oạ m i tr thành m t ngành khoa h c có s c s ng. M t thành ph n không th thi uớ ở ộ ọ ứ ố ộ ầ ể ế
đ c c a ượ ủ Trí tu nhân t oệ ạ là vi c dùng các máy tính s nh m t ph ng ti n ch nệ ố ư ộ ươ ệ ọ
l a đ t o ra và th nghi m các lý thuy t v trí tu . Hai m i quan tâm n n t ng nh tự ể ạ ử ệ ế ề ệ ố ề ả ấ
c a các nhà nghiên c u ủ ứ Trí tu nhân t oệ ạ là bi u di n tri th c và tìm ki m. S quanể ễ ứ ế ự
tâm th nh t chú ý đ n v n đ n m b t theo m t ngôn ng tri th c đ y đ mà hành viứ ấ ế ấ ề ắ ắ ộ ữ ứ ầ ủ
thông minh đòi h i. Trong khi đó, tìm ki m là kĩ thu t gi i quy t v n đ theo cáchỏ ế ậ ả ế ấ ề
kh o sát có h th ng m t không gian tr ng thái bài toán, t c là các giai đo n tu n t vàả ệ ố ộ ạ ứ ạ ầ ự
có ch n l a trong quá trình gi i quy t v n đ . ọ ự ả ế ấ ề
Trong các chi n l c tìm ki m, ng i ta bi u di n quá trình gi i quy t v n đế ượ ế ườ ể ễ ả ế ấ ề
nh m t quá trình tìm ki m đ ng đi trên m t đ th không gian tr ng thái mà trong đó:ư ộ ế ườ ộ ồ ị ạ
m i tr ng thái bài toán đ c xem nh m t nút c a đ th hay còn g i là m t tr ng tháiỗ ạ ượ ư ộ ủ ồ ị ọ ộ ạ
và các đ ng chuy n tr ng thái khi áp d ng các phép toán h p l vào m t tr ng tháiườ ể ạ ụ ợ ệ ộ ạ
nào đó s chuy n bài toán t tr ng thái này sang tr ng thái khác đ c g i là các liên k tẽ ể ừ ạ ạ ượ ọ ế
c a đ th . Đây không ph i ch là m t trong nh ng kĩ thu t hi u qu mà tính quy t c vàủ ồ ị ả ỉ ộ ữ ậ ệ ả ắ
chính xác c a nó làm cho vi c cài đ t trên máy tính mang tính tr c ti p.ủ ệ ặ ự ế
Trong bài t p l n này, em tìm hi u v ậ ớ ể ề Thu t toán tìm ki m A*ậ ế và s d ng ngônử ụ
ng l p trình Visual Basic đ xây d ng ch ng trình minh h a cho thu t toán. D a trênữ ậ ể ự ươ ọ ậ ự
s ch b o t n tình c a các th y cô giáo và s giúp đ c a các b n cùng l p, d a trênự ỉ ả ậ ủ ầ ự ỡ ủ ạ ớ ự
Sinh viên th c hi n: Ngô Hoàng Liêmự ệ
1
L p ĐHCQ K6Bớ
Đ tài: Xây d ng ch ng trình minh h a thu t toán A*ề ự ươ ọ ậ
GVHD: Nông Th Hoaị
nh ng ki n th c đã h c, em đã hoàn thành đ tài này tuy nhiên v n còn nhi u sai sót,ữ ế ứ ọ ề ẫ ề
r t mong có s đóng góp ý ki n c a các th y cô và các b n đ đ tài c a em đ cấ ự ế ủ ầ ạ ể ề ủ ượ
hoàn thi n h n.ệ ơ
Em xin chân thành c m n!ả ơ
Ph n I: LÝ THUY T C Sầ Ế Ơ Ở
I – TRÍ TU NHÂN T O LÀ GÌỆ Ạ
Thu t ng ậ ữ trí tu nhân t oệ ạ đ c John McCarthy đ a ra trong h i th o ượ ư ộ ả ở
Dartmouth vào mùa hè năm 1956. Đây đ c xem là th i đi m ra đ i th t s c a lĩnhượ ờ ể ờ ậ ự ủ
v c nghiên c u ự ứ trí tu nhân t oệ ạ (TTNT).
Trong các sách vi t v TTNT các năm g n đây, các tác gi đã đ a ra nhi u đ nhế ề ầ ả ư ề ị
nghĩa v TTNT, nh ng nhìn chung, ta có th hi u: “TTNT là s thi t k và nghiên c uề ư ể ể ự ế ế ứ
các ch ng trình máy tính ng x m t cách thông minh. Các ch ng trình này đ c xâyươ ứ ử ộ ươ ượ
d ng đ th c hi n các hành vi mà khi th c hi n ng i và đ ng v t chúng ta xem làự ể ự ệ ự ệ ở ườ ộ ậ
thông minh” (“Dean, Allen and Aloimonos, 1995).
Hi n nay nhi u nhà nghiên c u quan ni m r ng, TTNT là lĩnh v c nghiên c u sệ ề ứ ệ ằ ự ứ ự
thi t k các tác nhân thông minh (intelligent agent). Tác nhân thông minh là b t c cái gìế ế ấ ứ
t n t i trong môi tr ng và hành đ ng m t cách thông minh. M c tiêu khoa h c c aồ ạ ườ ộ ộ ụ ọ ủ
TTNT là hi u đ c b n ch t các hành vi thông minh. M c tiêu th c ti n, công nghể ượ ả ấ ụ ự ễ ệ
c a TTNT là xây d ng nên các h thông minh, các máy thông minh.ủ ự ệ
M t s ngành khoa h c khác cũng nghiên c u các năng l c đ c xem là thông minhộ ố ọ ứ ự ượ
c a con ng i nh : Tri t h c, Tâm lý h c… Nh ng khác v i các ngành khoa h c trên,ủ ườ ư ế ọ ọ ư ớ ọ
TTNT là m t ngành c a khoa h c máy tính – nghiên c u x lý thông tin b ng máy tính.ộ ủ ọ ứ ử ằ
Do đó, TTNT đ t ra m c tiêu nghiên c u: làm th nào đ hi u đ c các hành vi thôngặ ụ ứ ế ể ể ượ
minh b ng thu t toán, r i nghiên c u các ph ng pháp cài đ t các ch ng trình có thằ ậ ồ ứ ươ ặ ươ ể
Sinh viên th c hi n: Ngô Hoàng Liêmự ệ
2
L p ĐHCQ K6Bớ
Đ tài: Xây d ng ch ng trình minh h a thu t toán A*ề ự ươ ọ ậ
GVHD: Nông Th Hoaị
th c hi n đ c các hành vi thông minh. Nh v y chúng ta c n xây d ng các mô hìnhự ệ ượ ư ậ ầ ự
tính toán (computational models) ph c v cho vi c gi i thích, mô t các hành vi thôngụ ụ ệ ả ả
minh b ng thu t toán, ti p theo ta c n ch ra tính hi u qu , tính kh thi c a thu t toánằ ậ ế ầ ỉ ệ ả ả ủ ậ
th c hi n m t nhi m v và t đó đ a ra các ph ng pháp cài đ t.ự ệ ộ ệ ụ ừ ư ươ ặ
II – GI I QUY T V N Đ B NG TÌM KI MẢ Ế Ấ Ề Ằ Ế
V n đ tìm ki m, m t cách t ng quát, có th hi u là tìm m t đ i t ng th a mãnấ ề ế ộ ổ ể ể ộ ố ượ ỏ
m t s đòi h i nào đó, trong m t t p h p r ng l n các đ i t ng. Trong các lĩnh v cộ ố ỏ ộ ậ ợ ộ ớ ố ượ ự
nghiên c u c a trí tu nhân t o, chúng ta th ng xuyên ph i đ i đ u v i v n đ tìmứ ủ ệ ạ ườ ả ố ầ ớ ấ ề
ki m. Đ c bi t trong l p k ho ch và h c máy, tìm ki m đóng vai trò r t quan tr ng.ế ặ ệ ậ ế ạ ọ ế ấ ọ
Trong khuôn kh ch ng trình gi ng d y c a nhà tr ng, chúng ta s đ c tìmổ ươ ả ạ ủ ườ ẽ ượ
hi u các k thu t sau:ể ỹ ậ
Các k thu t tìm ki m mù.ỹ ậ ế
Các k thu t tìm ki m kinh nghi m (tìm ki m heuristic). ỹ ậ ế ệ ế
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 .ươ ế ố ủ
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 t đ 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 đ c đ 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.ượ ọ ụ
Các chi n l c tìm ki m bao g m:ế ượ ế ồ
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.ậ ậ
Sinh viên th c hi n: Ngô Hoàng Liêmự ệ
3
L p ĐHCQ K6Bớ
Đ tài: Xây d ng ch ng trình minh h a thu t toán A*ề ự ươ ọ ậ
GVHD: Nông Th Hoaị
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 hóa: Thu t toán di truy n.ế ắ ướ ự ế ậ ề
3.1 – M t s quy c trong bài toán tìm đ ng điộ ố ướ ườ
Giá tr c a cung (a,b) là đ dài đ ng n i t a đ n b.ị ủ ộ ườ ố ừ ế
Đ dài đ ng đi t tr ng thái đ u đ n tr ng thái k t thúc là t ng đ dài cácộ ườ ừ ạ ầ ế ạ ế ổ ộ
cung trên đ ng đi.ườ
Không gian tìm ki m: T t c các đ ng đi t tr ng thái đ u đ n tr ng tháiế ấ ả ườ ừ ạ ầ ế ạ
đích.
3.2 – Xây d ng hàm đánh giáự
Gi s ả ử u là m t tr ng thái t i (đi t tr ng thái đ u đ n ộ ạ ớ ừ ạ ầ ế u), xây d ng các hàm:ự
g(u): đánh giá đ dài đ ng đi t tr ng thái đ u đ n u.ộ ườ ừ ạ ầ ế
h(u): đánh giá đ dài đ ng đi t u đ n tr ng thái đích.ộ ườ ừ ế ạ
f(u) = g(u) + h(u): đánh giá đ dài đ ng đi t tr ng thái đ u đ n tr ng tháiộ ườ ừ ạ ầ ế ạ
đích mà đi qua u.
IV – 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). T c là: trong các tr ng thái ch phát tri n, ch n tr ng thái có giá tr hàmứ ạ ờ ể ọ ạ ị
đánh giá nh nh t (ho c l n nh t) đ phát tri n ti p. Đ nh đ c phát tri n có th ỏ ấ ặ ớ ấ ể ể ế ỉ ượ ể ể ở
m c hi n t i ho c các m c trên.ứ ệ ạ ặ ứ
4.1 – Thu t toánậ
1. Kh i t o danh sách L ch ch a tr ng thái ban đ u;ở ạ ỉ ứ ạ ầ
2. Loop do
Sinh viên th c hi n: Ngô Hoàng Liêmự ệ
4
L p ĐHCQ K6Bớ
Đ tài: Xây d ng ch ng trình minh h a thu t toán A*ề ự ươ ọ ậ
GVHD: Nông Th Hoaị
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 đích ạ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 sao cho tr ng thái cóắ ế ứ ự ầ ủ ạ
giá tr c a hàm f nh nh t đ u danh sách;ị ủ ỏ ấ ở ầ
End loop;
4.2 – M t s nh n xét v thu t toán A*ộ ố ậ ề ậ
Chúng ta đ a ra m t s nh n xét v thu t toán A* nh sau:ư ộ ố ậ ề ậ ư
Ng i ta ch ng minh đ c r ng, n u hàm đánh giá ườ ứ ượ ằ ế h(u) là đánh giá th p (tr ngấ ườ
h p đ c bi t, ợ ặ ệ h(u) = 0 v i m i tr ng thái ớ ọ ạ u) thì thu t toán A* là thu t toán ậ ậ t i uố ư , t cứ
là nghi m mà nó tìm ra là ngi m t i u. Ngoài ra, n u đ dài c a các cung không nhệ ệ ố ư ế ộ ủ ỏ
h n m t s d ng δ nào đó thì thu t toán A* là thu t toán ơ ộ ố ươ ậ ậ đ y đầ ủ theo nghĩa r ng, nóằ
luôn d ng và tìm ra cây nghi m.ừ ệ
Trong tr ng h p hàm đánh giá ườ ợ h(u) = 0 v i m i ớ ọ u, thu t toán A* chính là thu tậ ậ
toán tìm ki m t t nh t đ u tiên v i hàm đánh giá ế ố ấ ầ ớ g(u).
Thu t toán A* đã đ c ch ng t r ng là thu t toán hi u qu nh t trong s cácậ ượ ứ ỏ ằ ậ ệ ả ấ ố
thu t toán đ y đ và t i u cho v n đ tìm ki m đ ng đi ng n nh t.ậ ầ ủ ố ư ấ ề ế ườ ắ ấ
Sinh viên th c hi n: Ngô Hoàng Liêmự ệ
5
L p ĐHCQ K6Bớ