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
Báo cáo môn học Nhập môn trí tuệ nhân tạo
Đề bài:
!"
#"$%&'()*+, /+.*
/0&)*+122$"3245462
Tên học viên:
Khuất Đình Đăng
Giảng viên:
TS. Ngô Hữu Phúc
Yêu cầu:
780&' 9:4;$<=>?? 92@>A 9BC
I. Phương pháp %m kiếm Greedy Best First Search
D&)*+122$"3245462$@E&)*+
122$"3245462 FG"HIJK)*+2LJ*+MN
.)*+*
O !
E
C)*+4;$<*E#"$%PQ =NRJ
JM*4STUV U1VJ
T4WPJQUWVJX*Y,J+Z
C)*+4;$<*EM[G\J] 9+J#"$%
WME)*+4SG 9MNME)*+
.ENM)*+*(EJ\J &J.#"$%
^\J] =E#"$%_"JMMGL`\J"+
74WMZ$<ML
2. Loại trạng thái u ở đầu queue L;
3. If u là trạng thái kết thúc then { thông báo thành
công; stop; }
4. For mỗi trạng thái v kề u do
Xen v vào queue L sao cho các node trong L được sắp
xếp theo thứ tự tăng dần của hàm đánh giá;
End;
bJK1356
• Tính đủa >.MM[@\JoP*M
M$J"EM*E*0/
Q
• Độ phức tạp thời gian: pPQ 9+J2J4kG-W%+'"
4SGLJ
• Độ phức tạp không gian: pPQ FJ:G9$24
• Tính tối ưu: $*q/JK"r*qWJ
II. Các kết quả đạt được
O 78
3&'TMN 7R
-T./ 7R-4WX% 7R
Wh-/TW:h./ C]4WnMNR
Wh-T*%+:h./
1T /R
T * %+:h
. / 1 T
$NR- TT
q -
h c#" $% PQ
1T PQ
R - J J *
T 0 ^ *
- 44;$<..T'$-
- "TMTZ#-
- xyT4WX%-
- wa*Z-P-.E'[*ZQ
- !T-
- 6222$T-]0J"*
>&XZNa
public bool ifChecked(int _x, int _y) xác
định có phải đỉnh đang được trỏ đến bởi chuột hay
không.
public void show(PaintEventArgs e)
hiển thị đỉnh bằng một hình tròn bán kính r và số
thứ tự đỉnh.
public void showH(PaintEventArgs e)
hiển thị giá trị hàm đánh giá bên dưới hình tròn.
FNcanhT&XMN/ >J
qNcanh
private int xdau, ydau, xcuoi, ycuoi;
// tọa độ 2 đỉnh của cạnh.
private int dinhdau, dinhcuoi;
// số thứ tự 2 đỉnh.
private Graphics gr;
private Pen pen = new Pen(Color.Black, 1);
// gr và pen dùng để “vẽ” cạnh ra màn hình
private int dodai;
// độ dài cạnh
>&XNa
public void show(PaintEventArgs e)
// hiển thị cạnh ra màn hình là một đường thẳng
public void showS(PaintEventArgs e)
6%*EDDJ23a
private void pictureBox1_Paint(object sender,
PaintEventArgs e)
// hiển thị các cạnh, các đỉnh của đồ thị
6%*EGJa
private void pictureBox1_MouseDown(object sender,
MouseEventArgs e)
{
//nếu nhấn chuột trái
if (e.Button == MouseButtons.Left)
{
foreach (dinh temp in pList)
// nếu nhấn vào một đỉnh
if (temp.ifChecked(e.X, e.Y))
{
drag = true;
// cập nhật tọa độ đỉnh đầu, đỉnh cuối của cạnh trùng với
tọa độ tâm đỉnh được nhấn
c.X1 = c.X2 = temp.X;
c.Y1 = c.Y2 = temp.Y;
// lưu ID đỉnh đầu cạnh = ID đỉnh đang được nhấn
c.P1 = temp.getID;
return;
}
// nếu đang nhấn 1 vị trí “trống”
if (ID <= 14)
{
ID++;
// thêm một đỉnh vào mảng các đỉnh
pList.Add(new dinh(ID, e.X, e.Y));
{
// cập nhật đỉnh cuối của cạnh
c.P2 = temp.getID;
// gọi form nhập độ dài cạnh, trong form đó thực hiện thêm
cạnh đó vào trong mảng các cạnh
Inputbox = new inputBox(new canh(c.X1,
c.Y1, temp.X, temp.Y, c.P1, c.P2, 1));
Inputbox.Show();
break;
}
}
// cho đỉnh đầu đỉnh cuối cạnh trùng nhau (để hiển thị không
bị lỗi)
c.X2 = c.X1; c.Y2 = c.Y1;
drag = false;
pictureBox1.Invalidate();
}
9GvC'a
private void button1_Click(object sender, EventArgs
e)
{
start = true;
richTextBox1.Clear();
map = new bando(pList.Count, cList);
int isp=int.Parse(textBox1.Text);
int iep=int.Parse(textBox2.Text);
dinh ps=new dinh();
dinh pe = new dinh();
foreach (dinh p in pList)
{
Copyright: Tài liệu đại học ©