TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
BÁO CÁO BÀI TẬP LỚN
Giải bài toán N-Puzzle sử dụng thuật toán A*
Giáo viên: ThS. Phạm Văn Hải
Nhóm số 2:
Đặng Vũ Hạnh 20080899
Trần Bá Tùng 20083041
Nguyễn Huy Triển 20082751
Phạm Việt Phong 20083429
Phùng Ngọc Duy 20101256
Nguyễn Anh Tuấn 20102772

Hà Nội, Tháng 08 năm 2013
1
Lời nói đầu
Chọn đề tài này với mong muốn có thể áp dụng những kiến thức học tập và nghiên cứu
được để bắt tay xây dựng một ứng dụng cụ thể. Việc này giúp chúng em có thể hiểu sâu về thuật
toán hơn, sử dụng linh hoạt để xử lý những bài toán tìm kiếm trong quá trình học tập , nghiên
cứu và công việc sau này. Sử dụng những thuật toán thông minh của con người, kết hợp với tốc
độ xử lý dữ liệu của máy tính để tạo nên một thiết bị hoàn hảo, từ những thuật toán nhỏ hình
thành ý tưởng lớn. Lập trình cho các thiết bị có thể thay thế những công việc của con người
trong tương lai.

2
A. Thuật toán A*
I. Tìm hiểu thuật toán
Thuật toán A* là một trường hợp của Best First Search nên ta sẽ đi tìm hiểu trực quan BFS
trước khi bắt tay vào A* để có thể có một cái nhìn chung về những thuật toán tìm kiếm tối ưu
này.
1.Khái niệm

+ CLOSE: Tập chứa các trạng thái đã được xét đến, ta cần lưu trữ những trạng thái này trong
bộ nhớ để phòng trường hợp khi một trạng thái mới sinh ra trong qua trình duyệt lại trùng hợp
với trạng thái đã xét tới trước đó. Khi không gian tìm kiếm có dạng cây thì ta không cần sử
dụng tới tập này.
- Cài đặt
+ Đặt OPEN chứa trạng thái khởi đầu
Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong tập OPEN vòng lặp thực
hiện duyệt các trạng thái tiếp theo, mỗi bước:
+ Chọn trạng thái tốt nhất Tbest trong OPEN ( và xóa trạng thái Tbest khỏi OPEN)
+Nếu Tbest là trạng thái kết thúc thì thoát.
+Nếu Tbest không phải là trạng thái tốt nhất, tạo ra các trạng thái Tn con của Tbest . Đối với
mỗi trạng thái kết tiếp, thực hiện tính hàm chi phí f(Tn) và thêm Tn vào trong OPEN.
Hình ảnh minh họa BFS
1.2. Thuật toán tìm kiếm A*
5
a. Khái niệm
Không giống như thuật toán Dijkstra , A* là một thuật toán tìm đường đi từ điểm tới điểm, từ
một nút khởi đầu đến một nút đích cho trước hoặc tới một nút thỏa mãn điều kiện và không sử
dụng để tìm giải pháp cho vấn đề tìm đường đi ngắn nhất trong học thuyết đồ thị.
Về bản chất, thuật toán này làm việc rất giống như Dijkstra. Nhưng hiệu quả hơn khi A* sử
dụng một hàm đánh giá bổ sung ( đánh giá heuristic) để ước lượng về tuyến đường đi tốt nhất
qua nút đó (Việc lựa chọn trạng thái tiếp theo sẽ phụ thuộc vào hàm lượng giá này).
A* Là một ví dụ cho thuật toán Best first search, là một thuật toán đầy đủ, luôn tìm thấy một
lời giải nếu bài toán có lời giải.
b. Đăt vấn đề:
Vấn đề đưa ra giống với vấn đề được giải quyết bởi thuật toán tìm đường đi ngắn nhất Dijkstra.
Cho một đồ thị ( đồ thị có hướng và trọng số không âm) và hai node trên đồ thị (gọi là điểm bắt
đầu và điểm cuối), cần tìm một con đường có chi phí đi từ đầu tới cuối là nhỏ nhất trong các
đường đi có thể, kết quả là danh sách các node nó cần đi qua để tới đích với chi phí nhỏ nhất.
c. Thuật toán

