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À NI 04-

MC LC

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 bit n vi nhiu phiên bn và tên g+i khác nhau như: 8-puzzle, 15-puzzle, Gem puzzle, Boss puzzle. Bài toán N-puzzle là vn  c, in cho mô hình thut toán liên quan n trí tu nhân to. Bài toán t ra là phi tìm ư$ng i t- trng thái hi n ti ti trng thái ích. Và cho ti nay v chưa có thut toán t i ưu  gii bài toán này.

Ph"n mm N-Puzzle là m&t chương trình xây d ng trò chơi và gii quyt bài toán này. Ph"n mm ưc vit trên nn Java, s dng giao di n % h+a  mô ph]ng trò chơi và thut toán A*  tìm ư$ng i. Ngư$i dùng có th s dng chu&t/bàn phím chơi vi các kích thưc khác nhau và vi hình nh khác nhau hoc có th s dng chc n ng tìm l$i gii nh$ thut toán A*.

Yêu c"u xây d ng bng ô vuông n hàng, n c&t. Bng g%m 1 ô tr ng và n 2 - 1 ô cha các s trong phm vi [1, n 2 - 1]. Xut phát t- m&t cách xp bt kì, di chuyn ô tr ng lên trên, xu ng dưi, sang phi, sang trái  ưa các ô v trng thái ích. S dng chu&t hay phím chc n ng  di chuyn ô tr ng. Chương trình có chc n ng t &ng chơi / bt kì trng thái nào ó. M 0 i trng thái c!a bng s là m&t hoán v 1 c!a n 2 ph"n t. 2 ây ta có th m/ r&ng b[ng vi c thêm hình nh vào game hoc g 3 n s vào hình nh  gi ý cho ngư$i chơi. 2 trng thái ban "u, các ô ưc s 3 p xp ng nhiên, và nhi m v c!a ngư$i chơi là tìm ưc cách ưa chúng v trng thái ích[ô "u tr ng, các ô khác theo th t t ng d"n t- trái qua phi, t- trên xu ng dưi].  ơn gin trong cách tip cn bài toán, ta gi 1nh ch 4 các ô tr ng di chuyn trong bng là di chuyn n các v 1 trí khác nhau. Như vy ti m&t trng thái bt kì có t i a 4 cách di chuyn n trng thái khác[trái, phi, lên, xu ng].

1.1: Trng thái b 3 t "u và ích

Bưc di chuyn c!a ô tr ng:

1.1: Bưc di chuyn c!a ô tr ng

II- THU
T TOÁN A*

1- Gii thiu thut toán Thut 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+, thut toán ưc g+i là thut

2- Mô t thut toán Gi s n là m&t trng thái t ti[có ư$ng i t- trng thái ban "u n 0 ti 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 n 0 ti nút hi n ti n
• h[n] chi phí ưc lưng t- nút hi n ti n ti ích
• f[n] chi phí t,ng th ưc lưng c!a ư$ng i qua nút hi n ti n n ích M&t ưc lưng heuristic h[n] ưc xem là chp nhn ưc nu vi m+i nút n: 0 8 h[n] 8 h*[n]

Trong ó h*[n] là chi phí tht[th c t]  i t- nút n n ích.

3- Cài t thut toán OPEN[FRINGE]: tp cha các trng 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 nht là ph"n t t t nht.

CLOSE: tp cha các trng thái ã ưc xét n. Chúng ta c"n lưu tr* nh*ng trng thái này trong b& nh  phòng trư$ng hp khi có m&t trng thái mi ưc to ra li trùng vi m&t trng thái mà ta ã xét n trưc ó.

Khi xét n m&t trng thái ni trong OPEN bên cnh vi c lưu tr* 3 giá tr 1 cơ bn g, h, f  ph 9 n ánh & t t c!a trng thái ó, A* còn lưu tr* thêm hai thông s sau:

• Trng thái cha c!a trng thái ni [ký hi u Cha[ni]]: cho bit trng thái d n trng thái ni.
• Danh sách các trng thái tip theo c!a ni: danh sách này lưu tr* các trng thái k tip nk c!a ni sao cho chi phí n nk thông qua ni t- trng thái ban "u là thp nht. Th c cht danh sách này có th ưc tính t- thu&c tính Cha c!a các trng thái ã ưc lưu tr*. Tuy nhiên vi c tính toán này có th mt nhiu th$i gian[khi tp OPEN,CLOSE ưc m/ r&ng] nên ngư$i ta thư$ng lưu tr* ra m&t danh sách riêng.

Thut toán A*:

function Astar[n 0 , ngoal]

1. t OPEN ch 4 ch n 0. t g[n 0 ] = h[n 0 ] = f[n 0 ] = 0. t CLOSE là tp r 0 ng
2. Lp li các bưc sau cho n khi gp iu ki n d-ng 2 Nu OPEN r 0 ng: bài toán vô nghi m, thoát. 2 Ngưc li, ch+n ni trong OPEN sao cho f[ni] sao cho f[ni]min 2.b Ly ni ra kh]i OPEN và ưa ni vào CLOSE 2.b Nu ni chính là ích ngoal thì thoát và thông báo l$i gii là ni 2.b Nu ni không phi là ích. To danh sách tt c các trng thái k tip c!a ni. G+i m&t trng thái này là nk. Vi m 0 i nk, làm các bưc sau: 2.b.3 Tính g[nk] = g[ni] + cost[ni, nk]; h[nk]; f[nk] = g[nk] + h[nk]. 2.b.3 t Cha[nk] = ni 2.b.3 Nu nk chưa xut hi n trong OPEN và CLOSE thì thêm nk vào OPEN
3. KQ tp trng thái kt qu, lưu các trng thái t- trng thái hi n ti ti ích "u vào: trng thái hi n ti, trng thái ích "u ra: tp các trng thái t- trng thái hi n ti ti trng thái ích iu ki n d-ng thut toán: tìm thy kt qu hoc gii hn th$i gian hoc ngư$i dùng cho phép d-ng.

Trong bài toán này ta có th ci tin b[ng vi c b] tp CLOSE. Ta thy trong bưc 2.b / trên sau khi tìm ra các trng thái con c!a trng thái ni. Khi ó ni có t i a 4 trng thái con, nhưng trong các trng thái con c!a ni có 1 trng thái trùng vi trng thái cha c!a ni. Vì vy ta có th loi b] trng thái này  tránh vi c xét lp. Khi loi b] trng thái này s&

