HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO MÔN HỌC
TRÍ TUỆ NHÂN TẠO
Giáo viên hướng dẫn: Ngô Hữu Phúc
HÀ NỘI 3/2010
Họ và tên:Vũ Khắc Điệp-Tin 5a
GIẢI THUẬT TÌM KIẾM A*
Trong khoa học máy tính, A* (A* Search) là 1 thuật toán tìm kiếm trong đồ thị.
Thuật toán này tìm một đường đi từ 1 nút khởi đầu tới 1 nút cho trước (hoặc tới 1 nút
thỏa mãn 1 điều kiện đích). Thuật toán này sử dụng 1 đá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
thưo thứ tự của đánh giá heurristic này. Do đó thuật toán A* là 1 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ở Peter Hart và Bertram Rafael.
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
1 đánh giá heuristic thích hợp sẽ thu được hoạt động tối ưu, do đó mà có tên là A*.
I.Heuristic chấp nhận được
Trong kỹ thuật tìm kiếm, để việc tìm kiếm có hiệu quả sẽ sử dụng hàm đánh giá để
hướng dẫn tìm kiếm. Các kỹ thuật này thuộc nhóm tìm kiếm Heuristic.
• Giả sử u là một trạng thái đạt tới (có đường đi từ trạng thái đầu u
0
tới u);
hàm đánh giá được xác định như sau:
 g(u): đánh giá độ dài đường đi ngắn nhất từ u
0
tới u.
 h(u): đánh giá độ dài đường đi ngắn nhất từ u tới trạng thái
đích.Hàm h(u) được gọi là chấp nhận được nếu với mọi trạng thái u,
h(u) ≤ độ dài đường đi ngắn nhất thực tế từ u tới trạng thái đích.
 Để tăng hiệu quả của quá trình tìm kiếm: f(u) = g (u) + h(u)

A* lưu giữ một tập các lời giải chưa hoàn chỉnh, nghĩa là các đường đi qua đồ thị,
bắt đầu từ nút xuất phát. Tập lời giải này được lưu trong một hàng đợi ưu tiên (priority
queue). Thứ tự ưu tiên gán cho một đường đi n được quyết định bởi hàm lượng giá f(n)=
g(n) + h(n)
 g(n) = chi phí để đến n
 h(n)= lượng giá từ n đến đích
 f(n)= ước lượng tổng giá đến đích qua n
Procedure A*;
Begin
1. Khởi tạo danh sách L chỉ chứa trạng thái đầu.
2. Loop do
2.1. if L rỗng then {thông báo thất bại; stop;}
2.2. Loại trạng thái u ở đầu danh sách L;
2.3. if u là trạng thái đích then {thông báo thành công; stop}
2.4. for mỗi trạng thái v kề u do
{ g(v) ← g(u)+ k(u,v); f(v) ← g(v)+h(v);
Đặt v vào danh sách L;}
2.5. Sắp xếp L theo thứ tự giảm dần của hàm f sao cho trạng thái có giá trị
của hàm f nhỏ nhất ở đầu danh sách;
3.END
IV.Chương trình DEMO
a.Giao diện chương trình
Gồm các phần:
• Vẽ Điểm
• Vẽ cạnh
• Xóa
• Thuật toán A*
• Thoát
1.Vẽ điểm
Ta CLIKC chuột và chọn các điểm bất kỳ

Canh = new int[1000, 1000];
for (i = 0; i < 1000; i++)
for (j = 0; j < 1000; j++)
{
if (i == j)
Canh[i, j] = 0;
else Canh[i, j] = -1;
}
h = new int[1000];
g = new int[1000];
f = new int[1000];
father = new int[1000];
ChuaXet = new bool[1000];
Queue = new int[1000];
QueueNo = 0;
for (i = 0; i < 1000; i++)
{
father[i] = 0;
ChuaXet[i] = true;
}
DaTimThay = false;

