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!
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_pcGjkcBdk2fvr6lq6cNsmwEKI28aHaS2HPF_-8Kr82KOEzNqulEvo11HOCHawUZfVDP4mjx3e2D2B0o8-5X298UBWKWCxvxArY-UfjHMWlhBvvjWIA2Ei-92bKwyVpnkVX9N8_8bgbQ/s0/n-puzzle-ai.png"
/>
Đề 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
href="https://soict.hust.edu.vn/pgs-ts-le-thanh-huong.html"
target="_blank"
>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ình và
khó tương đương với các kích thước 3*3, 4*4 và
5*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
class="lazy loaded"
data-src="https://img.youtube.com/vi/FVGLKZnQj4k/sddefault.jpg"
lazied=""
src="https://img.youtube.com/vi/FVGLKZnQj4k/sddefault.jpg"
/>
Hình ảnh
class="lazy loaded"
data-src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1tz92RwxPN8PLO73kxgdkDnFKyvvyIaG9kQq91SRDSOfygAlUWKkPhRO7P6-p0h1ZkFVgeUxcd5G6BeWVhgpf7XuI4gu89ZILgSACQYfY7TkK0lX0mjthhla7zLpvA0ZIH5RJRe4wBhU/s0/main.png"
lazied=""
onclick="return false"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1tz92RwxPN8PLO73kxgdkDnFKyvvyIaG9kQq91SRDSOfygAlUWKkPhRO7P6-p0h1ZkFVgeUxcd5G6BeWVhgpf7XuI4gu89ZILgSACQYfY7TkK0lX0mjthhla7zLpvA0ZIH5RJRe4wBhU/s0/main.png"
/>
class="lazy loaded"
data-src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpRLrFhs8B4Xkmi9ucN5GkS4BxAcK7eGBeJip6tMfa0xB2WU4IyG_GzDO5kGQvwtsCUHxkfETKUa9tGk4lRw17ZL2rr2GAnK-uVCeDcDwAKvZGLqT1TuE7Xz5QL_p9VGXGFeP68m1XTuw/s0/jumb.png"
lazied=""
onclick="return false"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpRLrFhs8B4Xkmi9ucN5GkS4BxAcK7eGBeJip6tMfa0xB2WU4IyG_GzDO5kGQvwtsCUHxkfETKUa9tGk4lRw17ZL2rr2GAnK-uVCeDcDwAKvZGLqT1TuE7Xz5QL_p9VGXGFeP68m1XTuw/s0/jumb.png"
/>
class="lazy loaded"
data-src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJfnQbevDYKhClMpDIp_rSJgxzh41dxz1elLG2LwF2w_4_Fc4Uk7RTusRy_6h9v3iU3CFfI-gZ-KtDn7V7oPgGkc3jyx5mWOBUkQRK1M1CpQc-fw-HgWpRbThO8Ux5897NkLJ5-HTKFUk/s0/img.png"
lazied=""
onclick="return false"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJfnQbevDYKhClMpDIp_rSJgxzh41dxz1elLG2LwF2w_4_Fc4Uk7RTusRy_6h9v3iU3CFfI-gZ-KtDn7V7oPgGkc3jyx5mWOBUkQRK1M1CpQc-fw-HgWpRbThO8Ux5897NkLJ5-HTKFUk/s0/img.png"
/>
class="lazy loaded"
data-src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilzJkAz-MWy6vcxVYMDfnN0GbQGMk4ofY4xXEiYoKJcCKaCMAjg3JbEc_kfFSm4p5a0_i27oZROqZlYtr-csqS4UeyA_sVBom3ZoruePnGNwC46vXuo-Ddb2BPOxhUiiBOLbtqJVbiflQ/s0/play.png"
lazied=""
onclick="return false"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilzJkAz-MWy6vcxVYMDfnN0GbQGMk4ofY4xXEiYoKJcCKaCMAjg3JbEc_kfFSm4p5a0_i27oZROqZlYtr-csqS4UeyA_sVBom3ZoruePnGNwC46vXuo-Ddb2BPOxhUiiBOLbtqJVbiflQ/s0/play.png"
/>
class="lazy loaded"
data-src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4edEYdvG7ABHRZCuW5FScGmYyX2y5AsTBhvCoIuNkxD-oc80aflUopuvoiHwFLyd3uq4YyE9Txc_URvAbbEJUk3tpg975RKP4BNh2Qz9-RYjjWLj-g-tW9mnHAJ9VyD9J9Sp2mridu3Q/s0/ket-qua.png"
lazied=""
onclick="return false"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4edEYdvG7ABHRZCuW5FScGmYyX2y5AsTBhvCoIuNkxD-oc80aflUopuvoiHwFLyd3uq4YyE9Txc_URvAbbEJUk3tpg975RKP4BNh2Qz9-RYjjWLj-g-tW9mnHAJ9VyD9J9Sp2mridu3Q/s0/ket-qua.png"
/>
class="lazy loaded"
data-src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8cuIvDBvbkEDwkv_AKHwXZVFAPTGu6aloPmnGjSJjQEMd1yI8qb8yfHPSa2_faXw_c3HYFtWDBE8LLzDelX0V9-WIr-s17VnPpp0ZccVXzw9IiinF4QBlC7Yh0UjyG3vty7FJeAV8684/s0/so-sanh.png"
lazied=""
onclick="return false"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8cuIvDBvbkEDwkv_AKHwXZVFAPTGu6aloPmnGjSJjQEMd1yI8qb8yfHPSa2_faXw_c3HYFtWDBE8LLzDelX0V9-WIr-s17VnPpp0ZccVXzw9IiinF4QBlC7Yh0UjyG3vty7FJeAV8684/s0/so-sanh.png"
/>
Phụ lục
Source code:
href="https://github.com/phamvanlinhxyz/N-Puzzle-AI"
target="_blank"
>https://github.com/phamvanlinhxyz/N-Puzzle-AI >
Báo cáo:
href="https://drive.google.com/file/d/1gBWbTK4GK_m73iyomaOFbRzZ1Nv1EIkZ/view?usp=sharing"
target="_blank"
>https://drive.google.com/file/d/1gBWbTK4GK_m73iyomaOFbRzZ1Nv1EIkZ/view?usp=sharing >
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