1. Vấn đề
Bài toán N-Puzzle
Bài toán này khá quen thuộc, với nhiều phiên bản khác nhau như 8 puzzle, 15 puzzle….
Ở mức độ thấp nhất đó là 8 puzzle, bài toán bao gồm một bảng 3x3 các ô số được đánh từ
1>8.
Ở trạng thái bắt đầu, thứ tự của các ô số được sắp xếp ngẫu nhiên, nhiệm vụ của người giải
là phảo đưa chúng về đúng thứ tự ban đầu đó là sắp xếp theo thứ tự tăng dần và từ trái qua
phải.
2. Xây dựng giải pháp
Bài toán được xây dựng trên bảng các ô vuông theo kích thước n x n (với 8 puzzle thì n=3 và
với 15 puzzle thì n=4). Số lượng trạng thái ban đầu là hoán vị của n x n phần tử. Như vậy , mỗi
khi giá trị của n tăng lên 1 thì không gian trạng thái của bài toán cũng tăng lên rất nhanh. Do
vậy, phụ thuộc vào cách chọn hàm đánh giá, nếu không kết hợp với các kỹ thuật bổ sung thì các
bài toán với n>3 rất lâu tìm ra kết quả hoặc là không thể thực hiện quá trình tìm lời giải bởi vì
không gian trạng thái quá lớn.
- Bài toán 8 Puzzle
Dễ dàng nhận thấy rằng, tại mỗi trạng thái của bài toán chỉ có tối đa 4 cách di chuyển sang trạng
thái khác ( trái , phải, lên , xuống)- các trạng thái con, và để có thể trở về trạng thái thỏa mãn
yêu cầu (trạng thái đích) thì trạng thái đầu tiên phải tuân theo một quy luật nào đó.
Xét một ví dụ về trạng thái đầu tiên như sau:
8
Duyệt qua từng ô theo thứ tự từ trái sang phải và đếm tổng số các ô có giá trị nhỏ hơn sau nó
theo thứ tự duyệt
Xét tại i=1, ta thấy có 7 ô nằm sau có giá trị nhỏ hơn 8 : n1 = 7
Xét tại i=2, có 5 giá trị nằm sau nó nhỏ hơn 6: n2=5
Xét tại i=3, có 3 giá trị nằm sau nó nhỏ hơn 4: n3=3
Xét tại i=4, có 4giá trị nằm sau nó nhỏ hơn 7: n2=4
Xét tại i=5, và i =6 có 2 giá trị nhỏ hơn nó n5= n6 = 2
Xét tại i=7, n7 =1
Và giá trị n8=0

Tìm trạng thái đích?
Ta có thể nhận ra rằng để xác định tọa độ đúng ( ở trạng thái đích) của ô có giá trị Id trên ma
trận ô vuông kích thước n x n thì ta sử dụng công thức sau:
RowId = Id / n;
ColId = Id % n;
Tính giá chi phí từ trạng thái hiện tại tới trạng thái đích theo hàm lượng giá sử dụng phương
pháp tính khoảng cách Manhattan, xét trên một ô vuông xi có tọa độ đích là (row1, col1) và
trạng thái hiện tại là (row2, col2)
Giá trị khoảng các theo hàm ước lượng: h= |row1 – row2| - |col1 – col2|
B. Cài đặt
10
I. Xây dựng ứng dụng
Để minh họa cho bài toán, nhóm sẽ xây dựng một ứng dụng ghép hình ảnh
1. Phương pháp giải quyết bài toán
Sử dụng hàm đánh giá chi phí: f(n) = g(n) + h(n);
Giá trị : g(n): chi phí từ node gốc tơi node hiện tại, h(n): chi phí ước lượng từ nút hiện
tại tới đích.
Loại bỏ vòng lặp
Để đảm bảo giải thuật A* là hoàn chỉnh thì phải khử các vòng lặp
Bằng cách, mỗi nút con sinh ra, ta kiểm tra trạng thái của chúng có tồn tại trong hai tập
OPEN và CLOSE hay không trước khi thêm nó vào trong tập hợp OPEN để tránh việc
xét lại các phương án đã xét trước đó.
Để tăng tốc độ duyệt tìm các nút trùng lặp nên đã sử dụng tập hash như một bảng
băm rồi đem ra so sánh.
Hàm ước lượng Heuristic h(n)
Hàm ước lượng : h(n) = h1+ h2 ( h1 là tổng chi phí ngắn nhất để đưa các ô sai về vị trí
đúng theo khoảng cách Manhattan, h2 là hàm chặn)
Gọi x là khoảng cách theo chiều dọc sai vị trí, y là khoảng cách theo chiều ngang sai vị
trí thì h2 công thêm max(x,y) với mỗi ô có (x+y)>1
2. Cấu trúc chương trình

final int f()
boolean isSame(int[] n): So sánh trạng thái
boolean isSameOpen(TreeNode[][] hash, Tree t)
ArrayList<TreeNode> findPart(TreeNode[][] hash, int[] finish, Tree t)
e. Class Tree

void addOpen(TreeNode t) : Thêm Node vào tập hợp OPEN
void addHash(TreeNode n): Thêm Node vào tập hợp HASH
13
TreeNode getOpen() : Lấy một Node ra từ trong danh sách OPEN
void AStar() : Cài đặt thuật toán tìm kiếm A*
void start(TreeNode st, TreeNode fn) : Tiến hành thực hiên tìm kiếm
void stop(): Kết thúc quá trình tìm kiếm ( khi quá thời gian quy định hoặc khi quá trình tìm
kiếm kết thúc).
3. Vấn đề còn tồn tại
- Hàm đánh giá Heuristic chưa đánh giá được hoàn chỉnh, chỉ sử dụng được ở các mức thâp
- Duyệt tìm ở mức cao, phần tử trong hash có số phần tử con lớn nên thuật toán bị chậm
4. Hướng phát triển
- Tìm hàm ước lượng tối ưu hơn, đánh giá được giá trị tốt hơn và có thể sử dụng ở các mức cao
hơn
- Xây dựng hàm băm tối ưu hơn để tăng tốc tìm kiếm
- Tiếp tục nghiên cứu thuật toán , áp dụng cho công việc và học tập – nghiên cứu sau này

II. Sử dụng sản phẩm
Đây là màn hình giao diện đầu tiên của chương trình
- Trong mục lựa chọn, hãy chọn độ khó phù hợp.
- Nếu bạn muốn sử dụng hình ảnh mặc đỉnh của chương trình thì hãy ấn vào nút “Tạo mới” để
bắt đầu chơi, nếu không hãy chọn nút “Chọn ảnh” để lấy hình ảnh trên máy tính của mình lên
chương trình.
14