rtxtQueue.Text = "";
2.Hàm vẽ điểm
private void DrawPoint(int x, int y)
{
_PointNo += 1;
_Points[_PointNo] = new Point(x, y);
cmbDiemCuoi.Items.Add(_PointNo.ToString());
cmbDiemDau.Items.Add(_PointNo.ToString());

{
if (diem == false)
{
i = TimDiem(e.X, e.Y);
if (i > 0)
{
dau = new Point(_Points[i].X, _Points[i].Y);
idau = i;
graph.FillEllipse(new SolidBrush(Color.DarkBlue),
_Points[i].X - 10, _Points[i].Y - 10, 20, 20);
graph.DrawString(i.ToString(), new
Font(FontFamily.GenericSerif, 13, FontStyle.Bold, GraphicsUnit.Pixel, 8,
false), Brushes.White, _Points[i].X - 6, _Points[i].Y - 6);
diem = true;
}
}
else
{
i = TimDiem(e.X, e.Y);
if (i>0)
{
cuoi=new Point(_Points[i].X, _Points[i].Y);
graph.DrawLine(new Pen(Color.DarkBlue), dau, cuoi);
graph.FillEllipse(new SolidBrush(Color.DarkBlue),
dau.X - 10, dau.Y - 10, 20, 20);
graph.DrawString(idau.ToString(), new
Font(FontFamily.GenericSerif, 13, FontStyle.Bold, GraphicsUnit.Pixel, 8,
false), Brushes.White, dau.X - 6, dau.Y - 6);
kc = (int)Math.Sqrt((dau.X - cuoi.X) * (dau.X -
cuoi.X) + (dau.Y - cuoi.Y) * (dau.Y - cuoi.Y)) / 10;

duongdi ="Đường đi: "+ DiemDau.ToString() + " > " + duongdi;
rtxtQueue.Text +=duongdi+ "\r\nĐộ dài đường đi: " +
kc.ToString();;
graph.FillEllipse(new SolidBrush(Color.Red), _Points[DiemDau].X -
10, _Points[DiemDau].Y - 10, 20, 20);
graph.FillEllipse(new SolidBrush(Color.Red), _Points[DiemCuoi].X -
10, _Points[DiemCuoi].Y - 10, 20, 20);
graph.DrawString(DiemDau.ToString(), new
Font(FontFamily.GenericSerif, 13, FontStyle.Bold, GraphicsUnit.Pixel, 8,
false), Brushes.White, _Points[DiemDau].X - 6, _Points[DiemDau].Y - 6);
graph.DrawString(DiemCuoi.ToString(), new
Font(FontFamily.GenericSerif, 13, FontStyle.Bold, GraphicsUnit.Pixel, 8,
false), Brushes.White, _Points[DiemCuoi].X - 6, _Points[DiemCuoi].Y - 6);

}
6.Hàm sắp xếp vị trí trong danh sách L
private void SapXep()
{
int tg;
for (int i=vt+1;i<QueueNo;i++)
for (int j=i+1;j<=QueueNo;j++)
if (f[i] > f[j])
{
tg = f[i]; f[i] = f[j]; f[j] = tg;
tg = Queue[i]; Queue[i] = Queue[j]; Queue[j] = tg;
tg = father[i]; father[i] = father[j]; father[j] =tg;
tg = g[i]; g[i] = g[j]; g[j] = tg;
}
}
7.Hàm xủ lí thuật toán A*

}
}
SapXep();
vt += 1;
}
}

if (vt<=QueueNo)
AStar();
}
}
8.Hàm vẽ đồ thị
private void DrawDoThi()
{
int i;
int j;
int kc;
panel1.Refresh();
for (i = 1; i <= _PointNo; i++)
for (j = 1; j <= _PointNo; j++)
if (Canh[i, j] > 0)
{
graph.DrawLine(new Pen(Color.BlueViolet), _Points[i],
_Points[j]);
kc = (int)Math.Sqrt((_Points[i].X - _Points[j].X) *
(_Points[i].X - _Points[j].X) + (_Points[i].Y - _Points[j].Y) * (_Points[i].Y
- _Points[j].Y)) / 10;
graph.DrawString(kc.ToString(), new
Font(FontFamily.GenericSerif, 13, FontStyle.Bold, GraphicsUnit.Pixel, 8,
false), Brushes.Red, (_Points[i].X + _Points[j].X) / 2, (_Points[i].Y +