TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
BÁO CÁO BÀI TẬP LỚN TRÍ TUỆ NHÂN TẠO
Đề tài:
Tìm hiểu giải thuật A* , ứng dụng giải bài toán 8-puzzle
Giảng viên hướng dẫn: Thầy Phạm Văn Hải
Sinh viên thực hiện: Nguyễn Hải Đăng 20090713
Đỗ Hà Anh 20090073
Lê Khánh Dương 20090591
Mai Văn Quân 20092116
Bùi Việt Anh 20090051
Nguyễn Văn Chinh 20096374
Hà Nội 7/2013
Mục lục
Lời nói đầu 2
I. Giới thiệu về bài toán n-puzzle 3
1. Phân tích bài toán 3
2. Phương pháp 4
II. Tìm hiểu về giải thuật A* 5
1. Giới thiệu về A* 5
2. Mô tả thuật toán 6
3. Sử dụng giải thuật A* vào bài toán 8
a. Ý tưởng về hàm lượng giá 9
b. Cách tính hàm lượng giá 10
III. Biểu diễn không gian trạng thái bài toán 11
IV. Công nghệ và ngôn ngữ lập trình sử dụng 12
V. Triển khai cài đặt thuật toán A* 14
VI. Giao diện 22
VII. Hướng cải thiện chương trình 24
VIII. Tài liệu tham khảo 27

4 | T r a n g
Xin chân thành cảm ơn
I. Giới thiệu bài toán n-puzzle :
Bài toán (hay game) n-puzzle có lẽ rất quen thuộc với chúng ta cũng như những
người mới bắt đầu tiếp cận với môn trí tuệ nhân tạo. 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, Game of
Fifteen, Mystic Square,… Ở mức độ đơn giản tôi xin nói về 8-puzzle.
Bài toán gồm một bảng 3×3 với các ô số được đánh từ 1->8 và một ô trống. Ở trạng
thái bắt đầu, các ô được sắp đặt ngẫu nhiên, và nhiệm vụ của người giải là tìm cách di
chuyển các ô sao cho các con số về đúng thứ tự, bài toán đặt ra ở đây là tìm phương
án tối ưu sao cho số lần di chuyển là ít nhất.
1 2 3
4 5 6
7 8
1 5 7
2 3 6
4 8

Trạng thái đầu (hình 1) Trạng thái đích
5 | T r a n g
1. Phân tích bài toán :
Để đơn giản trong cách tiếp cận giải bài toán, người ta giả định chỉ có ô trống trong
bảng là di chuyển đến những vị trí khác. Như vậy tại một trạng thái thì chỉ có tối đa 4
cách đi để chuyển sang trạng thái khác (trái, phải, lên, xuống).
Với trạng thái đầu như hình trên thì có ba trạng thái đích có thể xảy ra :
1 2 3
4 5 6
7 8
1 2 3
8 4

Với số N này ta chỉ cần biết 1 thông tin là nó có chia hết cho 2 hay không (lẻ hay chẵn).
Nếu N là số chẵn thì chúng ta chỉ có thể có đáp án là trạng thái đích là A hoặc B,
ngược lại là trạng thái C . Bởi vì khi di chuyển ô trống với hướng đi bất kì thì giá trị N
mod 2 cũng không thay đổi. Tức là từ trạng thái đích bạn có thể xáo trộn bằng cách di
chuyển ô trống nhiều lần thì giá trị N vẫn là số chẵn.
7 | T r a n g
Lý do : Do trật tự ta qui định trước là từ trái sang phải , từ trên xuống dưới ,qui định
nó như là một tập không có thứ tự các số , rồi xét các khả năng hoán vị của ô trống và
cuối cùng kết luận là hoặc là bảo toàn , hoặc là tăng giảm theo 2.
Chúng ta đã xác định được trạng thái đích cần đạt được, bây giờ bắt đầu tìm kiếm giải
thuật để tìm ra đích. Ở đây có nhiều giải thuật nhằm tìm ra đáp án. Ở đây tôi giới
thiệu 4 giải thuật tìm kiếm:
1. Tìm kiếm theo chiều rộng (Breadth-first search algorithm)
2. Tìm kiếm theo chiều sâu (Depth-first search algorithm)
3. Tìm kiếm lặp sâu dần (cải tiến từ giải thuật tìm kiếm theo chiều sâu)
4. A* (a sao) (cải tiến từ thuật toán Dijkstra) (minh họa bằng giải thuật này)
II. Tìm hiểu giải thuật A* :
1. Giới thiệu A* :
Trong khoa học máy tính, A* (đọc là A sao) là một thuật toán tìm kiếm trong đồ thị.
Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới
một nút thỏa mãn một điều kiện đích). Thuật toán này sử dụng một "đánh giá heuristic"
để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó. Thuật toán
này duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó, thuật toán A* là một ví
dụ của tìm kiếm theo lựa chọn tốt nhất (best-first search).
Thuật toán A* được mô tả lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson, và Bertram
Raphael. Trong bài báo của họ, thuật toán được gọi là thuật toán A; khi sử dụng thuật
toán này với một đánh giá heuristic thích hợp sẽ thu được hoạt động tối ưu, do đó mà có
tên A*.
Năm 1964, Nils Nilsson phát minh ra một phương pháp tiếp cận dựa trên khám phá để
tăng tốc độ của thuật toán Dijkstra . Thuật toán này được gọi là A1. Năm 1967 Bertram

