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 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 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 c!a ph"n m m c#ng như ng
d ng 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 t i ư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
m&t 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
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, i n 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à n2-1
ô ch a các s trong ph m vi [1, n2-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 ó. M0i tr ng thái c!a b ng s
là m&t hoán v1 c!a n2 ph"n t . 2 ây ta có th m/ r&ng b(ng vi c thêm hình nh
vào game ho c g3n s vào hình nh g i ý cho ngư$i chơi. 2 tr ng thái ban
"u, các ô ư c s3p 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 t ng 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 1nh ch4 các ô tr ng di chuy n trong b ng là di chuy n n các v1 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
1.1.1: Tr ng thái b3t "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
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 % th1.
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 i u ki n ích). Thu t toán này s d ng m&t ánh giá
heuristic x p lo i t-ng 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- i m 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ó ch4 xây d ng các tuy n ư$ng có v5 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
m&t hàm ánh giá heuristic v kho ng cách t- i m b t k6 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 -
m&t ánh giá x y x4 thư$ng dùng cho kho ng cách c!a ư$ng giao thông.
i m khác bi t c!a A* i v i tìm ki m theo l a ch+n t t nh t là nó còn
tính n kho ng cách ã i qua. i u ó làm cho A* "y ! và t i ưu, ngh7a là
A* s' luôn tìm th y ư$ng i ng3n 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
m&t 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 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 n0 t i
n). Ta xác 1nh hàm ánh giá: f(n) = g(n) + h(n)
• g(n) là chi phí t- nút g c n0 t i 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
M&t ư c lư ng heuristic h(n) ư c xem là ch p nh n ư c n u v i m+i nút n: 0 8 h(n) 8 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
m i ư 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 ni trong OPEN bên c nh vi c lưu tr* 3 giá tr1 cơ
b n g, h, f ph9n á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 ni (ký hi u Cha(ni)): cho bi t tr ng thái d.n n tr ng thái ni.
• Danh sách các tr ng thái ti p theo c!a ni: danh sách này lưu tr* các tr ng
thái k ti p nk c!a ni sao cho chi phí n nk thông qua ni 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
m t 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 Thu t toán A*: function Astar(n0, ngoal) 1. t OPEN ch4 ch n0. t g(n0) = h(n0) = f(n0) = 0. t CLOSE là t p r0ng
2. L p l i các bư c sau cho n khi g p i u ki n d-ng
2.a N u OPEN r0ng: bài toán vô nghi m, thoát.
2.b Ngư c l i, ch+n ni trong OPEN sao cho f(ni) sao cho f(ni)min
2.b.1 L y ni ra kh)i OPEN và ưa ni vào CLOSE
2.b.2 N u ni chính là ích ngoal thì thoát và thông báo l$i gi i là ni
2.b.3 N u ni 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 ni. G+i m&t tr ng thái này là nk. V i m0i nk, làm các bư c sau:
2.b.3.1 Tính g(nk) = g(ni) + cost(ni, nk); h(nk); f(nk) = g(nk) + h(nk). 2.b.3.2 t Cha(nk) = ni
2.b.3.3 N u nk chưa xu t hi n trong OPEN và CLOSE thì thêm nk vào OPEN 8 III- CÀI T BÀI TOÁN
1. Tr ng thái xu t phát
R t d th y m0i tr ng thái c!a b ng s là m&t hoán v1 c!a n2 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à n2!, 8-puzzle là 9! =
362880(n = 3) và 15-puzzle là 16! = 20922789888000(n = 4),…. Khi m t ng lên
1 ơn v1 thì không gian tr ng thái s' t ng lên r t nhanh, i u 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 v1 c!a n2 ph"n t trong o n (0; n2-1).
V i 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 b3t "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 c#ng gi ng như ph"n trên ã nêu:
• FRINGE là t p ch a các tr ng thái ã ư c sinh ra nhưng chưa ư c xét n.
• M là t p các tr ng thái ti p theo c!a tr ng thái ni 9
• KQ t p 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
i u 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 ni. Khi ó
ni có t i a 4 tr ng thái con, nhưng trong các tr ng thái con c!a ni có 1 tr ng thái
trùng v i tr ng thái cha c!a ni. Vì v y ta có th lo i b) tr ng thái này tránh
vi c xét l p. 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à
m&t 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. M0i 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' b1 c3t 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 c!a tr ng thái ban "u, và trong m0i 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 c3t t4a 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 Minh h a A* 1.1.4: Minh h+a A* 11
3. Hàm c l ng heuristic
3.1 Các hàm c l ng heuristic
3.1.1 heuristic1 = t,ng kho ng cách d1ch chuy n (;,<,=,>) ng3n nh t
d1ch chuy n các ô sai v v1 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 ô / v1 trí úng
+ rows, cols là t+a &(dòng và c&t) c!a ô / v1 trí sai + xd = |cols – col | + yd = |rows – row |
d = xd + yd là kho ng cách ng3n nh t di chuy n 1 ô v úng v1 trí h1 = d
Trong b ng s 3x3 trên, di chuy n ô s 8 v v1 trí úng c"n 1 l"n, di
chuy n ô s 1 v v1 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 v1
trí(v1 trí hi n t i và v1 trí úng)
- L y t+a & c!a ô s 1 / v1 trí hi n t i ta có: rows = 1, cols = 0
- L y t+a & ô s 1 / v1 trí úng : row = 1/3 = 0; cols = 1%3 = 1
- V y kho ng cách ng3n nh t di chuy n ô s 1 v v1 trí úng:
d1 = |rows – row | + |cols – 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 h1 = 1+0+2+1+1+0+1+1 = 7
3.1.2 heuristic2 = t,ng kho ng cách d1ch chuy n (;,<,=,>) ng3n nh t
d1ch chuy n các ô sai v v1 trí úng c!a nó c&ng thêm ch4 s ph t c p ô hàng
xóm v i nhau ang n(m ngư c v1 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 v1 trí c"n d1ch 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 v1 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
Xét 1 ô n(m sai v1 trí: d = |rows – row |2 + |cols – col |2 t d3 = ?d 13
h3 = d3 – [0.15*d3] + a 3.1.4 heuristic4
Xét 1 ô sai n(m sai v1 trí: d = |rows – row |2 + |cols – col |2 t d4 = ?d h4 = d4 + 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)
+ d34 = 8 + 4 + 1 + 1 + 1 + 1 + 5 + 1 = 22
+ heuristic3 = d34 – [0.15*d34] + 2 = 21 + heuristic4 = d34 + 2 = 24 14 III- K T QU 1- Giao di n Các l a ch+n Khung hình chính Khung so sánh k t qu 15 2- So sánh
V i tr ng thái b3t "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 T,ng s nút trên cây: 73742 Th$i gian gi i quy t: 38598ms 16 + heuristic2 S bư c th c hi n: 37 S nút ã xét: 25950 T,ng s nút trên cây: 52228 Th$i gian gi i quy t: 19370ms 17 + heuristic3: S bư c th c hi n: 37 S nút ã xét: 400 T,ng s nút trên cây: 809 Th$i gian gi i quy t: 17ms 18 + heuristic4 S bư c th c hi n: 41 S nút ã xét: 475 T,ng s nút trên cây: 939 Th$i gian gi i quy t: 20ms 19 Thu t toán IDA* + heuristic1 S bư c th c hi n: 37 S nút ã xét: 77849
T,ng 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 T,ng s nút trên cây: 97311 Th$i gian gi i quy t: 4081ms + heuristic3 S bư c th c hi n: 37 S nút ã xét: 404 T,ng 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 T,ng s nút trên cây: 9622 Th$i gian gi i quy t: 41ms 20