Báo Cáo Đồ Án Nhập Môn AI: Áp Dụng Thuật Toán A* Trong N-Puzzle | Đại học Điện lực

lOMoARcPSD| 59629529
TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN
NHẬP MÔN TRÍ TUỆ NHÂN TẠO ĐỀ TÀI:
ÁP DỤNG THUẬT TOÁN A* VÀO TRÒ CHƠI GHÉP TRANH
Sinh viên thực hiện : TRẦN THỊ THẢO PHƯƠNG LÊ DUY KIÊN NGUYỄN ĐỨC NAM
Giảng viên hướng dẫn : VŨ VĂN ĐỊNH
Ngành : CÔNG NGHỆ THÔNG TIN
Lớp học phần : D16CNPM7 Khóa : D16 lOMoARcPSD| 59629529
Hà Nội, tháng 10 năm 2023 PHIẾU CHẤM ĐIỂM STT
Họ và tên sinh viên Điểm Chữ ký 1 Trần Thị Thảo Phương 2 Lê Duy Kiên 3 Nguyễn Đức Nam
Họ và tên giảng viên Chữ ký Ghi chú Giảng viên chấm 1: Giảng viên chấm 2: MỤC LỤC
CHƯƠNG 1. THUẬT TOÁN A*.................................................................1 1.1
Giới thiệu thuật toán................................................................................1 lOMoARcPSD| 59629529 1.2
Mô tả thuật toán.......................................................................................2 1.3
Cài đặt thuật toán.....................................................................................2 1.4
Ví dụ minh họa........................................................................................4 1.5
Đánh giá thuật toán..................................................................................5 1.6
Ưu điểm của A*.......................................................................................5 1.7
Nhược điểm..............................................................................................5
CHƯƠNG 2. BÀI TOÁN GHÉP TRANH..................................................6 2.1
Giới thiệu về bài toán ghép tranh.............................................................6 2.2
Minh họa..................................................................................................6 2.3
Áp dụng thuật toán A* vào ứng dụng ghép tranh 8 số............................9
CHƯƠNG 3. CHƯƠNG TRÌNH...............................................................25 CHƯƠNG 4. KẾT
LUẬN...........................................................................26 LỜI MỞ ĐẦU
Trong thời đại công nghệ 4.0 đang ngày càng phát triển, ứng dụng trí tuệ
nhân tạo vào đời sống được xem là một trong những xu thế phát triển mạnh mẽ
hiện nay. Việc tự động hóa các hành vi thông minh đang trở thành một cuộc cách
mạng trong ngành công nghệ thông tin.
Vì vậy chúng em đã thực hiện đồ án trí tuệ nhân tạo áp dụng thuật toán A*
để làmlàm ra trò chơi ghép tranh 8 ô số, phục vụ cho việc chứng minh áp dụng trí
tuệ nhân tạo mang lại lợi ích tối ưu về không gian và thời gian cho con người.
Với sự hướng dẫn tận tình của thầy Vũ Văn Định, chúng em đã hiểu được
cách thức hoạt động của thuật toán và hoàn thành bài báo cáo đồ án này. Do chưa
có nhiều kinh nghiệm nghiên cứu, thực hành nên chúng em cũng không tránh khỏi lOMoARcPSD| 59629529
những thiếu sót. Chúng em rất mong nhận được sự thông cảm và góp ý của thầy
để đề tài của chúng em được hoàn thiện hơn.
Chúng em xin chân thành cảm ơn ! lOMoARcPSD| 59629529
CHƯƠNG 1. THUẬT TOÁN A* 1.1
Giới thiệu thuật toán
Trong khoa học máy tính, A* là một thuật toán tìm kiếm trong đồ thị.
Thuật toán này tìm đường đi từ nút khởi đầu tới một nút đích cho trước .
Thuật toán áp dụng hàm đánh giá heuristic để sắp xếp từng nút theo ước
lượng về hướng đi tôt nhất đi qua nút đó: Nút tốt nhất sẽ được ưu tiên duyêt
trước nhằm tìm kiếm kết quả tốt nhất. Do đó, thuật toán A* là thuật toán sử dụng
thuật toán tìm kiếm tốt nhất đầu tiên với hàm đánh giá f(u) thay vì h(u). Hình 1 – Thuật toán A*
A* khác với best fist search ở chỗ thuật toán còn lưu lại chi phí mà nó đã
đi qua. Điều đó làm cho A* đầy đủ và tối ưu, nghĩa là: A* không đảm bảo sẽ
chạy nhanh hơn các thuật toán tìm kiếm đơn giản hơn.
A* còn nhật lại cả đỉnh đã duyệt và các đỉnh chờ duyệt nếu hướng đi mới tốt hơn. 1.2 Mô tả thuật toán
Nếu u là một trạng thái hiện tại . lOMoARcPSD| 59629529
Ta xác định hàm đánh giá: f(u) = g(u) + h(u). •
g(u) là chi phí từ nút gốc u0 tới nút hiện tại u. •
h(u) là hàm đánh giá heuristic nhằm tínhchi phí nhỏ nhất có
thể để đếnđích từ u.
Hàm f(u) có giá trị càng thấp thì độ ưu tiên của u càng cao . •
f(u) tổng chi phí ước lượng của đường đi qua nút hiện tại u đến đích. 1.3
Cài đặt thuật toán
OPEN: bao gồm tập các trạng thái đang được chờ để xét. Trong tập OPEN ta sẽ
ưu tiên cho nút có chi phí bé nhất so với các nút còn lại trong tập OPEN để phát triển.
CLOSE: tập chứa các trạng thái đã được xét đến. Nếu có một trạng thái
khác đang set mà trùng với trạng thái trong tập CLOSE và có tổng chi phí đường
đi tốt hơn thì trạng thái đó sẽ thay thế trạng thái cũ trong tập CLOSE.
Khi xét đến trạng thái u, trong OPEN bên cạnh việc lưu trữ 3 giá trị cơ
bản h, g, f để so sánh độ ưu tiên của trạng thái đó, A* còn lưu trữ thêm hai thông số sau:
• Cha của u (ký hiệu Father(v)): cho biết đường đi dẫn đến trạng thái u.
• Danh sách các trạng thái kề với u: chứa các trạng thái kế tiếp v của u. - Thuật toán. BEGIN lOMoARcPSD| 59629529
1. Khởi tạo danh sách OPEN chỉ chứa trạng thái ban đầu, CLOSE = rỗng. 2. Lặp
2.1 If OPEN rỗng {thông báo tìm thất bại; stop};
2.2 Loại trạng thái u ở đầu danh sách OPEN
2.3 If u là trạng thái đích {thông báo đã tìm thành công; stop;};
2.4 For mỗi trạng thái v kề u { g(v) = g(u) + k(u,v)
If v không thuộc OPEN hay CLOSE { f(v)  g(v) + h(v); Father (v)  u
Đặt v vào danh sách OPEN; } }
2.5 Sắp xếp OPEN theo thứ tự tăng dần của hàm đánh giá f saocho
trạng thái có giá trị của hàm f nhỏ nhất ở đầu danh sách. END 1.4
Ví dụ minh họa tìm đường đi từ A-Z lOMoARcPSD| 59629529 E-I=3
Hình 2 – Ví dụ minh họa Bướ u v OPEN CLOSE father c lặp 0 A 1 A B,C,D,E C13,E21,B24,D27 A 2 C E,G E21,B24,G26,D27 A,C {A} 3 E I I18,E21,B24,G26,D27 A,C,E {C} 4 I H,Z Z19,E21,B24,H25,G26,D27 {E} 1. A,C,E 5 Z I I
Vậy đường đi là ACEIZ. 1.5
Đánh giá thuật toán
Độ phưc tạp thời gian của A* phụ thuộc vào hàm đánh giá heuristic. Tùy
từng bài toán mà có hàm đánh giá khách nhau. lOMoARcPSD| 59629529
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.
Đọ phức tạp bộ nhớ A* còn rắc rối hơn độ phức tạp về thời 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ũ. 1.6 Ưu điểm của A*.
- Một thuật toán hiệu quả, tổng quát, linh động, tối ưu.
- Thuật toán chứa cả tìm kiếm theo chiều sâu, tìm kiếm theo
bề rộng vànhững hàm đánh giá Heuristic khác.
-Tìm kiếm đến đích nhanh hơn với sự định hướng của hàm Heuristic. 1.7 Nhược điểm
A* rất linh động nhưng vẫn gặp một khuyết điểm cơ bản đó là phải lưu
lại các trạng thái đi qua nhằm so sánh với trạng thái hiên tại nên tốn khá nhiều bộ nhớ.
CHƯƠNG 2. BÀI TOÁN GHÉP TRANH
2.1 Giới thiệu về bài toán ghép tranh.
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, 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. Ở đây ta xét bài toán ghép tranh với giao diện đơn giản nhất là bài toán 8 số. lOMoARcPSD| 59629529
Bài toán gồm môt ma trận 3x3 các tranh được đánh thứ tự từ 1 đến 8.̣ Trạng
thái ban đầu, các ô số được đánh thứ tự ngẫu nhiên, 1 ô trống đánh số 0. Nhiêm
vụ của ta là phải sắp xếp từ vị trí 0 với các ô lân cận sao cho đưa chúng ̣ trở về
đúng thứ tự ( trạng thái đích). 2.2 Minh họa. • Trạng thái đầu • Các bước đi tiếp
- B1: Từ trạng thái đầu sẽ sinh ra 3 trạng thái tiếp
+ G(u)=1, h(u)= 4 => f(u)=5.
+ G(u)=1, h(u)= 4 => f(u)=5. lOMoARcPSD| 59629529
+ G(u)=1, h(u)= 2 => f(u)=3.
- B2: Từ các trạng thái trên chọn trạng thái tốt nhất sẽ là f =3. Phát triểntiếp ta được.
G(u)=2, h(u)= 4 => f(u)=6. Kiểm tra có tồn tại trong Close xong đánh giá
không tốt hơn trạng cũ lên không được cập nhật để phát triển.
+ G(u)=2, h(u)= 1 => f(u)=3. lOMoARcPSD| 59629529 - B3 : chọn f=3.
+ G(u)=3, h(u)= 2 => f(u)=5.
+ G(u)=3, h(u)= 0 => f(u)=3. => trạng thái đích.
2.3Áp dụng thuật toán A* vào ứng dụng ghép tranh 8 số. lOMoARcPSD| 59629529
2.3.1Khởi tạo lớp Node để mô tả trạng trái hiện tại . public class Node {
public int[,] MaTran;// ma trận 8 số public int
SoManhSai;//số mảnh sai vị trí của ma trận public int
ChiSo;// chỉ số của node public int Cha;// cha của
node, để truy vét kết quả public int fn;// chi phí đi đến node đó } 2.3.2 Hàm đánh giá
Tùy vào từng bài toán , mỗi bài toán có hàm đánh giá khác nhau. Trong bài toán
ghép tranh thì hàm đánh giá sẽ dựa vào số mảnh sai so với vị trí đích cộng với
chi phí đã đi tới nút đó.
int soMiengSaiViTri(int[,] MaTran) { int dung = 0; if (MaTran[0, 0] == 1) dung++; if (MaTran[0, 1] == 2) dung++; if (MaTran[0, 2] == 3) dung++; if (MaTran[1, 0] == 4) dung++; if (MaTran[1, 1] == 5) dung++; if (MaTran[1, 2] == 6) dung++; if lOMoARcPSD| 59629529 (MaTran[2, 0] == 7) dung++; if (MaTran[2, 1] == 8) dung++; return 8 - dung; }
2.3.3 Hàm tìm ra vị trí tốt nhất của tập Open để phát triển.
Đưa các nút vào tập Open , sau đó sắp xếp chúng sao cho vị trí tốt nhất đứng đầu của danh sách.
Nếu tồn tại 2 trạng thái có số mảnh sai = nhau
int viTriTotNhatOpen(List Open) { if (Open.Count != 0) { Node min = new Node(); min = Open[0]; int vt = 0;
for (int i = 1; i < Open.Count; i++)
if (min.SoManhSai > Open[i].SoManhSai) { min = Open[i]; vt = i; } else lOMoARcPSD| 59629529 {
if (min.SoManhSai == Open[i].SoManhSai) { if (min.fn > Open[i].fn) { min = Open[i]; vt = i; } } } return vt; } return 0; }
2.3.4 Hàm kiểm tra trong tập Close tồn tại trạng thái đó chưa.
bool danhSachDaCoMaTran(int[,] a, List Close) {
for (int i = 0; i < Close.Count; i++) {
if (haiMaTranBangNhau(a, Close[i])) { return true; } } lOMoARcPSD| 59629529 return false; }
2.3.5 Hàm sinh ngẫu nhiên trạng thái đầu.
// sinh một ma trận ngẫu nhiên để làm node bắt đầu
public int[,] randomMaTran(int kickThuoc) {
int[,] MaTran = new int[kickThuoc, kickThuoc];
//khởi tạo ma trận 8 số MaTran[0, 0] = 1; MaTran[0, 1] = 2; MaTran[0, 2] = 3; MaTran[1, 0] = 4; MaTran[1, 1] = 5; MaTran[1, 2] = 6; MaTran[2, 0] = 7; MaTran[2, 1] = 8; MaTran[2, 2] = 0;
//tập Close lưu lại các hướng đã đi để đảm bảo sinh ra hướng đi mới không trùng lặp List Close = new List(); int n = MaTran.GetLength(0); lOMoARcPSD| 59629529 int[,] Temp = new int[n, n];
Array.Copy(MaTran, Temp, MaTran.Length);
Close.Add(Temp); int h = 2, c = 2; Random rd = new Random(); int t = rd.Next(1, 5); for (int r = 0; r < 20; r++) { if (h==2 && c==2 ) {
MaTran[h, c] = MaTran[h - 1, c]; MaTran[h - 1, c] = 0; h--;
MaTran[h, c] = MaTran[h, c - 1]; MaTran[h, c - 1] = 0; c--; }
//đi lên trên với t =1 t =
rd.Next(1, 5); if (h > 0 && h <= n - 1 && t == 1) {
MaTran[h, c] = MaTran[h - 1, c]; MaTran[h - 1, c] = 0;
if (!danhSachDaCoMaTran(MaTran, Close)) { h --; Temp = new int[n, n];
Array.Copy(MaTran, Temp, MaTran.Length); Close.Add(Temp); lOMoARcPSD| 59629529 } else {
MaTran[h - 1, c] = MaTran[h, c]; MaTran[h, c] = 0; } } t = rd.Next(1, 5); //đi sang trái với t=2
if (c > 0 && c <= n - 1 && t == 2) {
MaTran[h, c] = MaTran[h, c - 1]; MaTran[h, c - 1] = 0;
if (!danhSachDaCoMaTran(MaTran, Close)) { c--; Temp = new int[n, n];
Array.Copy(MaTran, Temp, MaTran.Length); Close.Add(Temp); } else {
MaTran[h, c - 1] = MaTran[h, c]; MaTran[h, c] = 0; } } lOMoARcPSD| 59629529 t = rd.Next(1, 5);
//đi xuống giưới với t=3
if (h < n - 1 && h >= 0 && t == 3) {
MaTran[h, c] = MaTran[h + 1, c]; MaTran[h + 1, c] = 0;
if (!danhSachDaCoMaTran(MaTran, Close)) { h+ +; Temp = new int[n, n];
Array.Copy(MaTran, Temp, MaTran.Length); Close.Add(Temp); } else { MaTran[h + 1, c] = MaTran[h, c]; MaTran[h, c] = 0; } } t = rd.Next(1, 5);
//đi sang phải với t = 4
if (c < n - 1 && c >= 0 && t == 4) { lOMoARcPSD| 59629529
MaTran[h, c] = MaTran[h, c + 1]; MaTran[h, c + 1] = 0;
if (!danhSachDaCoMaTran(MaTran, Close)) { c+ +; Temp = new int[n, n];
Array.Copy(MaTran, Temp, MaTran.Length); Close.Add(Temp); } else {
MaTran[h, c + 1] = MaTran[h, c]; MaTran[h, c] = 0; } } }
// trả về hướng đi cuối dùng trong danh sách hướng đi
return Close[Close.Count - 1]; }
2.3.6 Hàm tìm kiếm kết quả đưa về trang thái đích
public Stack timKetQua(int[,] MaTran, int n) {
Stack stkKetQua = new Stack(); List Close = new List(); List Open = new List();