Bài tập lớn môn Trí tuệ nhân tạo: Thuật toán A* ứng dụng trong bài toán ghép tranh

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 CL C
L i nói u ........................................................................................................................................ 3

I- BÀI TOÁN GHÉP TRANH ......................................................................................................... 4 II- THU T TOÁN A*....................................................................................................................... 5 123Gi i thi u thu t toán ................................................................................................................ 5 Mô t thu t toán ...................................................................................................................... 7 Cài t thu t toán..................................................................................................................... 7 T BÀI TOÁN................................................................................................................. 9

III- CÀI 1. 2. 3.

Tr ng thái xu t phát ................................................................................................................. 9 Cài t A* ............................................................................................................................... 9

Hàm ư c lư ng heuristic ....................................................................................................... 12 3.1 3.2 Các hàm ư c lư ng heuristic .......................................................................................... 12 Ví d so sánh 3 hàm heuristic.......................................................................................... 14

III- K T QU ................................................................................................................................. 15 123Giao di n............................................................................................................................... 15 So sánh.................................................................................................................................. 16 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. tài nh m m c ích xây d ng m t h th ng gi i quy t Nhóm th c hi n 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 ó. M i tr ng thái c a b ng s là m t hoán v c a n2 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 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 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

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