Đ 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 và s d ng ngôn ậ ớ ề Thu t toán tìm ki m A* ế ậ ể ử ụ
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 ữ ậ ự ể ươ ự ậ ọ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
1
L p ĐHCQ K6B
ớ
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 ự ỉ ả ậ ỡ ủ ự ủ ự ạ ầ ớ
Đ 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 này đ c xây ươ ng trình máy tính ng x m t cách thông minh. Các ch ử ộ ứ ươ ượ
ng i và đ ng v t chúng ta xem là d ng đ th c hi n các hành vi mà khi th c hi n ự ể ự ệ ở ự ệ ườ ậ ộ
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ì ế ế ấ ứ
i trong môi tr t n t ồ ạ ườ ọ ủ 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 ộ ố ự ượ ứ ọ
t h c, Tâm lý h c… Nh ng khác v i các ngành khoa h c trên, c a con ng ủ ườ i nh : Tri ư ế ọ ư ọ ọ ớ
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 ể ể ụ ứ ế ặ ượ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
2
L p ĐHCQ K6B
ớ
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 ứ ằ ậ ồ ươ ặ ươ ể
Đ 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
ng xuyên ph i đ i đ u v i v n đ tìm nghiên c u c a trí tu nhân t o, chúng ta th ệ ứ ủ ạ ườ ả ố ầ ớ ấ ề
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). ế ệ ế ậ ỹ
i u. Các k thu t tìm ki m t ậ ế ỹ ố ư
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 ư ể ể ộ ổ
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 đó t ượ ế ượ ị ủ ố ượ ộ ố ớ
f(x), m c tiêu c a ta là tìm đ ng có giá tr ủ ụ c đ i t ượ ố ượ ị 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 ậ ỹ ườ ắ ấ ạ ậ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
3
L p ĐHCQ K6B
ớ
A*, thu t toán nhánh – và – c n. ậ ậ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
ng t Các k thu t tìm ki m đ i 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. ế
ng đi t tr ng thái đ u đ n tr ng thái k t thúc là t ng đ dài các Đ dài đ ộ ườ ừ ạ ế ế ầ ạ ổ ộ
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 i (đi t tr ng thái đ u đ n ả ử u là m t tr ng thái t ộ ạ ớ ừ ạ ế 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; ỉ ứ ở ạ ạ ầ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
4
L p ĐHCQ K6B
ớ
2. Loop do
Đ 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;}
đ u danh sách L; 2.2. Lo i tr ng thái u ạ ạ ở ầ
then 2.3. if u là tr ng thái đích ạ
{ 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
t, u) thì thu t toán A* là thu t toán h p đ c bi ặ ợ ệ h(u) = 0 v i m i tr ng thái ọ ạ ớ ậ ậ i uố ư , t cứ t
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 ệ ệ ố ư ủ ế ộ ỏ
ng δ nào đó thì thu t toán A* là thu t toán h n m t s d ơ ộ ố ươ ậ ậ đ 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 g(u). ế ố t nh t đ u tiên v i hàm đánh giá ớ ấ ầ
Thu t toán A* đã đ r ng là thu t toán hi u qu nh t trong s các ậ ượ c ch ng t ứ ỏ ằ ệ ậ ả ấ ố
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
5
L p ĐHCQ K6B
ớ
thu t toán đ y đ và t i u cho v n đ tìm ki m đ ầ ủ ậ ố ư ề ế ấ ườ ng đi ng n nh t. ắ ấ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
4.3 – Ví d minh h a ụ
ọ
Đ th y đ c thu t toán A* làm vi c ra sao, ta xét đ th không gian tr ng thái nh ể ấ ượ ồ ị ệ ạ ậ ư
hình v . 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 cung đó, các s c nh các đ nh là giá tr c a hàm ạ ố ạ ị ủ ộ ỉ h. Đ u tiên, ầ
A sinh ra các đ nh con C, D, E và F. Tính giá tr hàm f t i các đ nh này ta phát tri n đ nh ể ỉ ỉ ị ạ ỉ
có:
g(C) = 9 f(C) = 9 + 15 = 24
g(D) = 7 f(D) = 7 + 6 = 13
g(E) = 13 f(E) = 13 + 8 = 21
g(F) = 20 f(F) = 20 + 7 = 27
Nh v y đ nh t ư ậ ỉ ố t nh t là ấ D (vì f(D) = 13 là nh nh t). phát tri n đ nh ỏ ỉ D, ta nh nậ ể ấ
đ ượ c các đ nh con ỉ H và E. ta đánh giá H và E (m i).ớ
g(H) = g(D) + đ dài cung (D, H) = 7 + 8 = 15 ộ
f(H) = 15 + 10 = 25
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
6
L p ĐHCQ K6B
ớ
Đ ng đi t i ườ ớ E qua D có đ dài: ộ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
g(E) = g(D) + đ dài cung (D,E) = 7 + 4 = 11 ộ
f(E) = g(E) + h(E) = 11 + 8 = 19
E v i đánh giá f(E) = 19 là đ nh t Trong s các đ nh ch phát tri n thì đ nh ờ ể ố ỉ ỉ ớ ỉ ố ấ t nh t.
Phát tri n đ nh này, ta nh n đ c các đ nh con c a nó là K và I. Chúng ta ti p t c quá ể ậ ỉ ượ ủ ỉ ế ụ
trình trên cho t ng đi ớ i khi đ nh đ ỉ ượ c ch n đ phát tri n là đ nh k t thúc ể ể ế ọ ỉ B, đ dài đ ộ ườ
ng n nh t t i ả ấ ớ B là g(B) = 19. Đ theo dõi quá trình làm vi c c a thu t toán, ta l p b ng ệ ủ ể ậ ậ ắ
phân tích g m 4 c t: ồ ộ
L n l p: s l n l p c a thu t toán ố ầ ặ ủ ầ ặ ậ
u: đ nh phát tri n u ể ỉ
v: các đ nh con c a u ỉ ủ
L: Danh sách L
V i quy c: đ nh . Ta có b ng phân tích nh sau ớ ướ ư ả ỉ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
7
L p ĐHCQ K6B
ớ
Đ ng đi ng n nh t: A → D → E → I → B ườ ắ ấ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Quá trình tìm ki m trên đ c mô t b i cây tìm ki m sau. ế ượ ả ở ế
Ph n II: XÂY D NG CH
NG TRÌNH MINH H A
Ự
ầ
ƯƠ
Ọ
I – GI I THI U S L C V NGÔN NG L P TRÌNH VISUAL BASIC VÀ Ớ Ơ ƯỢ Ệ Ữ Ậ Ề
CÔNG C L P TRÌNH MICROSOFT VISUAL BASIC Ụ Ậ
Visual Basic (vi t t t h ng s ki n ế ắ VB) là m t ộ ngôn ng l p trình ữ ậ ướ ự ệ (event-driven)
và môi tr c phát tri n đ u tiên b i ườ ng phát tri n tích h p ể ợ (IDE) k t bó đ ế ượ ở Alan ể ầ
Cooper d i tên D án Ruby ( Project Ruby), và sau đó đ ướ ự ả ế c ượ Microsoft mua và c i ti n
nhi u. Visual Basic đã đ c thay th b ng ề ượ ế ằ Visual Basic.NET. Phiên b n cũ c a Visual ủ ả
Basic b t ngu n ph n l n t ồ ầ ớ ừ BASIC và đ l p trình viên phát tri n các ể ậ ể ắ giao di n ng ệ ườ i
dùng đ h a (Rapid Application ồ ọ (GUI) theo mô hình phát tri n ng d ng nhanh ể ứ ụ
Development, RAD); truy c p các ậ ơ ở ữ ệ dùng DAO (Data Access Objects), RDO c s d li u
ố (Remote Data Objects), hay ADO (ActiveX Data Objects); và l p các đi u khi n và đ i ề ể ậ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
8
L p ĐHCQ K6B
ớ
ng ượ ActiveX. t
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
M t l p trình viên có th phát tri n ng d ng ộ ậ ể ể ứ ụ dùng các thành ph nầ (component) có
s n trong Visual Basic. Các ch ẵ ươ ể ử ụ ng trình b ng Visual Basic cũng có th s d ng ằ
Windows API, nh ng làm v y thì ph i s d ng các khai báo hàm bên ngoài. ả ử ụ ư ậ
ng m i Trong lĩnh v c ự l p trình th ậ ươ ạ , Visual Basic có m t trong nh ng nhóm khách ữ ộ
hàng l n nh t. Theo m t s ngu n, vào năm 2003, 52% c a nh ng l p trình viên s ộ ố ủ ữ ậ ấ ớ ồ ử
d ng Visual Basic, làm nó thành ngôn ng l p trình ph bi n nh t vào lúc đó. Tuy ụ ổ ế ữ ậ ấ
nhiên, cu c nghiên c u c a Evans Data cho r ng 43% c a các l p trình viên đó có ý ứ ủ ủ ằ ậ ộ
đ nh đ i qua m t ngôn ng khác. Dù v y, trong th c hành thí nghi m thì VB v n đ ị ữ ự ệ ậ ẫ ộ ổ ượ c
dùng khá ph bi n vì s g n gũi và d h c d làm c a nó. Hi n nay xu h ổ ế ự ầ ễ ọ ủ ệ ễ ướ ậ ng l p
trình đang chuy n d n sang .NET vì nh ng u đi m và l i th tuy t v i c a nó. ữ ư ể ầ ể ợ ệ ờ ủ ế
Microsoft Visual Basic. NET hay còn g i là VB.NET đ c Microsoft phát tri n t ọ ượ ể ừ
cu i ố th p niên 1990 ậ và ra phiên b n đ u vào năm ả ầ 2002 (cùng v i ớ Visual C# và
ASP.NET). Phiên b n m i nh t hi n nay là Visual Basic. NET 2010. ệ ấ ả ớ
II – T NG QUAN V CH NG TRÌNH Ổ Ề ƯƠ
ng trình
2.1 – C u trúc ch ấ
ươ
Ch ng trình g m có các thành ph n nh sau: ươ ư ầ ồ
Form chính: mainForm.vb
Form tác gi : author.vb ả
Form h ng d n s d ng: tutorial.vb ướ ẫ ử ụ
Form hi n th b ng k t qu : process.vb ị ả ể ế ả
Module ch a các hàm và th t c h tr : functions.vb ủ ụ ỗ ợ ứ
Module ch a các hàm và th t c v : draw.vb ủ ụ ẽ ứ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
9
L p ĐHCQ K6B
ớ
Module ch a các hàm và th t c l u, m đ th : saveload.vb ủ ụ ư ở ồ ị ứ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Khai báo các l p s d ng trong ch ng trình: classes.vb ớ ử ụ ươ
Form giao di n chính c a ch ệ ủ ươ ủ ng trình (mainForm.vb) bao g m các control c a ồ
Visual Basic, các s ki n c a control đ c l p trình bên trong code c a mainForm.vb. ự ệ ủ ượ ậ ủ
Thu t toán A* và các thao tác nh p, xu t đ c th hi n form này. Các b n có th m ấ ượ ậ ậ ể ệ ở ể ở ạ
project đi kèm v i t p báo cáo này đ bi t thêm chi ti t. ớ ậ ể ế ế
Form h ng d n s d ng (tutorial.vb) hi n th nh ng h ng d n c b n và m t s ướ ẫ ử ụ ị ữ ể ướ ẫ ơ ả ộ ố
chú ý khi s d ng ch ng trình. ử ụ ươ
Form tác gi (author.vb) bao g m các thông tin v ch ng trình và tác gi . Code ả ề ồ ươ ả
ng trình r i đ a ra hi n th (code đ c vi t bên c a form này ch l y thông tin ch ủ ỉ ấ ươ ồ ư ể ị ượ ế
trong ph n onload c a form). ủ ầ
Form hi n th k t qu (process.vb) bao g m hai control, m t label ghi tiêu đ và ị ế ề ể ả ộ ồ
m t listView. Code c a form này ch l y k t qu tính toán đ vào listView và hi n th ra ỉ ấ ế ủ ể ả ộ ổ ị
màn hình (vi t trong ph n onload c a form). ế ủ ầ
ph n đ nh nghĩa các hàm, th t c trong module và Chúng ta s đi chi ti ẽ t h n ế ơ ở ủ ụ ầ ị
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
10
L p ĐHCQ K6B
ớ
ng trình ph n sau. đ nh nghĩa các class s d ng trong ch ị ử ụ ươ ở ầ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
2.2 – Ho t đ ng
ạ ộ
ấ ế Các th t c và s ki n trong form chính s ch a các dòng l nh nh p và xu t k t ẽ ứ ự ệ ủ ụ ệ ậ
qu . Quá trình nh p và xu t đ c th c hi n thông qua các ph ng th c có s n c a VB ấ ượ ả ậ ự ệ ươ ẵ ủ ứ
và các hàm, th t c đ c đ nh nghĩa trong các module. Đ ph c v cho thu t toán A* - ủ ụ ượ ị ể ụ ụ ậ
thu t toán chính c a ch ng trình - thì các thành ph n h tr cho nó cũng đ ủ ậ ươ ỗ ợ ầ ượ c đ nh ị
nghĩa đ y đ trong các module. ầ ủ
2.3 – Các l p đ
c s d ng
ớ
ượ ử ụ
Đ làm vi c có hi u qu h n và t n d ng các u đi m c a l p trình h ậ ủ ậ ả ơ ư ụ ệ ệ ể ể ướ ố ng đ i
ng, ch ng trình đã s d ng ph ng pháp l p trình này. M t l p các đ nh đ t ượ ươ ử ụ ươ ộ ớ ậ ỉ ượ c
khai báo trong file classes.vb. Th c ch t đây là file đ c thêm vào t menu add new ự ấ ượ ừ
item, class.
Các b n m file này ra s th y các đ nh nghĩa cho các l p. Có 3 l p đ ẽ ấ ớ ượ ử ụ c s d ng ạ ở ớ ị
trong ch ng trình là lopDinh, Child và listItem trong đó: ươ
lopDinh là l p chính bao g m các thu c tính c n thi ầ ớ ồ ộ ế ủ t c a m t đ nh trong ộ ỉ
ả thu t toán A* (t a đ , tên đ nh, giá tr hàm đánh giá, các đ nh con và kho ng ị ọ ộ ậ ỉ ỉ
cách t ng ng, các đ nh cha, giá tr hàm f và g) ươ ứ ỉ ị
Child là l p các con c a m t đ nh, nó g m các thu c tính nh cname (tên ộ ỉ ủ ư ớ ộ ồ
con) và cdistance(kho ng cách t cha c a nó đ n nó) ả ừ ủ ế
listItem là l p đ ớ ượ ử ụ ế c s d ng đ l u k t qu tính toán và đ a ra b ng k t ể ư ư ế ả ả
qu . L p này g m 4 thu c tính t ồ ả ớ ộ ươ ệ ng ng v i b ng s d ng đ th c hi n ử ụ ể ự ớ ả ứ
thu t toán A* (các thu c tính g m s l n l p, đ nh u, t p các đ nh con v, và ố ầ ặ ậ ậ ộ ồ ỉ ỉ
danh sách L).
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
11
L p ĐHCQ K6B
ớ
Chi ti c chi ti t hóa ph n sau. t v l p s đ ế ề ớ ẽ ượ ế ở ầ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
2.4 – M t s giao di n ch
ng trình
ộ ố
ệ
ươ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
12
L p ĐHCQ K6B
ớ
Giao di n chính c a ch ng trình ủ ệ ươ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
i trong ch ng trình X lý l ử ỗ ươ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
13
L p ĐHCQ K6B
ớ
Sau khi tìm ki m thành công ế
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
K t qu tìm ki m ế ế ả
III – C U TRÚC CHI TI T Ấ Ế
3.1 – Đ nh nghĩa các l p
ớ
ị
c s d ng trong ch ng trình đ Các l p đ ớ ượ ử ụ ươ ượ c đ nh nghĩa đ y đ trong file ầ ủ ị
classes.vb
3.1.1 – L p các đ nh – l p chính c a ch
ủ
ớ
ớ
ỉ
ươ
ng trình – l p lopDinh ớ
L p đ nh cũng nh các l p khác trong ch ư ớ ớ ỉ ươ ng trình, không đ nh nghĩa thu c tính ị ộ
tr c ti p (đ nh nghĩa gi ng cú pháp
đ nh nghĩa các bi n riêng đ l u giá tr và đ nh nghĩa các thu c tính đ thông qua các ị ể ư ế ể ộ ị ị
thu c tính đó, l u các giá tr c n thi t vào các bi n riêng. Theo các tài li u l p trình ị ầ ư ộ ế ệ ậ ế
ng đ i t ng thì ph ng pháp này đ h ướ ố ượ ươ ượ ề ư c khuy n khích s d ng vì có nhi u u ử ụ ế
đi m h n và h n ch đ c các nh c đi m c a khai báo thu c tính tr c ti p. ế ượ ể ạ ơ ượ ự ế ủ ể ộ
Các thu c tính c a lopDinh bao g m: ủ ộ ồ
x: t a đ x c a đ nh, ki u s nguyên (Short) ọ ộ ể ố ủ ỉ
y: t a đ y c a đ nh, ki u s nguyên (Short) ọ ộ ể ố ủ ỉ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
14
L p ĐHCQ K6B
ớ
name: tên đ nh, ki u Char ỉ ể
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
value: giá tr hàm đánh giá h, ki u s nguyên (Short) ể ố ị
fval: giá tr hàm f, ki u s nguyên (Short) ể ố ị
gval: giá tr hàm g, ki u s nguyên (Short) ể ố ị
childs: các đ nh con, thu c tính này là t p h p các đ i t ố ượ ậ ộ ợ ỉ ng thu c l p Child ộ ớ
c nói đ n ngay sau ph n này. s đ ẽ ượ ế ầ
parents: có ki u là string, l u tên các đ nh cha ư ể ỉ
Riêng 2 thu c tính childs và parents đ c đ nh nghĩa tr c ti p. ộ ượ ị ự ế
ế
ế
ể
ạ
ộ
M i thu c tính đ ộ ỗ ượ ị c đ nh nghĩa b ng phát bi u: ằ ể
Ki u có th là ki u d li u nguyên th y ho c các l p đ i t ng… ể ữ ệ ố ượ ủ ể ể ặ ớ
Vi c đ nh nghĩa thu c tính nh trên gi ng cho t t c các l p đ c s d ng trong ư ệ ộ ố ị ấ ả ớ ượ ử ụ
ch ng trình. ươ
Hai th t c New và New(danh sách tham bi n) dùng đ kh i t o giá tr m c đ nh ở ạ ị ặ ủ ụ ể ế ị
cho các thu c tính c a l p. Chi ti ủ ớ ộ ế ề ị t v đ nh nghĩa l p, các b n có th tìm hi u trên th ạ ể ể ớ ư
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
15
L p ĐHCQ K6B
ớ
vi n c a Microsoft ( http://msdn.microsoft.com). ệ ủ
Đ 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 l p nói chung, đa s đ u đ c đ nh nghĩa tuân theo t ng l p trình h ố ề ớ ượ ị t ư ưở ậ ướ ng
ng. Nh ng do tính ph c t p c a ch đ i t ố ượ ứ ạ ư ủ ươ ng trình ch a ph i là cao, nên m t s ả ộ ố ư
thu c tính v n đ ẫ ượ ị c đ nh nghĩa m t cách tr c ti p. ộ ự ế ộ
3.1.2 – L p các con - l p Child
ớ
ớ
L p này g m có các thu c tính sau: ộ ồ ớ
cname: ki u Char, l u tên c a đ nh con ủ ỉ ư ể
cha nó đ n nó cdistance: ki u Short, l u giá tr là kho ng cách t ư ể ả ị ừ ế
ả M t đ nh thu c lopDinh s có m t thu c tính childs l u t p h p các con và kho ng ư ậ ộ ỉ ẽ ộ ợ ộ ộ
cách t ươ ứ ớ ng ng. V i m t dinh thu c lopDinh thì các con c a nó s là dinh.childs(i), v i ủ ẽ ộ ớ ộ
i là ch s t ng thu c l p Child). ỉ ố ươ ứ ng ng (vì childs là m t danh sách các đ i t ộ ố ượ ộ ớ
3.1.3 – l p listItem ớ
L p này g m các thu c tính t ng ng v i b ng quá trình tính toán: ồ ộ ớ ươ ứ ớ ả
lanlap: ki u Short, l u s l n l p c a thu t toán ư ố ầ ặ ủ ể ậ
ng ng u: ki u String, l u tên đ nh u và các giá tr hàm f, g t ỉ ư ể ị ươ ứ
v: ki u String, l u tên các đ nh v và các giá tr hàm f, g t ng ng ư ể ị ỉ ươ ứ
L: ki u String, l u danh sách L g m tên các đ nh và các giá tr hàm f, g t ồ ư ể ị ỉ ươ ng
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
16
L p ĐHCQ K6B
ớ
ngứ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
L p này đ c s d ng đ l u các k t qu tính toán và đ a ra b ng tính toán (form ớ ượ ử ụ ể ư ư ế ả ả
process.vb). Các giá tr hàm f, g s đ c chuy n sang xâu ký t c khi thêm vào ẽ ượ ị ể tr ự ướ
thu c tính u, v và L c a đ i t ủ ố ượ ộ ng thu c l p này. ộ ớ
3.2 – Các th t c v
ủ ụ ẽ
Các th t c v đ c đ nh nghĩa trong Module functions.vb. ủ ụ ẽ ượ ị
3.2.1 – V m t đ nh c a đ th ồ ị
ẽ ộ ỉ
ủ
S d ng các th t c và hàm có s n đ v . T o m t đ i t ng đ h a trên panel ể ẽ ạ ộ ố ượ ử ụ ủ ụ ẵ ồ ọ
ủ ụ v (panel này có tên là pnlMain và thu c form chính mainForm). S d ng th t c ẽ ử ụ ộ
FillEllipse v i chi u r ng b ng chi u ngang đ v m t hình tròn không vi n và s ể ẽ ộ ề ộ ề ề ằ ớ ử
ng t , v m t elip khác bên trên elip d ng th t c DrawEllipse đ v vi n cho nó. T ụ ể ẽ ề ủ ụ ươ ự ẽ ộ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
17
L p ĐHCQ K6B
ớ
cũ đ th hi n giá tr hàm đánh giá. ể ể ệ ị
Đ 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 l nh r nhánh If … Then đ c dùng đ căn ch nh v trí cho các ký t có đ ẽ ệ ượ ể ị ỉ ự ộ
t. Th t c drawString dùng đ v m t xâu ký t lên màn hình v trí đ r ng đ c bi ộ ặ ệ ể ẽ ộ ủ ụ ự ở ị ượ c
ch đ nh. Th t c này dùng đ v tên đ nh và giá tr hàm đánh giá. th t c v mũi tên ể ẽ ủ ụ ỉ ỉ ị ị Ở ủ ụ ẽ
c s d ng đ v giá tr kho ng cách gi a hai đ nh. n i hai đ nh c a đ th , nó cũng đ ố ủ ồ ị ỉ ượ ử ụ ể ẽ ữ ả ỉ ị
sFont, vFont là ki u font v i kích c và ki u (đ m, nghiêng, th ng, g ch chân…) ể ể ậ ớ ỡ ườ ạ
cho các xâu ký t ng ng (tên đ nh, giá tr hàm đánh giá), ta khai báo hai ki u Font t ự ươ ứ ể ị ỉ
này đ ph c v cho l nh drawString. ể ụ ụ ệ
Các tham bi n truy n vào th t c này g m có: ủ ụ ế ề ồ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
18
L p ĐHCQ K6B
ớ
dinh: đ i t ng thu c lopDinh ố ượ ộ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
p: đ i t ố ượ ng thu c l p System.Drawing.pen dùng đ v vi n ể ẽ ề ộ ớ
b: đ i t ng thu c l p System.Drawing.brush dùng đ tô màu ố ượ ộ ớ ể
3.2.2 – Th t c v mũi tên n i hai đ nh c a đ th ồ ị
ủ ụ ẽ
ủ
ố
ỉ
Trong th t c này, chúng ta s s d ng m t chút ki n th c v toán h c. Hình v ẽ ử ụ ứ ề ủ ụ ế ọ ộ ẽ
th hi n cách nghĩ và ph ể ệ ươ ng pháp th c hi n c a th t c này. ệ ủ ủ ụ ự
hình v , r là bán kính c a đ c các Ở ủ ườ ẽ ng tròn. T các t a đ c a 2 đ nh, ta tính đ ọ ộ ủ ừ ỉ ượ
dx = x2 – x1 và dy = d2 – d1, ta tính đ ượ ộ c đ dài đo n th ng n i 2 tâm c a nó, và nh ố ủ ạ ẳ ờ
đó tính đ c sinα và cosα. Theo ph ng trình đ ng tròn thì ta s tìm đ ượ ươ ườ ẽ ượ ể c giao đi m
ng tròn t ng ng. c a đo n th ng n i 2 tâm c a 2 đ nh v i đ ủ ớ ườ ủ ạ ẳ ố ỉ ươ ứ
x = x1 + r*sinα và y = y1 + r*cosα
Tùy vào h ng c a đo n th ng (v trí c a đ nh th 2 so v i đ nh th nh t) mà ta s ướ ứ ấ ủ ỉ ớ ỉ ủ ứ ẳ ạ ị ẽ
ng ng. Sau khi tính đ c 2 t a đ giao đi m, ta v m t đ c ng ho c tr ộ ặ t ừ ươ ứ ượ ẽ ộ ườ ng ể ọ ộ
th ng n i 2 t a đ này và v m t hình tam giác th hi n cho mũi tên ể ệ ẽ ộ ẳ ố ọ ộ ở ạ cu i đo n ố
th ng. Cách tính t a đ này còn đ ọ ộ ằ ượ c m r ng đ tìm các v trí thích h p đ v giá tr ị ể ẽ ở ộ ể ợ ị
kho ng cách t đ nh cha t i đ nh con. ả ừ ỉ ớ ỉ
Các l nh đ ệ ượ ử ụ c s d ng g m drawLine đ v đo n th ng, drawString đ v xâu ký ạ ể ẽ ể ẽ ẳ ồ
t ự . Bi n arrow dùng đ t o ra m t hình mũi tên ể ạ ế ộ ở ố cu i đo n th ng. ạ ẳ Ở ố ớ đây thì đ i v i
đ nh th 2, đi m cu i c a đo n th ng s cách giao đi m c a đo n th ng đó kéo dài và ỉ ố ủ ứ ủ ể ẽ ể ẳ ạ ẳ ạ
đ ườ ng tròn m t kho ng = 4. Ta s dùng kho ng tr ng này đ v ph n nh n c a mũi ả ọ ủ ể ẽ ẽ ầ ả ộ ố
tên.
Các tham bi n truy n vào c a th t c này g m có: ủ ụ ủ ế ề ồ
Đ nh cha và đ nh con: đ i t ng thu c l p lopDinh. ố ượ ỉ ỉ ộ ớ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
19
L p ĐHCQ K6B
ớ
ng ng: ki u s nguyên Short Kho ng cách t ả ươ ứ ể ố
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
db (dinh brush), dp (dinh pen): t ng ng thu c l p brush và l p pen. Tham ươ ộ ớ ứ ớ
bi n này dùng đ xác đ nh giá tr màu cho vi n và màu tô cho đ nh. ị ế ể ề ị ỉ
lb (line brush), lp (line pen): t ng ng thu c l p brush và l p pen. Tham ươ ộ ớ ứ ớ
bi n này dùng đ xác đ nh giá tr màu cho đo n th ng và màu mũi tên. ế ể ạ ẳ ị ị
3.2.3 – Th t c v toàn b đ th ộ ồ ị
ủ ụ ẽ
ề Th t c này dùng đ v toàn b đ th v i màu ban đ u (ta coi màu tr ng, vi n ộ ồ ị ớ ể ẽ ủ ụ ầ ắ
xanh, đ ng n i màu xám là các màu ban đ u c a đ th ). ườ ầ ủ ồ ị ố
Cách nghĩ c a th t c này là: ủ ụ ủ
Ki m tra xem đ th có r ng hay không. N u r ng thì l nh return đ ế ỗ ồ ị ể ệ ỗ ượ ự c th c
hi n.ệ
N u đ th không r ng, duy t t ồ ị ệ ấ ả ớ t c các đ nh thu c danh sách đ nh, ng v i ứ ế ỗ ộ ỉ ỉ
m i đ nh, v mũi tên n i đ nh đó v i các con c a nó. V trí các đ nh con trong ỗ ỉ ố ỉ ủ ẽ ớ ị ỉ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
20
L p ĐHCQ K6B
ớ
danh sách đ ượ c tìm qua th t c pSearch. ủ ụ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
3.2.4 – Các th t c khác
ủ ụ
Ngoài các th t c nêu trên thì trong module này còn hai th t c ủ ụ ủ ụ
clearPanel: dùng đ xóa panel v (s d ng khi nh n nút [đ th m i] và khi ẽ ử ụ ồ ị ớ ể ấ
nh n nút [m đ th ], đi u ki n c a m đ th là ph i m thành công thì th ở ồ ị ở ồ ị ệ ủ ề ả ấ ở ủ
t c này m i th c hi n) ớ ụ ự ệ
coloredDraw: dùng đ v m t đ th v i m t màu khác, ch c n truy n tham ể ẽ ộ ồ ị ớ ỉ ầ ề ộ
s màu cho th t c n i đ nh ố ố ỉ ủ ụ ở ụ ử ụ m c 3.2.2. Trong th t c này có s d ng ủ ụ
vòng l p đ l y giá tr kho ng cách t thu c tính childs. ể ấ ả ặ ị ừ ộ
3.3 – Các th t c và hàm h tr
ủ ụ
ỗ ợ
Các th t c và hàm h tr này đ c đ nh nghĩa trong Module functions.vb và đa s ỗ ợ ủ ụ ượ ị ố
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
21
L p ĐHCQ K6B
ớ
có ph m vi public đ có th s d ng m i n i trong ch ể ử ụ ể ạ ở ọ ơ ươ ồ ng trình. Nó cũng bao g m
Đ 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 hàm và th t c có ph m vi private nh ng ch dùng đ ph c v cho các hàm và th ư ể ụ ụ ủ ụ ạ ỉ ủ
t c trong module. ụ
3.3.1 – Xóa đ nhỉ
T t ng c a thu t toán xóa đ nh r t đ n gi n. Đ u tiên tìm đ nh con c a nó và ư ưở ấ ơ ủ ủ ầ ả ậ ỉ ỉ
t ươ ứ ộ ng ng v i m i con, lo i b giá tr trùng v i giá tr tên c a đ nh c n xóa trong thu c ớ ạ ỏ ủ ỉ ầ ỗ ớ ị ị
tính đ nh cha (parents). T ng t ỉ ươ ự , tìm đ nh cha c a đ nh c n xóa và t ủ ỉ ầ ỉ ươ ứ ỗ ng ng v i m i ớ
cha, lo i b thành ph n trùng v i tên đ nh c n xóa trong thu c tính đ nh con (childs). ạ ỏ ầ ầ ớ ộ ỉ ỉ
c xóa, các Giá tr tr v c a hàm này là m t danh sách các đ nh v i đ nh đã đ ộ ị ả ề ủ ớ ỉ ỉ ượ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
22
L p ĐHCQ K6B
ớ
thu c tính c a các đ nh liên quan đ n đ nh đó cũng b xóa. ủ ế ộ ỉ ị ỉ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Tham bi n truy n vào c a hàm này là m t đ nh thu c l p lopDinh và m t danh sách ộ ỉ ộ ớ ủ ế ề ộ
các đ nh. ỉ
3.3.2 – Đ a d li u vào b ng k t qu
ư ữ ệ
ế
ả
ả
B ng k t qu n m trên Form process.vb và trong form này có m t control là ả ằ ế ả ộ
ListView1. Listview này có 4 sub item (ta coi nó là 4 c t). T ng ng chúng ta đã đ nh ộ ươ ứ ị
nghĩa m t l p listItem g m 4 thành ph n, và khai báo danh sách đ i t ộ ớ ố ượ ầ ồ ộ ớ ng thu c l p
đó. Do v y ng trong danh ậ ở đây ch vi c thêm các giá tr c a thu c tính c a m i đ i t ị ủ ỗ ố ượ ỉ ệ ủ ộ
sách vào trong ListView1. Công vi c c a th t c này có th đ ệ ủ ủ ụ ể ượ ố c hi u đ n gi n gi ng ể ả ơ
nh là thêm m t b n ghi vào m t b ng. ộ ả ộ ả ư
3.3.3 – Các th t c và hàm khác ủ ụ
Các th t c và hàm này cũng có t ng và thu t toán r t đ n gi n. ủ ụ t ư ưở ấ ơ ả ậ
Hàm thêm m t đ nh m i: Ki m tra xem đ nh đó đã có trong danh sách ch a, ư ộ ỉ ể ớ ỉ
ng t v i các hàm thêm n u có thì tr v false, và ch a thì tr v true. T ế ả ề ả ề ư ươ ự ớ
đ nh cha, thêm đ nh con. Ch khác là 2 hàm này thêm giá tr vào thu c tính ỉ ộ ỉ ỉ ị
c a m t đ nh ch không ph i thêm đ nh. ủ ộ ỉ ứ ả ỉ
c: Hàm này s tr v giá tr là v trí c a đ nh Hàm tìm đ nh có tên cho tr ỉ ướ ẽ ả ề ủ ỉ ị ị
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
23
L p ĐHCQ K6B
ớ
trong danh sách đ nh n u tìm đ c và tr v -1 n u không tìm đ c. T ế ỉ ượ ả ề ế ượ ư
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
ng ch là so sánh tên v i tên c a t t ưở ủ ấ ả t c các đ nh thu c danh sách đ nh, ộ ớ ỉ ỉ ỉ
n u tên trùng, có nghĩa là đã có đ nh đó. ế ỉ
Hàm xóa m t ký t ộ ự trong xâu: Ki m tra v trí ký t ể ị ự ầ ầ c n xóa, l y các ph n ấ
còn l i c a xâu mà không bao g m ký t đó, gán tr l i cho xâu cũ. Giá tr ạ ủ ồ ự ở ạ ị
tr v là m t xâu đã xóa ký t c n xóa. Hàm này dùng đ xóa tên đ nh cha ả ề ộ ự ầ ể ỉ
trong thu c tính parents c a m t đ nh và nó ph c v cho hàm xóa đ nh. ụ ụ ộ ỉ ủ ộ ỉ
Hàm s p x p danh sách L: S p x p danh sách L theo thu t toán s p x p n i ổ ế ế ế ắ ậ ắ ắ
b t.ọ
Th t c xóa tr ng các textbox: dùng đ xóa textbox khi c n thi t. ủ ụ ể ầ ắ ế
3.4 – mainForm – Form chính c a ch
ng trình
ủ
ươ
3.4.1 – Các khai báo
Trong Form này, khai báo 3 danh sách bao g m:ồ
dinh: danh sách các đ i t ố ượ ủ ng thu c l p lopDinh. Đây là danh sách chính c a ộ ớ
ch ng trình. ươ
Dlist: danh sách các đ i t ng thu c l p lopDinh. Dùng đ l u danh sách L ố ượ ộ ớ ể ư
(danh sách th c s ) và l u danh sách k t qu . Khi tìm ki m thành công, nó ự ự ư ế ế ả
đ c xóa đi và s đ c dùng l ng đi. ượ ẽ ượ ạ ể ư i đ l u các đ nh n m trên đ ỉ ằ ườ
ng thu c l p listItem, danh sách này đ resultList: m t danh sách đ i t ộ ố ượ ộ ớ ượ c
s d ng đ l u k t qu tìm ki m khi tìm ki m thành công. Ph m vi public ử ụ ể ư ế ế ế ả ạ
đ có th s d ng khi đ nh nghĩa th t c đ a d li u vào b ng k t qu ể ể ử ụ ữ ệ ủ ụ ư ế ả ị ả
(m c 3.3.2). ụ
3.4.2 – Nh p d li u vào
ữ ệ
ậ
Vi c nh p d li u vào đ ậ ữ ệ ệ ượ ư ấ c thông qua các th t c ki m soát các s ki n nh b m ự ệ ủ ụ ể
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
24
L p ĐHCQ K6B
ớ
chu t, nh n nút… ấ ộ
Đ 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 th t c nh p nh v m t đ nh b ng chu t, v đ nh b ng nút, nh p đ nh cha, ư ẽ ộ ỉ ủ ụ ẽ ỉ ằ ậ ằ ậ ộ ỉ
đ nh con, nh p đ nh đ u, đ nh cu i (đ v đ ầ ỉ ể ẽ ườ ậ ố ỉ ỉ ộ ng mũi tên n i hai đ nh) đ u có m t ề ố ỉ
i có th x y ra, khi có l đo n l nh đ u đ b t các l ầ ạ ệ ể ắ ỗ ể ả ỗ i thì s có m t b ng thông báo l ộ ả ẽ ỗ i
c th c hi n. đây t (messageBox) hi n lên và ti p sau đó câu l nh return s đ ế ẽ ượ ệ ệ ệ Ở ự ấ ả t c
các th t c nh p đ u có ki m tra l ng trình ủ ụ ể ề ậ ỗ i và l nh return s đ a quá trình ch y ch ẽ ư ệ ạ ươ
c kích ho t. N u l nh return đ v tr ng thái mà th t c ch a nó ch a đ ủ ụ ề ạ ứ ư ượ ế ệ ạ ượ ự c th c
hi n thì các l nh sau nó s không đ c th c hi n. ẽ ệ ệ ượ ự ệ
ử ụ V đ nh b ng chu t th c ch t là m t s ki n click chu t trên panel v . Ta s d ng ộ ự ệ ẽ ỉ ự ẽ ấ ằ ộ ộ
ng s ki n e và 2 thu c tính c a nó là x và y đ l y t a đ click chu t. T a đ đ i t ố ượ ể ấ ọ ộ ự ệ ọ ộ ủ ộ ộ
này s đ c l u vào thu c tính c a m t đ i t ng đ nh thu c danh sách các đ i t ẽ ượ ư ộ ố ượ ủ ộ ố ượ ng ộ ỉ
đ nh (dinh) thu c l p lopDinh khi không có l ỉ ộ ớ ỗ i nào x y ra. Hai l nh đ u tiên (sau các ệ ầ ả
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
25
L p ĐHCQ K6B
ớ
l nh khai báo) s hi n th giá tr t a đ click chu t ra 2 ô textbox đ ti n theo dõi. ệ ị ọ ộ ẽ ể ể ệ ộ ị
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Khi đã nh p đ y đ các d ki n, thì m t đ nh s đ c v ra panel v thông qua ữ ệ ộ ỉ ẽ ượ ủ ầ ậ ẽ ẽ
th t c drawDinh đ c đ nh nghĩa trong module draw.vb. Th t c này s đ c g i khi ủ ụ ượ ị ủ ụ ẽ ượ ọ
click chu t trên panel v ho c b m nút v đ nh. Các giá tr s đ ặ ấ ị ẽ ượ ư ộ c l u vào các thu c ẽ ỉ ẽ ộ
tính t ng này thu c l p lopDinh) và thêm vào danh ươ ứ ng ng c a m t đ nh t m (đ i t ộ ỉ ố ượ ủ ạ ộ ớ
ộ sách dinh thông qua th t c có s n (add) c a ki u danh sách (list (of T)). Khi thêm m t ủ ủ ụ ể ẵ
ng đ nh vào danh sách thì hàm ki m tra thêm đ nh m i s đ c g i (hàm này đ i t ố ượ ớ ẽ ượ ể ỉ ỉ ọ
i trong danh sách thì ta l đ nh nghĩa trong module functions.vb). N u đ nh đó đã t n t ị ồ ạ ế ỉ ạ i
c khi th s d ng messageBox đ báo l ử ụ ể ỗ i và m t l nh return đ quay v tr ng thái tr ể ề ạ ộ ệ ướ ủ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
26
L p ĐHCQ K6B
ớ
c kích ho t… t c đ ụ ượ ạ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Nút v đ th có ch c năng v mũi tên n i 2 đ nh, và nó s g i đ n th t c v mũi ố ẽ ọ ế ủ ụ ẽ ẽ ồ ị ứ ẽ ỉ
tên (dconnect) trong module draw.vb. T t ng c a nó ch là: tìm v trí đ nh cha và đ nh ư ưở ủ ỉ ị ỉ ỉ
con (tên c a hai đ nh này đ bàn phím) thông qua th t c pSearch ủ ỉ ượ c nh p t ậ ừ ủ ụ
c thêm vào m t đ i t (functions.vb). Sau đó thu c tính c a đ nh cha s đ ộ ủ ỉ ẽ ượ ộ ố ượ ộ ng thu c
l p Child t ớ ươ ứ ủ ng ng v i tên đ nh con v a nh p, và thu c tính parents (ki u String) c a ừ ể ậ ớ ộ ỉ
c thêm vào m t ký t t đ nh con cũng đ ỉ ượ ộ ự ươ ứ ố ng ng v i tên đ nh cha v a nh p. Các đ i ừ ậ ớ ỉ
ng đ nh cha, đ nh con (thu c l p lopDinh), giá tr kho ng cách, và các giá tr màu tô, t ượ ộ ớ ả ị ỉ ỉ ị
màu v s đ c dùng làm tham bi n th c s khi g i đ n th t c v mũi tên (dconnect ẽ ẽ ượ ủ ụ ẽ ự ự ọ ế ế
trong module draw.vb).
Khi nh n nút v đ th , các hàm ki m tra s đ c g i đ ki m tra xem đ nh cha, ẽ ồ ị ẽ ượ ể ấ ọ ể ể ỉ
đ nh con có t n t ỉ ồ ạ ồ i trong đ th hay không. N u m t trong hai, ho c c hai không t n ộ ặ ả ồ ị ế
i. Các hàm ki m tra (addChild, addParent) đ c đ nh nghĩa trong module t ạ i thì s báo l ẽ ỗ ể ượ ị
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
27
L p ĐHCQ K6B
ớ
funtions.vb.
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
V i nút b t đ u tìm ki m, s d ng hàm pSearch đ tìm v trí đ nh trong danh sách ắ ầ ử ụ ế ể ớ ị ỉ
các đ i t ng đ nh. Sau khi tìm đ c v trí hai đ nh đó (t ố ượ ỉ ượ ỉ ị ươ ng ng v i tên đ nh đ ớ ứ ỉ ượ c
nh p t bàn phím) thì th t c astar s đ ậ ừ ủ ụ ẽ ượ ế c g i v i hai đ nh truy n vào là tham bi n ọ ớ ề ỉ
th c s . Khi nút này đ c nh n thì ngoài các th t c và hàm nói trên đ c kích ho t thì ự ự ượ ủ ụ ấ ượ ạ
còn có thêm m t th t c khác n a đ c g i, đó là drawAll đ v l i đ th v i màu ủ ụ ữ ượ ộ ể ẽ ạ ồ ị ớ ọ
ban đ u. Th t c này đ c g i ra c đó mà có ủ ụ ầ ượ ọ ở đây đ n u có ti n hành tìm ki m tr ế ể ế ế ướ
k t qu tìm ki m thành công thì nó s đ a cách hi n th c a đ th v tr ng thái ban ế ị ủ ồ ị ề ạ ẽ ư ể ế ả
đ u đ sau đó ti n hành tìm ki m l n ti p theo. ầ ế ế ể ế ầ
3.4.3 – Th t c astar – th t c th hi n thu t toán A* ủ ụ
ể ệ
ủ ụ
ậ
Trong th t c này ta khai báo 2 đ i t ng là: ủ ụ ố ượ
Dtemp: thu c l p đ nh, coi là m t đ nh t m đ s d ng trong các l nh ti p ế ể ử ụ ộ ớ ộ ỉ ệ ạ ỉ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
28
L p ĐHCQ K6B
ớ
theo.
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
ng này đ itemTemp: thu c l p listItem, đ i t ộ ớ ố ượ ượ ữ ệ c dùng đ đ a các d li u ể ư
vào danh sách k t qu (resultList). ế ả
Đo n l nh trên dùng đ kh i t o các giá tr ban đ u cho các đ i t ạ ệ ở ạ ố ượ ể ầ ị ế ng và các bi n.
Trong đó:
m: s l n l p ố ầ ặ
txtResult: textbox trên mainForm, dùng đ th hi n k t qu . ả ể ể ệ ế
resultList.Add: Thêm m t đ i t ộ ố ượ ng vào danh sách k t qu (danh sách này ế ả
dung đ đ a k t qu ra b ng k t qu ), ban đ u danh sách k t qu có các ả ể ư ế ế ế ả ả ầ ả
ầ thu c tính ch a giá tr l n l p = 0 và u, v = r ng, thu c tính L ch a đ nh đ u ị ầ ặ ứ ỉ ứ ộ ỗ ộ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
29
L p ĐHCQ K6B
ớ
(tên đ nh và các giá tr hàm f, g đã chuy n sang ki u string). ể ể ị ỉ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Dlist.Add: Thêm đ nh đ u vào danh sách k t qu th c s (danh sách này ả ự ự ế ầ ỉ
dùng đ v đ th v i màu khác và đ thêm các giá tr vào resultList). ể ẽ ồ ị ớ ể ị
Thu c tính f c a đ nh đ c kh i t o giá tr b ng v i giá tr hàm đánh giá c a đ nh ủ ỉ ộ ượ ủ ỉ ở ạ ị ằ ớ ị
đó, vì đ nh đ u có giá tr hàm g = 0. ầ ị ỉ
Gi ng nh t t ư ư ưở ố ứ ng thu t toán thì ban đ u s l n l p = 0, u, v r ng, và L ch a ầ ố ầ ặ ậ ỗ
tr ng thái đ u tiên. Đo n l nh trên th hi n đ y đ đi u này. ầ ủ ề ể ệ ạ ệ ạ ầ
B t đ u vào thân vòng l p thì ta s s d ng l p vô t n khi đi u ki n l p luôn ẽ ử ụ ắ ầ ệ ặ ề ậ ặ ặ
đúng, vòng l p s d ng t ặ ẽ ừ ươ ằ ng ng v i các đi u ki n d ng c a thu t toán A* b ng ừ ủ ứ ệ ề ậ ớ
l nh return. ệ
Ban đ u ki m tra xem danh sách L có r ng hay không (Dlist), n u không r ng thì ỗ ế ể ầ ỗ
đ u c a danh sách L ra, ta s x lý nó đo n l nh sau. l y ph n t ấ ầ ử ầ ẽ ử ủ ở ạ ệ Ở ử đây x lý
tr ng h p khi danh sách L r ng (Dlist.Count = 0) thì thông báo tìm ki m th t b i ra ườ ấ ạ ế ợ ỗ
màn hình, t ng ng các control textbox và danh sách c a b ng k t qu cũng thêm các ươ ứ ủ ả ế ả
giá tr th hi n tìm ki m. Sau đó l nh return s đ ị ể ệ ẽ ượ ế ệ ư c th c hi n, thoát vòng l p và đ a ự ệ ặ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
30
L p ĐHCQ K6B
ớ
ch ươ ng trình tr v tr ng thái tr ở ề ạ ướ c khi th t c này đ ủ ụ ượ c kích ho t ạ
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Đo n l nh sau x lý tr ạ ệ ử ườ ng h p tìm ki m thành công, ế ợ ở ể ệ dòng đ u c a nó th hi n ầ ủ
đ u trong danh sách L. L nh này t ng ng v i b vi c lo i b m t ph n t ạ ỏ ộ ầ ử ầ ệ ệ ươ ớ ướ ứ ạ c lo i
b trong thu t toán. ỏ ậ
Ki m tra n u tên đ nh u (Dtemp) trùng v i tên đ nh k t thúc thì d ng thu t toán, ớ ừ ế ể ế ậ ỉ ỉ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
31
L p ĐHCQ K6B
ớ
c khi th c s d ng thì các k t qu , các x lý s đ c l p trình tr c. nh ng tr ư ướ ự ự ừ ẽ ượ ậ ử ế ả ướ
Đ 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 x lý và k t qu này dùng đ thông báo k t qu tìm ki m ra màn hình. Các ử ế ể ế ế ả ả
bi n đ c khai báo: ế ượ
Bi n resultPath ki u String đ l u chu i th hi n đ ng đi ể ệ ườ ể ư ế ể ỗ
Bi n Vtemp ki u String đ l u thu c tính v c a list k t qu (resultList) ể ư ủ ế ể ế ả ộ
Bi n Utemp ki u String đ l u thu c tính u c a list k t qu . ả ể ư ủ ế ể ế ộ
Bi n p ki u Short đ làm ch s l p cho vòng l p, ban đ u đ c gán = m ỉ ố ặ ế ể ể ặ ầ ượ
(s l n l p khi tìm ki m thành công) ố ầ ặ ế
Khi tìm ki m thành công thì Dlist s b xóa, và đ c dùng l ẽ ị ế ượ ạ ể ư ằ i đ l u các đ nh n m ỉ
trên đ ng đi, các đ nh này đ ườ ỉ ượ ấ c l y thông qua tên ch a trong danh sách k t qu ứ ế ả
(t ng ng v i cách l y đ ng đi t ươ ứ ấ ườ ớ d ừ ướ i lên trên b ng k t qu trong thu t toán A*). ả ế ả ậ
V l ẽ ạ i Dlist v i màu khác, đây chính là đ th k t qu . Ta v ra màn hình v i màu ồ ị ế ẽ ả ớ ớ
khác đ th hi n đ ng đi. ể ể ệ ườ
ầ Đo n l nh cu i trong th t c này th hi n các x lý c a thu t toán A*. Ban đ u ể ệ ạ ệ ủ ụ ử ủ ậ ố
tính l i các giá tr f và g cho các đ nh đ ạ ị ỉ ượ ố c phát tri n, sau khi tính xong thì đ a đ i ư ể
ng đ nh đó vào danh sách L (danh sách Dlist). đây ngoài đ i t ng dinhTemp là t ượ ỉ Ở ố ượ
đ i t ố ượ ộ ng t m dùng đ làm trung gian khi tính các giá tr f, g thì còn s d ng thêm m t ử ụ ể ạ ị
ng t m dinh4Add thu c l p lopDinh dùng đ thêm đ nh đã tính l đ i t ố ượ ộ ớ ể ạ ỉ ạ i f, g v i các ớ
thu c tính c n thi t vào trong danh sách Dlist. Vì trong thân vòng l p for, m i l n tính ầ ộ ế ỗ ầ ặ
i f, g thì dinhTemp l i có m t giá tr khác nhau, n u thêm th ng đ nh này vào danh l ạ ạ ế ẳ ộ ị ỉ
sách Dlist thì l n phát tri n khác, v i m t đ nh đ ở ầ ộ ỉ ể ớ ượ ế c sinh ra trùng v i đ nh cũ, n u ớ ỉ
Dlist đã ch a đ nh trùng v i đ nh v a sinh ra thì các giá tr f, g c a các đ nh này s trùng ứ ỉ ớ ỉ ừ ủ ẽ ị ỉ
nhau, và nh v y không đúng v i thu t toán. ư ậ ậ ớ
Sau khi tính toán các giá tr này thì thu c tính u, v, L t ị ộ ươ ng ng c a b ng k t qu ủ ả ứ ế ả
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
32
L p ĐHCQ K6B
ớ
i (sau khi các giá tr thu c tính đó đã chuy n sang ki u String). s l u l ẽ ư ạ ể ể ộ ị
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
Sau khi tính toán và thêm các đ i t ng đ nh vào trong danh sách Dlist thì danh sách ố ượ ỉ
này s đ c s p x p l i nh hàm Lsort. Dlist đ c s p x p và gán tr l i cho chính ẽ ượ ắ ế ạ ờ ượ ắ ở ạ ế
nó.
Ta t ng tóm t t các đo n l nh c a th t c này nh sau: ổ ắ ạ ệ ủ ụ ủ ư
Kh i t o danh sách L ch a tr ng thái đ u tiên, các danh sách c a b ng k t ế ủ ả ở ạ ứ ạ ầ
qu , các đ i t ng trung gian, các bi n kh i t o giá tr ban đ u… ố ượ ả ở ạ ế ầ ị
B t đ u thân vòng l p, x lý các tr ắ ầ ử ặ ườ ng h p k t thúc c a thu t toán. Hai ủ ế ậ ợ
tr ng h p k t thúc đ c x lý và đ a k t qu ra màn hình. ườ ợ ế ượ ử ư ế ả
Ph n l p chính c a thu t toán, tính các giá tr f, g cho các đ nh đ c phát ầ ặ ủ ậ ị ỉ ượ
tri n, và l u các giá tr này vào các đ i t ng, các bi n c n thi t đ đ a ra ố ượ ư ể ị ế ầ ế ể ư
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
33
L p ĐHCQ K6B
ớ
b ng k t qu ả ế ả
Đ tài: Xây d ng ch
ự
ề
ươ
ng trình minh h a thu t toán A* ọ
ậ
GVHD: Nông Th Hoa
ị
K T LU N
Ậ
Ế
Thu t toán tìm ki m t i u nói chung và Thu t toán tìm ki m A* nói riêng là ế ậ ố ư ế ậ
thu t toán mang tính ng d ng th c t cao, đ c bi t là trong l p k ho ch và h c máy. ự ế ụ ứ ậ ặ ệ ế ạ ậ ọ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
34
L p ĐHCQ K6B
ớ
Qua vi c th c hi n bài t p l n này, em đã có thêm ki n th c đ y đ và sâu s c h n v ứ ầ ủ ắ ơ ậ ớ ự ệ ế ệ ề
Đ 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 thu t toán tìm ki m nói chung và Thu t toán tìm ki m A* nói riêng. Ngoài ra, ế ậ ế ậ
chúng em cũng có c h i tìm hi u thêm v ngôn ng l p trình Visual Basic và công c ề ơ ộ ữ ậ ể ụ
l p trình Microsoft Visual Basic… ậ
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 nh ng ki n th c đã h c, em đã hoàn thành bài t p l n này. Tuy nhiên có ớ ậ ớ ữ ự ứ ế ọ
ng pháp v n ch a th c s t th ph ể ươ ự ự ố ư ự ỉ ả i u và còn nhi u sai sót, r t mong s ch b o ư ề ấ ẫ
Sinh viên th c hi n: Ngô Hoàng Liêm
ự
ệ
35
L p ĐHCQ K6B
ớ
c hoàn thi n h n. c a các th y cô và các b n đ đ tài c a em đ ủ ể ề ủ ạ ầ ượ ệ ơ
