Danh mục

Đề tài: Xây dựng chương trình Game 15-Puzzle

Số trang: 37      Loại file: pptx      Dung lượng: 911.39 KB      Lượt xem: 18      Lượt tải: 0    
Hoai.2512

Phí tải xuống: 18,500 VND Tải xuống file đầy đủ (37 trang) 0
Xem trước 4 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Game 15-puzzle còn gọi là Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square và nhiều tên khácLà trò chơi di chuyển trên một khung bao gồm các ô vuông đánh số theo thứ tự ngẫu nhiên với một ô bị thiếuTrò chơi này cũng tồn tại trong các kíchcỡ khác nhau, đặc biệt nhỏ hơn là 8-Puzzle
Nội dung trích xuất từ tài liệu:
Đề tài: Xây dựng chương trình Game 15-Puzzle Trường đại học Hải Phòng Khoa Toán-TinĐề tài xây dựng chương trình Game 15-Puzzle Giáo viên hướng dẫn: Nguyễn Ngọc Khương Sinh viên thực hiện: Nguyễn Văn Hùng Ø Đào Quang Phương Ø Đào Nhật Thịnh Ø 1Nội dung 2Giới thiệu Game 15-PuzzleØ Game 15-puzzle còn gọi là Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square và nhiều tên khácØ Là trò chơi di chuyển trên một khung bao gồm các ô vuông đánh số theo thứ tự ngẫu nhiên với một ô bị thiếuØ Trò chơi này cũng tồn tại trong các kích cỡ khác nhau, đặc biệt nhỏ hơn là 8-Puzzle 3Giới thiệu Game 15-PuzzleØ Nếu kích thước là 3 x 3 ô, trò chơi được gọi là 8-Puzzle hoặc 9- Puzzle, và nếu là 4 × 4 ô, trò chơi được gọi là 15-Puzzle hoặc 16-Puzzle, được đặt tên tương ứng số lượng ô và số lượng của không gianØ Mục tiêu của trò chơi là đặt các ô theo trật tự bằng cách trượt các ô để di chuyển không gian trốngØ n-Puzzle là một vấn đề cổ điển cho các thuật toán mô hình hóa liên quan đến đánh giá 4Giới thiệu Game 15-Puzzle§ Hàm đánh giá thường được sử dụng cho vấn đề này bao gồm đếm số ô đặt sai chỗ và tìm kiếm tổng khoảng cách Manhattan giữa mỗi khối với vị trí của nó trong cấu hình mục tiêu§ Tất cả hàm đánh giá đều được chấp nhận, nghĩa là, số lượng di chuyển nhiều sẽ không được đánh giá cao nhằm đảm bảo tối ưu cho các thuật toán tìm kiếm nhất định chẳng hạn như A* 5Mô tả giải thuật A*Ø Trong khoa học máy tính, A* (đọc là A sao) là một thuật toán tìm kiếm trong đồ thị.Ø Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút thỏa mãn một điều kiện đích).Ø Thuật toán này sử dụng một đánh giá heuristic để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó.Ø Thuật toán duyệt các nút theo thứ tự của đánh giá heuristic này 6Mô tả giải thuật A*Ø A* Sử dụng các tập: Open , Close (Để lưu các trạng thái) Và các giá trị: G,H,F (Để phản ánh độ tốt của trạng thái)Ø Trong đó: § Open: Chứa các trạng thái đã được sinh ra nhưng chưa được xét đến § Close: Chứa các trạng thái đã được xét đến § G(x):Chi phí để đi từ trạng thái đầu đến trạng thái 7Mô tả giải thuật A*Ø Ngoài ra ta còn sử dụng thêm 1 giá trị Cha(x):Lưu lại trạng thái đã sinh ra trạng thái xØ Việc sử dụng thêm giá trị Cha nhằm giúp ta có thể tìm lại được con đường từ trạng thái đích đến trạng thái đầu 8Mô tả giải thuật A*1. Đặt OPEN chỉ chứa T0(Trạng thái ban đầu). Đặt g(T0) = 0 ; Cha(T0)=null ; Tính H(T0) và F(T0) Đặt CLOSE là tập hợp rỗng.2. Lặp lại các bước sau cho đến 9Mô tả giải thuật A* 2.b.3. Nếu Tmax khôngphải là Đích. Sinh ra cáctrạng thái con của Tmax.Gọi một trạng thái này làTk. Với mỗi Tk, làm cácbước sau 10Mô tả giải thuật A* 11Mô tả giải thuật A* 12Mô tả giải thuật A* 13Mô tả giải thuật A*§ Độ phức tạp thời gian của A* phụ thuộc vào đánh giá heuristic. Trong trường hợp xấu nhất, số nút được mở rộng theo hàm mũ của độ dài lời giải, nhưng nó sẽ là hàm đa thức khi hàm heuristic h thỏa mãn điều kiện sau:§ trong đó h* là heuristic tối ưu, nghĩa là hàm cho kết quả là chi phí chính xác để đi từ x tới đích. Nói cách khác, sai số của h không nên tăng nhanh hơn lôgarit của heuristic hoàn hảo h * - hàm trả về khoảng cách thực từ x tới đích. 14Mô tả giải thuật A*§ Vấn đề sử dụng bộ nhớ của A* còn rắc rối hơn độ phức tạp thời gian.§ Trong trường hợp xấu nhất, A* phải ghi nhớ số lượng nút tăng theo hàm mũ.§ Một số biến thể của A* đã được phát triển để đối phó với hiện tượng này, một trong số đó là A* lặp sâu dần (iterative deepening A*), A* bộ nhớ giới hạn (memory-bounded A* - MA*) và A* bộ nhớ giới hạn đơn giản (simplified memory bounded A*). 15Mô tả giải thuật IDSØ Thuật toán tìm kiếm sâu dần(IDS-Iterative deepening search) là một thuật toán tìm kiếm trong đồ thịØ Là thuật toán tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút thỏa mãn một điều kiện đích)Ø Thuật toán này sử dụng giải thuật DFS(Depth First Search) cho từng độ sâu trong cây tìm kiếm ...

Tài liệu được xem nhiều: