Trần Thị Hồng Diệp Tin
học 5A
HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
-o0o-
ĐỒ ÁN MÔN TRÍ TUỆ NHÂN TẠO
Đề tài: Không gian trạng thái được mô tả là bài toán người
đưa thư. Hãy xây dựng chương trình cho phép tìm kiếm
đường đi tốt nhất theo giải thuật tìm kiếm Greedy best first
search
Thầy giáo hướng dẫn: Ngô Hữu Phúc
Họ và tên: Trần Thị Hồng Diệp
Lớp: Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
LỜI MỞ ĐẦU

Trí tuệ nhân tạo (Artificial Intelligence) có thể được định nghĩa như một
ngành của khoa học máy tính liên quan đến việc tự động hoá các hành vi thông
minh. AI là một bộ phận của khoa học máy tính và do đó nó phải được đặt trên
những nguyên lý lý thuyết vững chắc, có khả năng ứng dụng được của lĩnh vực
này. Những nguyên lý này bao gồm các cấu trúc dữ liệu dùng cho biểu diễn tri
thức, các thuật toán cần thiết để áp dụng những tri thức đó, cùng các ngôn ngữ và
kĩ thuật lập trình dùng cho việc cài đặt chúng.
Những đặc điểm của trí tuệ nhân tạo:
• Sử dụng máy tính vào suy luận trên các ky hiệu, nhận dạng, học và một số
hình thức suy luận khác.
• Tập trung vào một số vấn đề không thích hợp với các lời giải mang tính
thuật toán. Điều này dựa trên cơ sở tin tường vào phép tìm kiếm heuristic
như một kỹ thuật giải quuyết vấn đề AI.
• Sự quan tâm đến các kỹ thuật giải quyết vấn đề bằng những thông tin
không chính xác, thiếu hụt hoặc được định nghĩa một cách nghèo nàn, và

những ngành con. Trong khi chia sẻ một tiếp cận giải quyết vấn đề cơ bản, các
ngành con này có các mối quan tâm đến các ứng dụng khác nhau để giải quyết các
bài toán khác nhau.
Nhiều vấn đề bài toán phức tạp đều có dạng "tìm đường đi trong đồ thị" hay nói
một cách hình thức hơn là "xuất phát từ một đỉnh của một đồ thị, tìm đường đi hiệu
quả nhất đến một đỉnh nào đó". Một phát biểu khác thường gặp của dạng bài toán
này là:
Cho trước hai trạng thái T
0
và TG hãy xây dựng chuỗi trạng thái T
0
, T
1
, T
2
, , Tn
-1
,
Tn = TG sao cho:
thỏa mãn một điều kiện cho trước (thường là nhỏ nhất).
Trong đó, Ti thuộc tập hợp S (gọi là không gian trạng thái – state space) bao gồm
tất cả các trạng thái có thể có của bài toán và cost(T
i-1
, T
i
) là chi phí để biến đổi từ
trạng thái Ti
-1
sang trạng thái Ti. Dĩ nhiên, từ một trạng thái Ti ta có nhiều cách để
biến đổi sang trạng thái Ti

