Bài Tập Lớn Trí Tuệ Nhân Tạo - Thuật toán A* Ứng dụng trong bài toán ghép tranh
Tài liệu thuộc Bài tập lớn về Công Nghệ Thông Tin
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à n 2 -1 ô chứa các số trong phạm vi [1, n 2 -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 n 2 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).
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à n 2 -1 ô chứa các số trong phạm vi [1, n 2 -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 n 2 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).
Bạn chỉ có thể xem 15 trang. Hãy đăng nhập để download toàn bộ tài liệu này!
Download
Trang /
Đang hiển thị tài liệu...
