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