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

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

Chia sẻ: Phan Thanh Nhan | Ngày: | Loại File: PPTX | Số trang:37

Thêm vào BST
Báo xấu
204
lượt xem 59
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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 Ø 1
  2. Nội dung 2
  3. Giớ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 3
  4. Giớ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á 4
  5. Giớ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* 5
  6. Mô 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 6
  7. Mô 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 7
  8. Mô 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 8
  9. Mô 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 9
  10. Mô tả giải thuật A* 2.b.3. Nếu Tmax không phải là Đích. Sinh ra các trạ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ác bước sau 10
  11. Mô tả giải thuật A* 11
  12. Mô tả giải thuật A* 12
  13. Mô tả giải thuật A* 13
  14. Mô 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. 14
  15. Mô 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*). 15
  16. Mô 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 16
  17. Mô tả giải thuật IDS ØTìm kiếm theo chiều sâu-DFS § Phát triển các nút chưa xét theo chiều sâu – Các nút được xét theo thứ tự độ sâu giảm dần § Cài đặt: fringe là một cấu trúc kiểu ngăn xếp (LIFO) – Các nút mới được bổ sung vào đầu của fringe) 17 DFS (N, A, n0, ĐICH)
  18. Mô tả giải thuật IDS § Ví dụ DFS: 18
  19. Mô tả giải thuật IDS § Ví dụ DFS: 19
  20. Mô tả giải thuật IDS § Ví dụ DFS: 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA
165 tài liệu
2070 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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