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 ---------<br /> <br /> BÀI T P L N<br /> <br /> NH P MÔN TRÍ TU NHÂN T O<br /> tài: THU T TOÁN A* NG D NG TRONG BÀI TOÁN GHÉP TRANH<br /> <br /> 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<br /> <br /> HÀ N I 04-2013<br /> <br /> M CL C<br /> L i nói u ........................................................................................................................................ 3<br /> <br /> 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<br /> <br /> III- CÀI 1. 2. 3.<br /> <br /> Tr ng thái xu t phát ................................................................................................................. 9 Cài t A* ............................................................................................................................... 9<br /> <br /> 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<br /> <br /> III- K T QU ................................................................................................................................. 15 123Giao di n............................................................................................................................... 15 So sánh.................................................................................................................................. 16 Nh n xét ................................................................................................................................ 21<br /> <br /> 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.<br /> <br /> 2<br /> <br /> L i nói<br /> <br /> u<br /> <br /> â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.<br /> <br /> Xin chân thành c m ơn !<br /> <br /> 3<br /> <br /> I- BÀI TOÁN GHÉP TRANH<br /> 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).<br /> <br /> 4<br /> <br /> 1.1.1: Tr ng thái b t<br /> <br /> u và ích<br /> <br /> Bư c di chuy n c a ô tr ng:<br /> <br /> 1.1.2: Bư c di chuy n c a ô tr ng<br /> <br /> II- THU T TOÁN A*<br /> 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<br /> 5<br /> <br />