Bình luận

Thông báo

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Test link

Đề tài: Ứng dụng thuật toán BFS và A* vào giải bài toán xếp hình N-Puzzle

trí tuệ nhân tạo, bài toán n-puzzle, n-puzzle trong ai, bfs, a*, astar, tìm kiếm trong ai

Nếu bạn mới làm quen với AI hoặc mới học nhập môn AI tại trường thì có lẽ bài toán N-Puzzle không còn quá xa lạ với các bạn nữa!

Đề tài: Ứng dụng thuật toán BFS và A* vào giải bài toán xếp hình N-Puzzle

Giới thiệu

Đề tài

Ứng dụng thuật toán BFS và A* vào giải bài toán xếp hình N-Puzzle

Bài toán ban đầu đặt ra một ma trận vuông kích thước N*N với các ô số ngẫu nhiên, nhiệm vụ của người chơi là di chuyển ô trống sao cho đưa được tất cả các ô số về đúng trạng thái đích.

Tác giả

Tên Mã sinh viên
Phạm Văn Linh 20194094
Nguyễn Văn Đức 20194023
Bùi Tiến Đạt 20194012
Vũ Đức Anh 20193985

Giáo viên hướng dẫn

PGS.TS. Lê Thanh Hương - SOICT - HUST

Tính năng

Các tính năng của trò chơi sẽ được chia thành 2 nhóm chứ năng đó là chắc năng người chơi và chức năng giải bằng AI

Chức năng của người chơi:
  • Người chơi có thể sử dụng button Trộn để xáo các ô số trên màn hình.
  • Có 2 chế độ dành cho người chơi: chơi bằng bảng ô số hoặc thêm ảnh từ thiết bị.
  • Người chơi có thể chọn 3 mức độ chơi dễ, trung bìnhkhó tương đương với các kích thước 3*3, 4*45*5.
  • Người chơi có thể tùy chọn 2 trạng thái đích.
  • Khi chơi, người chơi thực hiện di chuyển các ô số thông qua các nút W, A, S, D trên bàn phím hoặc click chuột.
Chức năng giải bằng AI:
  • Người chơi có thể để AI tự giải bằng button Giải, sau khi giải xong người chơi có thể lựa chọn tự chạy lời giải hoặc không.
  • Chức năng thứ 2 đó là so sánh các Heuristic, AI sẽ tự chạy lần lượt các Heuristic để tìm lời giải sau đó so sánh kết quả các lần chạy.

Thuật toán

Trong trò chơi này bọn mình dùng 2 thuật toán để tìm lời giải đó là:

  • Tìm kiếm theo chiều rộng - BFS
  • Tìm kiếm với tri thức bổ sung - A* với 6 heuristic sẽ được giới thiệu ở phần sau.

Heuristic

6 heuristic được bọn mình sử dụng với thuật toán A* đó là:

  • H1: Tổng số ô sai vị trí.
  • H2: Khoảng cách Manhattan - Khoảng cách ngắn nhất để các ô về đúng vị trí đích.
  • H3: Khoảng cách Euclid giữa các ô và vị trí đích(lấy phần nguyên).
  • H4: Tổng số ô sai hàng cộng số ô sai cột.
  • H5: Linear conflict - Khoảng cách manhattan + số ô linear conflict
  • H6: H5 + số ô không thể về đích(các ô mà vị trí xung quanh trạng thái đích của nó đều đúng).

Demo

Video

Youtube video

Hình ảnh

Hình ảnh khởi tạo trò chơi
Trò chơi sau khi trộn
Thêm ảnh và trò chơi mức trung bình
Hình ảnh khi người chơi giải được
Hiển thị lời giải khi tìm được đáp án
Hiển thị kết quả so sánh heuristic

Phụ lục

Lời kết

Trong bài viết này mình đã chia sẻ cho các bạn bài tập lớn nhập môn AI của bọn mình. Nếu có bất kì thắc mắc hay góp ý nào hãy để lại cho mình 1 comment ở bên dưới. Chúc các bạn một ngày tốt lành!

Copyright © Phạm Văn Linh

Đánh Giá Bài Viết:
No pain, no gain !

Post a Comment

© Phạm Văn Linh. All rights reserved. Developed by Jago Desain
-->