bổ sung x vào tập đóng
foreach y in các_đường_đi_tiếp_theo(p)
đưa_vào_hàng_đợi(q, y)
return failure
9 | T r a n g
A*- search _ Các đặc điểm :
− Nếu không gian các trạng thái là hữu hạn và có giải pháp để tránh việc xét (lặp)
lại các trạng thái, thì giải thuật A* là hoàn chỉnh (tìm được lời giải) – nhưng
không đảm bảo là tối ưu.
− Nếu không gian các trạng thái là hữu hạn và không có giải pháp để tránh việc
xét (lặp) lại các trạng thái, thì giải thuật A* là không hoàn chỉnh (không đảm
bảo tìm được lời giải).
− Nếu không gian các trạng thái là vô hạn, thì giải thuật A* là không hoàn chỉnh
(không đảm bảo tìm được lời giải).
− Một ước lượng (heuristic) h(n) được xem là chấp nhận được nếu đối với mọi
nút n: 0 ≤ h(n) ≤ h*(n), trong đó h*(n) là chi phí thật (thực tế) để đi từ nút n đến
đích.
− Giải thuat A với hàm heuristic h(n) luôn luôn giá trị thực đi từ n đến goal.
Tính tối ưu của A* - Chứng minh :
Giả sử có một đích không tối ưu (suboptimal goal) G2 được sinh ra và lưu trong cấu
trúc fringe. Gọi n là một nút chưa xét trong cấu trúc fringe sao cho n nằm trênmột
đường đi ngắn nhất đến một đích tối ưu (optimal goal) G.
Ta có: 1) f(G2) = g(G2) vì h(G2) = 0
Ta có: 2) g(G2) > g(G) vì G2 là đích không tối ưu
Ta có: 3) f(G) = g(G) vì h(G) = 0
Từ 1)+2)+3) suy ra: 4) f(G2) > f(G)
Ta có: 5) h(n) ≤ h*(n) vì h là ước lượng chấp nhận được
10 | T r a n g
Từ 5) suy ra: 6) g(n) + h(n) ≤ g(n) + h*(n)
Ta có: 7) g(n) + h*(n) = f(G) vì n nằm trên đường đi tới G

Thuật toán A*:
• Gọi G là số bước đã di chuyển ô trống
• H là hàm heuristic, ước tính số hao tổn để tới trạng thái đích, tính bằng tổng
các quãng đường của các ô ở vị trí sai để về tới vị trí đúng
F
(n)
=G
(n)
+H
(n)
Có hai danh sách Open và Close, Open chứa các trạng thái chưa xét, danh sách Close
chứa các trạng thái đã xét.
Ban đầu ta thêm trạng thái khởi đầu vào Open, sau đó chọn trạng thái có f= g+ h nhỏ
nhất , lúc này danh sách Open chứa duy nhất trạng thái khởi đầu nên ta lấy trạng thái
khởi đầu khỏi Open và đưa vào danh sách Close các trạng thái đã xét .Từ trạng thái
đang xét ta xác định được các trạng thái tiếp theo dựa vào các hướng di chuyển của ô
trống .Đưa tất cả các trạng thái mới mà chưa có trong Close và Open vào danh sách
Open. Ta tiếp tục chọn trạng thái có f = g+h nhỏ nhất khỏi Open như bước đầu tiên cho
đến khi tìm ra trạng thái đích thì dừng lại. Từ trạng thái đích vừa tìm được đường đi
từ trạng thái khởi đầu đến trạng thái đích.
b. Cách tính khoảng cách sai lệch của các ô số với vị trí đúng(hàm lượng giá
h) :
1 5 7
2 3 6
12 | T r a n g
4 8
Trong bảng số 3×3 trên, để di chuyển ô số 5 vào đúng vị trí ta cần di chuyển nó 1 lần,
để di chuyển ô số 7 về đúng vị trí ta cần cần 4 lần (qua 4 ô khác). Để có được kết quả
này ta làm phép tính đơn giản: lấy tổng khoảng cách của dòng và cột giữa hai vị trí (ví
dụ với ô số 7):

2 3
4 8 6
1 5 7
2 3 6
4 8
f= 2+ 12 = 14
15 | T r a n g

f=3+12 =15 f= 3+12= 15
1 5
2 3 7
4 8 6
1 5 7
2 3
4 8 6
III. Công cụ và ngôn ngữ lập trình sử dụng :
1. Ngôn ngữ lập trình C# :
Ngôn ngữ C# khá đơn giản, chỉ khoảng hơn 80 từ khóa và hơn mười mấy kiểu dữ liệu
được dựng sẵn. Tuy nhiên, ngôn ngữ C# có ý nghĩa to lớn khi nó thực thi những khái
niệm lập trình hiện đại. C# bao gồm tất cả những hỗ trợ cho cấu trúc, thành phần
component, lập trình hướng đối tượng. Những tính chất đó hiện diện trong một ngôn
16 | T r a n g
ngữ lập trình hiện đại. Hơn nữa ngôn ngữ C# được xây dựng trên nền tảng hai ngôn
ngữ mạnh nhất là C++ và Java.
C# có các đặc trưng sau đây:
- C# là ngôn ngữ đơn giản
- C# là ngôn ngữ hiện đại
- C# là ngôn ngữ hướng đối tượng
- C# là ngôn ngữ mạnh mẽ và mềm dẻo
- C# là ngôn ngữ hướng module