Tuy nhiên, cách giải này lại có độ phức tạp 0(n!) (một hành trình là một hoán vị
của n điểm, do đó, tổng số hành trình là số lượng hoán vị của một tập n phần tử là
n!). Do đó, khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh.
Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là dùng một
thuật giải Heuristic ứng dụng nguyên lý Greedy.
Tư tưởng của giải thuật Greedy best first search (GBFS) như sau:
Trong khoa học máy tính, Greedy best first search (GBFS) 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á f(n)=h(n) (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á heurristic
này. Khác với phương pháp tìm kiếm tốt nhất đầu tiên, phương pháp này sử dụng
hàm đánh giá đến trạng thái đích. GBFS chọn node được cho là gần với node đích
để phát triển.
Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n
đại lý rồi chọn đi theo con đường ngắn nhất.
Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc
trên. Nghĩa là liệt kê tất cả con đường từ đại lý ta đang đứng đến những đại
lý chưa đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc
không còn đại lý nào để đi.
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
Bạn có thể quan sát hình sau để thấy được quá trình chọn lựa. Theo nguyên lý
Greedy, ta lấy tiêu chuẩn hành trình ngắn nhất của bài toán làm tiêu chuẩn cho
chọn lựa cục bộ. Ta hy vọng rằng, khi đi trên n đoạn đường ngắn nhất thì cuối
cùng ta sẽ có một hành trình ngắn nhất. Điều này không phải lúc nào cũng đúng.
Với điều kiện trong hình tiếp theo thì thuật giải cho chúng ta một hành trình có
chiều dài là 14 trong khi hành trình tối ưu là 13. Kết quả của thuật giải Heuristic
trong trường hợp này chỉ lệch 1 đơn vị so với kết quả tối ưu. Trong khi đó, độ phức
tạp của thuật giải Heuristic này chỉ là 0(n

Thuật toán Tìm Kiếm Greedy best first search (GBFS)
Form Giải gồm 3 phần chính:
• Khu vực vẽ các nút
• Kết quả tìm kiếm
• Các nút chức năng: Điểm đầu, Giải, Giải từng bước
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
2. Giới thiệu chương trình:
// Hàm hiển thị
private void hienthi()
{
// Hiển thị nhà:
dt = new dothi("dt1.txt");

for (int i = 0; i < dt.Sonha; i++)
{
this.Controls.Add(dt.Nha[i]);
}
//Hiên thị giá đường dưới dạng textbox
diem = new Point[dt.Sonha];
for (int i = 0; i < dt.Sonha; i++)
{
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
diem[i] = new Point(dt.Nha[i].Location.X + dt.Nha[i].Height /
2, dt.Nha[i].Location.Y + dt.Nha[i].Width / 2);
}
tb = new TextBox[dt.Sonha, dt.Sonha];
for (int i = 0; i < dt.Sonha; i++)
{

}
}
// Hàm lưu nhà
private void luunha(int x, int y)
{
StreamReader sr = new StreamReader("dt1.txt");
string sonutcu = sr.ReadLine();
int sonutmoi = Convert.ToInt32(sonutcu) + 1;
string temp = sr.ReadToEnd();
sr.Close();
StreamWriter sw = new StreamWriter("dt1.txt");
sw.WriteLine(sonutmoi);
sw.WriteLine(temp);
string toado = x.ToString() + "," + y.ToString();
sw.Write(toado);
sw.Close();
}
//Hàm xóa dữ liệu
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
private void xoadulieu()
{
StreamWriter sw1 = new StreamWriter("dt1.txt");
sw1.Write("");
sw1.Close();
StreamWriter sw2 = new StreamWriter("dt2.txt");
sw2.Write("");
sw2.Close();
}
// Hàm lưu giá

{
StreamWriter sw = new StreamWriter("dt2.txt");
temp = "00 |";
sw.WriteLine(temp);
sw.Close();
}
else
{
StreamReader sr = new StreamReader("dt2.txt");
string[] dauvao = new string[dt.Sonha - 1];
for (int i = 0; i < dt.Sonha - 1; i++)
{
dauvao[i] = sr.ReadLine();
}
sr.Close();
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
StreamWriter sw = new StreamWriter("dt2.txt");
for (int i = 0; i < dt.Sonha - 1; i++)
{
temp = temp + dauvao[i] + " | 00 |";
temp = temp + "\r\n";
}
for (int i = 0; i < dt.Sonha; i++)
{ temp = temp + "00 | "; }
sw.WriteLine(temp);
sw.Close();
}
}
private void themtb()

Graphics dohoa = this.CreateGraphics();
Pen to = new Pen(Color.Red, 2);

for (int i = 0; i < dt.Sonha; i++)
{
for (int j = i + 1; j < dt.Sonha; j++)
{
dohoa.DrawLine(to,diem[i],diem[j]);
}
}
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
}
private void button1_Click(object sender, EventArgs e)
{
luugia();
}
// Hàm lưu tọa độ nhà
private void readcost(string _patch, string _patch_cost)
{
StreamReader sr = new StreamReader(_patch);
_sonha = Convert.ToInt16(sr.ReadLine());
_mangcost = new int[_sonha, _sonha];
_nha = new nha[_sonha];

string tuvao;
string[] mangkytu = null;
string[] tungancach = { " | " };
string[] daungan = { "," };
sr.ReadLine();

_sonha = Convert.ToInt16(sr.ReadLine());
_mangcost = new int[_sonha, _sonha];
_nha = new nha[_sonha];

string tuvao;
string[] mangkytu = null;
string[] tungancach = { " | " };
string[] daungan = { "," };
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
sr.ReadLine();
for (int i = 0; i < _sonha; i++)
{
tuvao = sr.ReadLine().ToString();
mangkytu = null;
mangkytu = tuvao.Split(daungan,
StringSplitOptions.RemoveEmptyEntries);
_nha[i] = new nha(i);
_nha[i].Location = new Point(Convert.ToInt16(mangkytu[0]) -
_nha[i].Height / 2, Convert.ToInt16(mangkytu[1]) - _nha[i].Width / 2);
}
sr.Close();

}
}
}
// Hàm Nhập
private void nhậpToolStripMenuItem_Click(object sender, EventArgs e)
{
foreach (Form frm in this.MdiChildren)

{
xoahienthi();
luunha(e.X, e.Y);
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
dt = new dothi("dt1.txt");
hienthi();
this.Refresh();
}
}
private void button2_Click(object sender, EventArgs e)
{
xoahienthi();
xoadulieu();
dt = new dothi();
checkBox1.Checked = true;
hienthi();
this.Refresh();
}

}
}
// Hàm hiển thị
private void hienthi()
{
// Hiển thị nhà:
dt = new dothi("dt1.txt","dt2.txt");
for (int i = 0; i < dt.Sonha; i++)
{
this.Controls.Add(dt.Nha[i]);

}
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS) private void button1_Click_1(object sender, EventArgs e)
{
dothi dt = new dothi("dt1.txt", "dt2.txt");
greedy gr = new greedy(dt);
if (textBox1.Text == "")
gr.tinhtoan(0);
else
gr.tinhtoan(Convert.ToInt16(textBox1.Text));
Graphics dohoa = this.CreateGraphics();
Pen to = new Pen(Color.Blue, 4);
for (int i = 0; i < dt.Sonha - 1; i++)
{
dohoa.DrawLine(to, diem[gr.KQ[i]], diem[gr.KQ[i + 1]]);
}
}
private void button2_Click(object sender, EventArgs e)
{
dothi dt = new dothi("dt1.txt", "dt2.txt");
greedy gr = new greedy(dt);
if (textBox1.Text == "")
gr.tinhtoan(0);
else
Trần Thị Hồng Diệp Tin học 5A
Thuật toán Tìm Kiếm Greedy best first search (GBFS)
gr.tinhtoan(Convert.ToInt16(textBox1.Text));

{
_dt = new dothi();
_ketqua = new int[_dt.Sonha];
for (int i = 0; i < _dt.Sonha; i++)
{
_ketqua[i] = -1;
}
}
public greedy(dothi dt)
{
_dt = dt;
_ketqua = new int[_dt.Sonha];
for (int i = 0; i < _dt.Sonha; i++)
{
_ketqua[i] = -1;
}
}
// Hàm tính toán
public void tinhtoan(int dauvao)
{
_ketqua[0] = dauvao;
int min = 9999;
Trần Thị Hồng Diệp Tin học 5A