TRNG I HC BÁCH KHOA HÀ NI
VIN CÔNG NGH THÔNG TIN VÀ TRUYN THÔNG
----------
BÀI TP LN
NHP MÔN TRÍ TU NHÂN TO
 tài:
THUT TOÁN A*
NG DNG TRONG BÀI TOÁN GHÉP TRANH
Sinh viên thc hin : Lê ình Cng
(Các thành viên khác) : ……………………
Mã s sinh viên : 20080370
Nhóm: 3
HÀ NI 04-2013
2
MC LC
Li nói u ........................................................................................................................................ 3
I- BÀI TOÁN GHÉP TRANH ......................................................................................................... 4
II- THUT TOÁN A* ....................................................................................................................... 5
1- Gii thiu thut toán ................................................................................................................ 5
2- Mô t thut toán ...................................................................................................................... 7
3- Cài t thut toán ..................................................................................................................... 7
III- CÀI T BÀI TOÁN ................................................................................................................. 9
1. Trng thái xut 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- KT QU ................................................................................................................................. 15
1- Giao din ............................................................................................................................... 15
2- So sánh .................................................................................................................................. 16
3- Nhn xét ................................................................................................................................ 21
IV- KT LUN ............................................................................................................................... 22
Tài liu tham kho .......................................................................................................................... 23
PHIU GIAO NHIM V BÀI TP LN .......................................... Error! Bookmark not defined.
3
Li nói u
ây là tài liu dùng  biu din cơ bn thit k và gii quyt bài toán
“Trò chơi ghép tranh” s dng thut toán A* do tôi thit k và lp trình. Tài liu
này giúp ta có cái nhìn toàn vn v các chc n ng c!a ph"n mm c#ng như ng
dng thut toán A*  gii quyt bài toán này. Do th$i gian có hn nên % án
không th ti ưu ưc toàn b& không gian trng thái bài toán. Tuy nhiên, nhóm
s' nghiên cu hoàn thin trong th$i gian sm nht.
Nhóm thc hin  tài nh(m mc ích xây dng m&t h thng gii quyt
m&t bài toán thc t da trên chin lưc tìm kim heuristic và xây dng m&t trò
chơi ng dng gii trí. Trong quá trình thc hin  tài không tránh kh)i nh*ng
sai sót, nhóm tôi mong s' nhn ưc s góp ý và ánh giá c!a th"y.
Xin chân thành cm n !
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
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
hin ti ti trng thái ích. Và cho ti nay v.n chưa có thut toán ti ưu  gii
bài toán này.
Ph"n mm N-Puzzle là m&t chương trình xây dng trò chơi và gii quyt
bài toán này. Ph"n mm ưc vit trên nn Java, s dng giao din % 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 dng bng ô vuông n hàng, n c&t. Bng g%m 1 ô trng 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 ô trng lên trên, xung 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 ô trng. Chương trình
có chc n ng t &ng chơi / bt kì trng thái nào ó. M0i trng thái c!a bng s
là m&t hoán v1 c!a n
2
ph"n t. 2 ây ta có th m/ r&ng b(ng vic thêm hình nh
vào game hoc g3n s vào hình nh  gi ý cho ngư$i chơi. 2 trng thái ban
"u, các ô ưc s3p xp ng.u nhiên, và nhim v c!a ngư$i chơi là tìm ưc
cách ưa chúng v trng thái ích(ô "u trng, các ô khác theo th t t ng d"n t-
trái qua phi, t- trên xung dưi).  ơn gin trong cách tip cn bài toán, ta
gi 1nh ch4 các ô trng di chuyn trong bng là di chuyn n các v1 trí khác
nhau. Như vy ti m&t trng thái bt kì có ti a 4 cách di chuyn n trng thái
khác(trái, phi, lên, xung).
5
1.1.1: Trng thái b3t "u và ích
Bưc di chuyn c!a ô trng:
1.1.2: Bưc di chuyn c!a ô trng
II- THUT 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