Thuật toán A* - Ứng dụng trong bài toán ghép tranh

Nội dung text: Thuật toán A* - Ứng dụng trong bài toán ghép tranh

1. TR NG I H C BÁCH KHOA HÀ N I VI N CÔNG NGH THÔNG TIN VÀ TRUY N THÔNG
   
    BÀI T P L N NH ẬP MÔN TRÍ TU Ệ NHÂN T ẠO Đề tài: THU ẬT TOÁN A* ỨNG D ỤNG TRONG BÀI TOÁN GHÉP TRANH Sinh viên th c hi n : Lê Đình C ường (Các thành viên khác) : Mã s sinh viên : 20080370 Nhóm: 3 HÀ N I 04-2013
2. MỤC L ỤC Lời nói đầu 3 I- BÀI TOÁN GHÉP TRANH 4 II- THU ẬT TOÁN A* 5 1- Gi i thi u thu t toán 5 2- Mô t thu t toán 7 3- Cài t thu t toán 7 III- CÀI ĐẶT BÀI TOÁN 9 1. Tr ng thái xu t phát 9 2. Cài t A* 9 3. Hàm ưc l ưng heuristic 12 3.1 Các hàm ưc l ưng heuristic 12 3.2 Ví d so sánh 3 hàm heuristic 14 III- KẾT QU Ả 15 1- Giao di n 15 2- So sánh 16 3- Nh n xét 21 IV- KẾT LU ẬN 22 Tài li ệu tham kh ảo 23 PHI ẾU GIAO NHI ỆM V Ụ BÀI T ẬP L ỚN Error! Bookmark not defined. 2
3. Lời nói đầ u ây là tài li u dùng bi u di n c ơ b n thi t k và gi i quy t bài toán “Trò ch ơi ghép tranh” s d ng thu t toán A* do tôi thi t k và l p trình. Tài li u này giúp ta có cái nhìn toàn v n v các ch c n ng ca ph n m m c ng nh ư ng dng thu t toán A* gi i quy t bài toán này. Do th i gian có h n nên án không th ti ưu ưc toàn b không gian tr ng thái bài toán. Tuy nhiên, nhóm s nghiên c u hoàn thi n trong th i gian s m nh t. Nhóm th c hi n tài nh m m c ích xây d ng m t h th ng gi i quy t mt bài toán th c t d a trên chi n l ưc tìm ki m heuristic và xây d ng m t trò ch ơi ng d ng gi i trí. Trong quá trình th c hi n tài không tránh kh i nh ng sai sót, nhóm tôi mong s nh n ưc s góp ý và ánh giá c a th y. Xin chân thành c ảm ơn ! 3
4. I- BÀI TOÁN GHÉP TRANH Game ghép tranh(N-Puzzle) là m t trò ch ơi khá hay và trí tu , nó ưc bi t n v i nhi u phiên b n và tên g i khác nhau nh ư: 8-puzzle, 15-puzzle, Gem puzzle, Boss puzzle. Bài toán N-puzzle là v n c in cho mô hình thu t toán liên quan n trí tu nhân t o. Bài toán t ra là ph i tìm ưng i t tr ng thái hi n t i t i tr ng thái ích. Và cho t i nay v n ch ưa có thu t toán t i ưu gi i bài toán này. Ph n m m N-Puzzle là m t ch ươ ng trình xây d ng trò ch ơi và gi i quy t bài toán này. Ph n m m ưc vi t trên n n Java, s d ng giao di n h a mô ph ng trò ch ơi và thu t toán A* tìm ưng i. Ng ưi dùng có th s d ng chu t/bàn phím ch ơi v i các kích th ưc khác nhau và v i hình nh khác nhau ho c có th s d ng ch c n ng tìm l i gi i nh thu t toán A*. Yêu c u xây d ng b ng ô vuông n hàng, n c t. B ng g m 1 ô tr ng và n 2-1 ô ch a các s trong ph m vi [1, n 2-1]. Xu t phát t m t cách x p b t kì, di chuy n ô tr ng lên trên, xu ng d ưi, sang ph i, sang trái ưa các ô v tr ng thái ích. S d ng chu t hay phím ch c n ng di chuy n ô tr ng. Ch ươ ng trình có ch c n ng t ng ch ơi b t kì tr ng thái nào ó. M i tr ng thái c a b ng s là m t hoán v c a n 2 ph n t . ây ta có th m r ng b ng vi c thêm hình nh vào game ho c g n s vào hình nh g i ý cho ng ưi ch ơi. tr ng thái ban u, các ô ưc s p x p ng u nhiên, và nhi m v c a ng ưi ch ơi là tìm ưc cách ư a chúng v tr ng thái ích(ô u tr ng, các ô khác theo th t tng d n t trái qua ph i, t trên xu ng d ưi). ơn gi n trong cách ti p c n bài toán, ta gi nh ch các ô tr ng di chuy n trong b ng là di chuy n n các v trí khác nhau. Nh ư v y t i m t tr ng thái b t kì có t i a 4 cách di chuy n n tr ng thái khác(trái, ph i, lên, xu ng). 4
5. 1.1.1: Tr ng thái b t u và ích Bưc di chuy n c a ô tr ng: 1.1.2: B ưc di chuy n c a ô tr ng II- THU ẬT TOÁN A* 1- Gi ới thi ệu thu ật toán Thu t toán A* ưc mô t l n u tiên n m 1986 b i Peter Hart, Nils Nilson và Bertram Raphael. Trong báo cáo c a h , thu t toán ưc g i là thu t 5
6. toán A, khi s d ng thu t toán này v i m t hàm ánh giá heuristic thích h p s thu ưc ho t ng t i ưu, do ó mà có tên là A*. Trong khoa h c máy tính, A* là m t thu t toán tìm ki m trong th . Thu t toán này tìm m t ưng i t nút kh i u t i m t nút ích cho tr ưc( ho c t i m t nút th a mãn iu ki n ích). Thu t toán này s d ng m t ánh giá heuristic x p lo i tng nút theo ưc l ưng v tuy n ưng t t nh t i qua nút ó. Thu t toán này duy t các nút theo th t c a ánh giá heuristic này. Do ó, thu t toán A* là m t ví d c a tìm ki m theo l a ch n t t nh t(best-first search). Xét bài toán tìm ưng – bài toán mà A* th ưng ưc dùng gi i. A* xây d ng t ng d n t t c các tuy n ưng t im xu t phát cho t i khi nó tìm th y m t ưng i ch m t i ích. Tuy nhiên, c ng nh ư t t c các thu t toán tìm ki m có thông tin nó ch xây d ng các tuy n ưng có v d n v ích. bi t nh ng tuy n ưng nào có kh n ng s d n t i ích, A* s d ng mt hàm ánh giá heuristic v kho ng cách t im b t k cho t i ích. Trong tr ưng h p tìm ưng i, ánh giá này có th là kho ng cách ưng chim bay - mt ánh giá x y x th ưng dùng cho kho ng cách c a ưng giao thông. im khác bi t c a A* i v i tìm kim theo l a ch n t t nh t là nó còn tính n kho ng cách ã i qua. iu ó làm cho A* y và t i ưu, ngh a là A* s luôn tìm th y ưng i ng n nh t n u t n t i m t ưng i nh ư th . A* không m b o s ch y nhanh h ơn các thu t toán tìm ki m ơn gi n hơn. Trong mt môi tr ưng d ng mê cung, cách duy nh t n ích có th là tr ưc h t ph i i v phía xa ích và cu i cùng m i quay tr l i. Trong tr ưng h p ó, vi c th các nút theo th t “g n ích h ơn thì ưc th tr ưc” có th gây t n th i gian. 6
7. 2- Mô t ả thu ật toán Gi s n là m t tr ng thái t t i(có ưng i t tr ng thái ban u n 0 ti n). Ta xác nh hàm ánh giá: f(n) = g(n) + h(n) • g(n) là chi phí t nút g c n 0 ti nút hi n t i n • h(n) chi phí ưc l ưng t nút hi n t i n t i ích • f(n) chi phí t ng th ưc l ưng c a ưng i qua nút hi n t i n n ích Mt ưc l ưng heuristic h(n) ưc xem là ch p nh n ưc n u v i m i nút n: 0 h(n) h*(n) Trong ó h*(n) là chi phí th t(th c t ) i t nút n n ích. 3- Cài đặt thu ật toán OPEN (FRINGE): t p ch a các tr ng thái ã ưc sinh ra nh ưng ch ưa ưc xét n. OPEN là m t hàng i ưu tiên mà trong ó ph n t có ưu tiên cao nh t là ph n t t t nh t. CLOSE : t p ch a các tr ng thái ã ưc xét n. Chúng ta c n l ưu tr nh ng tr ng thái này trong b nh phòng tr ưng h p khi có m t tr ng thái mi ưc t o ra l i trùng v i m t tr ng thái mà ta ã xét n tr ưc ó. Khi xét n m t tr ng thái n i trong OPEN bên c nh vi c l ưu tr 3 giá tr c ơ bn g, h, f ph n ánh t t c a tr ng thái ó, A* còn l ưu tr thêm hai thông s sau: • Tr ng thái cha c a tr ng thái n i (ký hi u Cha(n i)): cho bi t tr ng thái d n n tr ng thái n i. • Danh sách các tr ng thái ti p theo c a n i: danh sách này l ưu tr các tr ng thái k ti p n k ca n i sao cho chi phí n n k thông qua n i t tr ng thái ban u là th p nh t. Th c ch t danh sách này có th ưc tính t thu c tính Cha c a các tr ng thái ã ưc l ưu tr . Tuy nhiên vi c tính toán này có th mt nhi u th i gian(khi t p OPEN,CLOSE ưc m r ng) nên ng ưi ta th ưng l ưu tr ra m t danh sách riêng. 7
8. Thu ật toán A*: function Astar(n 0, n goal ) 1. t OPEN ch ch n 0. t g(n 0) = h(n 0) = f(n 0) = 0. t CLOSE là t p rng 2. Lp l i các b ưc sau cho n khi g p iu ki n d ng 2.a N u OPEN r ng: bài toán vô nghi m, thoát. 2.b Ng ưc l i, ch n n i trong OPEN sao cho f(n i) sao cho f(n i)min 2.b.1 L y ni ra kh i OPEN và ư a n i vào CLOSE 2.b.2 N u n i chính là ích ngoal thì thoát và thông báo l i gi i là n i 2.b.3 N u n i không ph i là ích. T o danh sách t t c các tr ng thái k ti p c a n i. G i m t tr ng thái này là n k. V i m i n k, làm các b ưc sau: 2.b.3.1 Tính g(n k) = g(n i) + cost(n i, n k); h(n k); f(n k) = g(n k) + h(n k). 2.b.3.2 t Cha(n k) = n i 2.b.3.3 N u n k ch ưa xu t hi n trong OPEN và CLOSE thì thêm n k vào OPEN 8
9. III- CÀI ĐẶT BÀI TOÁN 1. Tr ạng thái xu ất phát Rt d th y m i tr ng thái c a b ng s là m t hoán v c a n 2 ph n t ( v i n là kích th ưc c nh), nh ư v y không gian tr ng thái c a nó là n 2!, 8-puzzle là 9! = 362880(n = 3) và 15-puzzle là 16! = 20922789888000(n = 4), . Khi m t ng lên 1 ơ n v thì không gian tr ng thái s t ng lên r t nhanh, iu này khi n cho vi c gi i quy t v i các phiên b n n > 3 ít ưc áp d ng. t o ra m t tr ng thái ban u c a trò ch ơi ta dùng m ng 1 chi u và sinh ng u nhiên m t m ng tr ng thái là hoán v c a n 2 ph n t trong on (0; n 2-1). Vi vi c sinh ng u nhiên thì s t o ra nh ng tr ng thái không h p l (tr ng thái không d n t i tr ng thái ích c a bài toán), thì ta c n ph i ki m tra xem tr ng thái có d n t i ích ưc hay không tr ưc khi kh i t o giao di n. Ngoài ra ta có th tr n ng u nhiên tr ng thái ích n m t tr ng thái b t kì. 1 2 3 7 3 2 4 5 11 10 1 7 4 9 12 14 6 8 13 15 6 8 5 1.1.3: Tr ng thái b t u 15-puzzle và 8-puzzle 2. Cài đặt A* Vi c cài t thu t toán A* trong bài toán N-Puzzle cng gi ng nh ư ph n trên ã nêu: • FRINGE là tp ch a các tr ng thái ã ưc sinh ra nh ưng ch ưa ưc xét n. • M là tp các tr ng thái ti p theo c a tr ng thái n i 9
10. • KQ tp tr ng thái k t qu , l ưu các tr ng thái t tr ng thái hi n t i t i ích u vào: tr ng thái hi n t i, tr ng thái ích u ra: t p các tr ng thái t tr ng thái hi n t i t i tr ng thái ích iu ki n d ng thu t toán: tìm th y k t qu ho c gi i h n th i gian ho c ng ưi dùng cho phép d ng. Trong bài toán này ta có th c i ti n b ng vi c b t p CLOSE . Ta th y trong b ưc 2.b.3 trên sau khi tìm ra các tr ng thái con c a tr ng thái n i. Khi ó ni có t i a 4 tr ng thái con, nh ưng trong các tr ng thái con c a n i có 1 tr ng thái trùng v i tr ng thái cha c a n i. Vì v y ta có th lo i b tr ng thái này tránh vi c xét lp. Khi lo i b tr ng thái này s không t n t i m t tr ng thái con nào trùng v i m t tr ng thái trong t p CLOSE n a. Vi c lo i b này s tránh ưc vi c ki m tra b ưc 2.b.3.3 gây t n r t nhi u th i gian. Ngoài ra, trong game này còn cài t thêm thu t toán A* sâu d n(IDA*) là mt bi n th c a thu t toán tìm ki m A*. IDA* giúp lo i b h n ch b nh c a A* mà ko hy sinh gi i pháp t i ưu. M i l n l p c a thu t toán là quá trình tìm ki m theo chi u sâu, f(n) = g(n) + h(n), t o nút m i. Khi m t nút ưc t o ra có chi phí v ưt quá m t ng ưng cutoff thì nút ó s b c t gi m, quá trình tìm ki m backtracks tr ưc khi ti p t c. Các ng ưng chi phí ưc kh i t o ưc l ưng heuristic ca tr ng thái ban u, và trong m i l n l p k ti p làm t ng t ng chi phí c a các nút có chi phí th p ã ưc c t t a tr ưc ó. Thu t toán ch m d t khi tr ng thái ích có t ng chi phí không v ưt quá ng ưng hi n t i. 10
11. Minh h ọa A* 1.1.4: Minh h a A* 11
12. 3. Hàm ước l ượng heuristic 3.1 Các hàm ước l ượng heuristic 3.1.1 heuristic1 = tng kho ng cách d ch chuy n (,,,) ng n nh t dch chuy n các ô sai v v trí úng c a nó(kho ng cách Manhattan) 1.1.5: Minh h ọa Gi s: + row , col là t a (dòng và c t) c a ô v trí úng + row s, col s là t a (dòng và c t) c a ô v trí sai + xd = |col s – col | + yd = |row s – row |  d = xd + yd là kho ng cách ng n nh t di chuy n 1 ô v úng v trí  h1 = ∑d Trong b ng s 3x3 trên, di chuy n ô s 8 v v trí úng c n 1 l n, di chuy n ô s 1 v v trí úng c n 2 l n(qua 2 ô khác). thu ưc k t qu này ta làm phép tính ơ n gi n: l y t ng kho ng cách c a các dòng và c t gi a hai v trí(v trí hi n t i và v trí úng) - Ly t a ca ô s 1 v trí hi n t i ta có: row s = 1, col s = 0 - Ly t a ô s 1 v trí úng : row = 1/3 = 0; col s = 1%3 = 1 - Vy kho ng cách ng n nh t di chuy n ô s 1 v v trí úng: d1 = |row s – row đ| + |col s – col đ| = |1 – 0| + |0 – 1| = 2 Tươ ng t , tính t t c các kho ng cách d c a các ô sai còn l i ta ưc 12
13. h1 = 1+0+2+1+1+0+1+1 = 7 3.1.2 heuristic2 = tng kho ng cách d ch chuy n ( ,,,) ng n nh t dch chuy n các ô sai v v trí úng c a nó cng thêm ch s ph t cp ô hàng xóm v i nhau ang n m ng ưc v trí c a nhau. 1 2 2 1 3 4 5 6 7 5 6 7 8 3 8 4 1.1.6a: Đích 1.1.6b: Minh h ọa  h2 = ∑d + a Trong ó a là ch ỉ số ph ạt c ặp ô hàng xóm đang n ằm ng ược v ị trí . C p (2,1) mu n v úng v trí cn d ch chuy n ít nh t 4 b ưc(không ý t i các ô khác), 2 b ưc ã ưc tính trong d nên a = 2 . Vì v y trong 1.1.6b có 2 c p hàng xóm n m ng ưc v trí nên ây a = 2+2 = 4. 3.1.3 heuristic3 1 2 3 2 6 3 7 4 5 6 7 4 5 10 11 8 9 10 11 12 9 14 1 12 13 14 15 8 13 15 1.1.7a: Đích 1.1.7b: Minh h ọa 2 2 Xét 1 ô n m sai v trí: d = |row s – row | + |col s – col | t d 3 = d 13
14.  h3 = d3 – [0.15*d 3] + a 3.1.4 heuristic4 2 2 Xét 1 ô sai n m sai v trí: d = |row s – row | + |col s – col | t d 4 = d  h4 = d 4 + a 3.2 Ví d ụ so sánh 3 hàm heuristic 8 7 1 6 4 3 2 5 Xét tr ng thái hình trên + heuristic1 = 4 + 2 + 1 + 1 + 1 + 1 + 3 + 1 = 14 + heuristic2 = heuristic1 + 2 = 16 (a = 2) + d 34 = 8 + 4 + 1 + 1 + 1 + 1 + 5 + 1 = 22 + heuristic3 = d34 – [0.15*d 34 ] + 2 = 21 + heuristic4 = d34 + 2 = 24 14
15. III- KẾT QU Ả 1- Giao di ện Các l a ch n Khung hình Khung so sánh chính kt qu 15
16. 2- So sánh Vi tr ng thái b t u là tr ng thái hình trên:  Thu ật toán A* + heuristic 1: S bưc th c hi n: 37 S nút ã xét: 36819 Tng s nút trên cây: 73742 Th i gian gi i quy t: 38598ms 16
17. + heuristic2 S bưc th c hi n: 37 S nút ã xét: 25950 Tng s nút trên cây: 52228 Th i gian gi i quy t: 19370ms 17
18. + heuristic3: S bưc th c hi n: 37 S nút ã xét: 400 Tng s nút trên cây: 809 Th i gian gi i quy t: 17ms 18
19. + heuristic4 S bưc th c hi n: 41 S nút ã xét: 475 Tng s nút trên cây: 939 Th i gian gi i quy t: 20ms 19
20.  Thu ật toán IDA* + heuristic1 S bưc th c hi n: 37 S nút ã xét: 77849 Tng s nút trên cây: 156896 Th i gian gi i quy t: 9760ms + heuristic2 S bưc th c hi n: 37 S nút ã xét: 48304 Tng s nút trên cây: 97311 Th i gian gi i quy t: 4081ms + heuristic3 S bưc th c hin: 37 S nút ã xét: 404 Tng s nút trên cây: 811 Th i gian gi i quy t: 4ms + heuristic4 S bưc th c hi n: 43 S nút ã xét: 4834 Tng s nút trên cây: 9622 Th i gian gi i quy t: 41ms 20
21. 3- Nh ận xét - Ta th y heuristic2 = heuristic1 + a, nên h1(n) h2(n) h*(n). Hàm h2(n) giúp s nút duy t ít h ơn và th i gian duy t nhanh h ơn h1(n). Vì v y h2(n) hi u qu hơn h1(n). Hai hàm heuristic1 và heuristic2 t ra kém hi u qu khi kích th ưc tr ng thái c a bài toán t ng lên, d n n m t nhi u th i gian và t n b nh . Nguyên nhân là do ưc l ưng chi phí heuristic1 và heuristic2 quá nh so v i chi phí th c t h*(n). - Hàm heuristic3 là m t ưc l ưng chi phí khá t i ưu, không gian tr ng thái và th i duy t gi m i áng k so v i hai hàm ưc l ưng trên. Nguyên nhân là do hàm ưc l ưng chi phí heuristic3 h*(n) (g n v i chi phí th c t ). - Hàm heuristic4 c ng khá hi u qu v mt b nh và th i gian khi duy t, nh ưng heuristic4 không ư a ra ưng i t i ưu vì heuristic4 ưc l ưng chi phí ln h ơn chi phí th ưc t . Có th nói, trong 4 hàm ưc l ưng heuristic3 làm hàm hi u qu nh t. - Tính t i ưu c a thu t toán A* ph thu c nhi u vào hàm ưc l ưng h(n) và ch phù h p v i không gian tr ng thái nh . Nu không gian các tr ng thái là hu h n và có gi i pháp tránh vi c xét l p l i các tr ng thái thì gi i thu t A* là hoàn ch nh(tìm ưc l i gi i)- nh ưng ko m b o tính t i ưu. N u không có gi i pháp tránh vi c xét l p thì A* không hoàn ch nh(không m b o tìm ưc l i gi i). Nu không gian tr ng thái là vô hn thì gi i thu t A* là không hoàn ch nh(không m b o tìm ưc l i gi i). - IDA* hi u qu hơn A* v mt b nh và th i gian. Nói chung IDA* nhanh h ơn A*, nh ưng IDA* c ng không m b o tính t i ưu. - Trong bài toán này ta có th cân nh c gi a vi c tìm ưng i t i ưu nh ưng s mt nhi u th i gian v i vi c tìm ưng i không t i ưu v i th i gian nhanh h ơn. - Hàm heuristic3 tuy khá hi u qu nh ưng không m rng ưc v i m i không gian tr ng thái vì khi A* xét các nút thì ph i tính toán heuristic gây t n nhi u th i gian. Nhóm ang nghiên c u ph ươ ng pháp tính tr ưc các hàm heuristic nh ưng do th i gian có h n nên ch ưa th hoàn thành ưc. 21
22. IV- KẾT LU ẬN Thông qua vi c tìm hi u và nghiên c u tài này giúp chúng tôi có cái nhìn toàn di n h ơn trong vi c ng d ng trí tu nhân t o vào gi i quy t v n th c t . ây là bài toán c in trong trí tu nhân t o cho các thu t toán mô hình hóa liên quan n tìm ki m có tri th c b sung. tài ã ưc nhi u ng ưi nghiên c u gi i quy t, nh ưng cho n nay v n ch ưa có cách gi i quy t t i ưu cho t t c không gian tr ng thái trò ch ơi vì kích th ưc t ng không gian tr ng thái s tng lên r t nhanh. Hy v ng nh ng nghiên c u ánh giá c a chúng tôi s góp ph n b sung thêm m t h ưng gi i quy t cho bài toán. Do th i gian có h n nên tài không tránh kh i nh ng sai sót, mong th y góp ý, ánh giá giúp chúng tôi hoàn thi n tài. 22
23. Tài li ệu tham kh ảo - B th ư vi n chu n c a Sun MicroSystem - Bài gi ng Nh p môn trí tu nhân t o – Nguy n Nh t Quang - - - gi%E1%BA%A3i-bai-toan-n-puzzle/ Hà N ội, ngày 15 tháng 04 n ăm 2013 Tác gi BTL Lê Đình C ường 23