các kiểu giá trị int, double,…
• GetId(): Tạo ra id cho đối tượng, id dựa vào thứ tự sắp xếp các số trong mảng,
dĩ nhiên với 2 mảng khác nhau thì id cũng khác nhau. Việc dùng Id sẽ giúp ta
kiểm tra và tìm kiếm đối tượng dễ dàng hơn khi chúng ở trong một collection.
(Bạn nên cẩn thận khi cho kích thước bảng quá lớn sẽ vượt ngoài phạm vi kiểu
int của biến Id).
• MakeMove(MoveDirection): thực hiện “di chuyển” (hoán vị) bảng số dựa vào
hướng di chuyển được truyền vào
• Shuffle(): Xáo trộn bảng số
- OpenList: Chứa các đối tượng Matrix (node) đã được duyệt tới, khi thêm một
node vào danh sách. Ta sẽ chèn nó vào đúng vị trí sao cho OpenList luôn được sắp xếp
từ nhỏ đến lớn.
19 | T r a n g
• idList: Danh sách cài đặt bằng HashSet chứa id của các phần tử được thêm vào,
dùng để kiểm tra trước khi thêm xem trong OpenList có phần tử đó chưa. Việc
lưu trữ dùng mã “băm” sẽ giúp việc tìm kiếm nhanh hơn so với các dạng
collection khác.
- GameEngine: đối tượng quản lý chung các hoạt động của thuật toán, chứa danh
sách OPEN và CLOSE. Danh sách “solution” để lưu lại đường đi tìm được từ trạng thái
đầu tiên tới đích.
• Solve(): phương thức chính đế giải bài toán.
• Evaluate(): hàm lượng giá Heuristic tính giá trị của một bảng số.
• GenMove(Matrix): Sử dụng phương thức CloneMove(Matrix, MoveDirection)
sinh ra các nước đi tiếp theo từ node được truyền vào. Nếu node mới tạo ra đã
tồn tại trong CLOSE thì kiểm tra và cập nhật nước đi ngắn hơn cho node.
• TrackPath(): Tạo danh sách các nước đi từ trạng thái đầu tiên đến đích và lưu
vào đối tượng solution.
1. Lớp Matrix:
Trong lớp này thay vì sử dụng mảng hai chiều để lưu bảng số, thì sử dụng mảng 1
chiều để so sánh. Tuy điều này có lợi về lưu trữ và giúp cho một vài đoạn code viết dễ

get { return GameEngine.IndexCols[Blank_Pos] > 0; }
}
public bool CanMoveRight
{
get { return GameEngine.IndexCols[Blank_Pos] < Size - 1; }
}
Các property trên sẽ được viết rất dễ dàng nếu như bạn dùng mảng hai chiều. Trong
bảng số Size*Size, để ô trống (Blank_Pos) có thể di chuyển lên trên (hay xuống dưới),
21 | T r a n g
tức là nó không nằm ở dòng đầu tiên (hoặc dòng cuối nếu như di chuyển xuống) của
bảng, và phép kiểm tra rất đơn giản như bạn thấy ở trên.
Tương tự với phép kiểm tra di chuyển trái/phải, ta lấy tọa độ ô trống chia dư cho Size
để lấy được tọa độ cột, cuối cùng là so sánh.
public override bool Equals(object obj)
{
Matrix m = obj as Matrix;
if (m == null)
return false;
return this.Id.Equals(m.Id);
}
Phương thức này cần được override nếu bạn muốn các collection tìm kiếm đúng đối
tượng Matrix mà mình muốn.
2. Lớp GameEngine :
Phương thức kiểm tra bài toán có cấu hình hợp lệ không (có thể đưa về dạng đích)
/// <summary>
/// Kiểm tra xem puzzle có thể chuyển về dạng đích ko
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public bool CanSolve(Matrix matrix)

{
// Làm rỗng các collection
closeQ.Clear();
openQ.Clear();
Solution.Clear();

// Thêm phần tử hiện tại vào OPEN
this._matrix.Parent = null;
this._matrix.Score = Evaluate(this._matrix);
openQ.Add(this._matrix);

while (openQ.Count > 0)
{
// Lấy node có giá trị (ComparingValue) nhỏ nhất
Matrix m = openQ[0];
// Kiểm tra xem có phải trạng thái đích
if (m.Score == WIN_VALUE)
{
// Tạo solution
24 | T r a n g
TrackPath(m);
return;
}

// Xóa node đầu tiên của OPEN
openQ.Remove(m);
// Sinh các node tiếp theo của node m
GenMove(m);
}
}