039; không t%n ti m&t trng thái con nào trùng vi m&t trng thái trong tp CLOSE n*a. Vi c loi b] này s&

039; tránh ưc vi c kim tra / bưc 2.b.3 gây t n rt nhiu th$i gian.

Ngoài ra, trong game này còn cài t thêm thut toán A* sâu d"n[IDA*] là m&t bin th c!a thut toán tìm kim A*. IDA* giúp loi b] hn ch b& nh c!a A* mà ko hy sinh gii pháp t i ưu. M 0 i l"n lp c!a thut toán là quá trình tìm kim theo chiu sâu, f[n] = g[n] + h[n], to nút mi. Khi m&t nút ưc to ra có chi phí vưt quá m&t ngư:ng cutoff thì nút ó s&

039; b 1 c 3 t gim, quá trình tìm kim backtracks trưc khi tip tc. Các ngư:ng chi phí ưc kh/i to ưc lưng heuristic c!a trng thái ban "u, và trong m 0 i l"n lp k tip làm t ng t,ng chi phí c!a các nút có chi phí thp ã ưc c 3 t t 4 a trưc ó. Thut toán chm dt khi trng thái ích có t,ng chi phí không vưt quá ngư:ng hi n ti.

Minh ha A*

1.1: Minh h+a A*

h 1 = 1+0+2+1+1+0+1+1 = 7 3.1 heuristic2 = t,ng khong cách d 1 ch chuyn [;,] ng 3 n nht  d 1 ch chuyn các ô sai v v 1 trí úng c!a nó c&ng thêm ch 4 s pht cp ô hàng xóm vi nhau ang n[m ngưc v 1 trí c!a nhau.

1.1: ích 1.1: Minh h
a

 h 2 = d + a Trong ó a là ch s pht cp ô hàng xóm ang nm ngc v trí. Cp [2,1] mu n v úng v 1 trí c"n d 1 ch chuyn ít nht 4 bưc[không  ý ti các ô khác], 2 bưc ã ưc tính trong ?d nên a = 2. Vì vy trong 1.1 có 2 cp hàng xóm n[m ngưc v 1 trí nên / ây a = 2+2 = 4.

3.1 heuristic

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1.1: ích 1.1: Minh h
a Xét 1 ô n[m sai v 1 trí: d = |rows – row| 2 + |cols – col| 2 t d 3 = ?d

2 1

6 7 5

3 8 4

1 2

3 4 5

6 7 8

2 6 3 7

4 5 10 11

12 9 14 1

8 13 15

 h 3 = d 3 – [0*d 3 ] + a

3.1 heuristic Xét 1 ô sai n[m sai v 1 trí: d = |rows – row| 2 + |cols – col| 2 t d 4 = ?d  h 4 = d 4 + a

3 Ví d so sánh 3 hàm heuristic

Xét trng 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 = d 34 – [0*d 34 ] + 2 = 21
• heuristic4 = d 34 + 2 = 24

8 7 1

6 4

3 2 5

2- So sánh Vi trng thái b 3 t "u là trng thái / hình trên:

 Thut 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 gii quyt: 38598ms