intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: Cau Be | Ngày: | Loại File: PDF | Số trang:23

1.148
lượt xem
160
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài tập lớn môn Trí tuệ nhân tạo với đề tài "Thuật toán A* ứng dụng trong bài toán ghép tranh" nhằm xây dựng 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í.

Chủ đề:
Lưu

Nội dung Text: 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 />
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2