1

BÀI TP LN
MÔN: TRÍ TU NHÂN TO

ĐỀ TÀI: A
KT
ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY Sinh viên thc hin:
1. Trnh Minh Châu.
2. Trn Th Minh Hi.
3. Nguyn Bá Nguyn.
4. 
5. Phm Trng Toàn.

Ging dn: Ths Trng.

2 LU 3
Phân tích bài toán 4
M 4
Cách làm. 5
Cu trúc d liu và cách biu din trng thái ca bài toán 7
Lng 7
Hàm to mu chui nhp vào 8
Hàm x lý chui nhp vào 9
nh t cho các nút v 11

1. Phân tích bài toán.
1.1. Mục đích bài toán.
Gi s ta có m th d: Ta c m A J. Bit g(n) là chi phí thc t n
0
 n.
Thut gii A
KT
là m rng ca thut gii A
T
bng cách s dng thêc
ng h(n).
Thut gii A
T
là thut gi nh và giá ca
chúng (g). Tuy nhiên gii thut này không còn phù hp khi gp phi nhng bài

         d  ng   ng f(n) và
f(n) tt ca li gii.
1.2. Cách làm.
Thuật giải A
KT
c 1:
- Mt.
- M u tiên S, gán g(S) = 0
- S dng tri thc b  c tính hàm h(S)
- Tính f(S) = g(S) + h(S)
c 2: Chnh m có f là nh nht và gnh N
- N nh N là ngn nht và
và bng g(N). Dng (Success).
- Nu không tn tnh m nào: cây biu din v không tn ti
i mc tiêu. Dng (Fail).
 Nnh m tr lên có cùng giá tr f nh nht: Chúng ta phi kim tra
xem nh
6

o + Nng  nh N là ngn nht và bng
g(N). Dng (Success).
o + Nu không có: chn ngu nhiên mnh

c 3:
- nh N, m mnh sau N. Vi mnh S sau N, tính:
- g(S) = g(N) + cost(SN)
- S dng tri thc b  tính h(S) và f(S): f(S) = g(S) + h(S)
c 4:
- Quay lc 2.
Thủ tục tìm kiếm:

7

If m

MO DONG then
{ MO =MO {m}
Tính f(m)
}
Else if f
cu
(m) >f
moi
(m) then MO = MO  {m}
}

}
2. Cấu trúc dữ liệu và cách biểu diễn trạng thái của bài toán
1. Lớp khai báo đối tượng
class Nut
{
protected string _Ten;
private int _G;
private int _H;
protected int _ID;
protected int _IDcha;

public Nut(int id, int idcha, string ten, int g, int h)
{
_ID = id;
_IDcha = idcha;

}

public int IDcha
{
get { return _IDcha; }
set { _IDcha = value; }
}

public Object Tag;

}
Gi ng ca nút
_Ten : Tên nút
_ID : Mã nút
_IDcha : Mã nút cha
_G : g
_H : h

2. Hàm tạo mẫu chuỗi nhập vào
//Tạo một mẫu mặc định
public string TaoCayGia(int maxLen, string title)
{
int ser = 0,ser1=0,ser2=1;
string text = "";
text = "ID\tID Cha\tTên Nut\tG\tH";
text += "\r\n_______\t_______\t_______\t_______\t_______";
for (int i = 0; i < maxLen; i++)
{
ser = rdNumber(maxLen, i, ser);
ser1 = rdNumber(5, i, ser1);

return TaoCayTuChuoi(lines);
}
public TreeNode TaoCayTuChuoi(string[] lines)
{
//Bỏ qua 2 dòng đầu chứa các tiêu đề
if (lines.Length <= 2)
return null;

TreeNode trNodes = new TreeNode();
SortedList<string, TreeNode> sortnodes = new SortedList<string, TreeNode>();

for (int id = 2; id < lines.Length; id++)
{
string line = lines[id];
char[] tab = { '\t' };
//cắt chuỗi ở vị trí tab
string[] chuoi = line.Split(tab, StringSplitOptions.RemoveEmptyEntries);
//cắt khoảng trắng ở đầu cuối các chuỗi
chuoi[0].Trim(); chuoi[1].Trim(); chuoi[2].Trim(); chuoi[3].Trim();
chuoi[4].Trim();

TreeNode curNode = null;
try { curNode = sortnodes[chuoi[0]]; }
catch (Exception) { curNode = null; }

if (curNode == null)
{
curNode = new TreeNode(chuoi[2]);
sortnodes.Add(chuoi[0], curNode);
}

while (nodesEnum.MoveNext())
{
TreeNode node = (TreeNode)nodesEnum.Current.Value;
if (node.Level == 0)
trNodes.Nodes.Add(node);
}

TreeNode lastNode = trNodes.Nodes.Count > 1 ? trNodes : trNodes.Nodes[0];
lastNode.Text = "Đồ thị";
return lastNode;
}
//hàm kiểm tra trùng tên
//public bool kiemtratennut(string ten)
//{
// for (int i = 0; i < ALLNut.Count; i++)
// {
// ArrayList anut = ALLNut[i];
// string str = (string)anut[2];
// if (str == ten)
// {

// MessageBox.Show("Tên nút trùng nhau, xin hãy kiểm tra lại!");
// return true;
// break;
// }
// }
// return false;
//}

//them node vào arraylist chính


public Rectangle vien//hcn kích thước của text
{
get
{
int w = sz.Width + delta;
return new Rectangle(ViTri.X + (w - sz.Width) / 2 - 1, ViTri.Y +
TangY, sz.Width + 1, sz.Height);

}
}
public Point diemDau
{
get
{
Rectangle rect = vien;
return new Point(rect.Left + (rect.Width / 2), rect.Top);
}
}
public Point diemCuoi
{
get
{
Rectangle rect = vien;
return new Point(rect.Left + (rect.Width / 2), rect.Bottom);
}
}
}

12

{
ToaDo b = (ToaDo)((Nut)tnode.Tag).Tag;
TreeNode p = tnode.Parent;
ToaDo pb = (ToaDo)((Nut)p.Tag).Tag;

//Tăng chiều rộng của các nút cha bởi chiều rộng cung cấp
int pbw = pb.sz.Width + pb.delta;
int bw = b.sz.Width + b.delta;
pb.kidsW -= !first ? b.prevW : 0;
pb.delta += ((bw + pb.kidsW - pbw) + Math.Abs(bw + pb.kidsW - pbw)) / 2;
pbw = pb.sz.Width + pb.delta;
pb.kidsW += bw;
b.prevW = bw;
//Điều chỉnh vị trí
if (first)
{
//các nút con được vẽ sau nút cha nên điều chỉnh sẽ chính xác
b.ViTri = new Point(pb.ViTri.X + pb.kidsW - bw, ((tnode.Level - 1) *
kcachtang));
first = false;
}
//
w = Math.Max(pb.ViTri.X + pbw + ToaDo.TangX / 2, w);
h = Math.Max((((tnode.Level - 1) * kcachtang)) + kcachtang, h);
//
tnode = p;
}
if (first && w > tangX)
13

//Vẽ nút
LinearGradientBrush brush = new LinearGradientBrush(rect, Color.White,
Color.DodgerBlue, LinearGradientMode.ForwardDiagonal);
gr.FillEllipse(brush, rect);
gr.DrawEllipse(new Pen(new SolidBrush(Color.Brown)), rect);
//viết tên nút, g,h
using (StringFormat sf = new StringFormat())
{
sf.Alignment = StringAlignment.Center;
sf.LineAlignment = StringAlignment.Center;
gr.DrawString(b.Text, fnt, mau_chu, rect, sf);
}
};
NutLap(node, draw);//lặp lại các nút trong cây
gr.Dispose();
return bmp;
}

6. Hàm giải thuật AKT
public List<ArrayList> ALLNut = new List<ArrayList>();//mảng chính
List<ArrayList> nodeBn = new List<ArrayList>();
List<ArrayList> MO = new List<ArrayList>();
List<ArrayList> DONG = new List<ArrayList>();
14 public int dem = 0;
public void akt_search(string root,string nodesearch,ListView lv)

itemlv = new ListViewItem(root);
lv.Items.Add(itemlv);
itemlv.SubItems.Add(laybn());
itemlv.SubItems.Add(layMO());
itemlv.SubItems.Add(layDONG());
akt_search(laynutMo(), nodesearch, lv);

}
else
{
themDONG(root);
itemlv = new ListViewItem(root);
lv.Items.Add(itemlv);
itemlv.SubItems.Add("Đích");
itemlv.SubItems.Add("");
itemlv.SubItems.Add(layDONG());

}
}

}
else
MessageBox.Show("Không tồn tại nút này!");
}
15 7. Các hàm cho giải thuật
//lấy nút gốc
public ArrayList laygoc()

st=(string)arr1[2];
}
return st;
}
public int lay_min_f()
{

int min = 1000000;
for (int i = 0; i < MO.Count; i++)
{
ArrayList arr1 = MO[i];
min = (int)arr1[5] <= min ? (int)arr1[5] : min;
}
return min;
}

//lấy chuỗi để add vào listview
//
//
//lay ten nut goc
public string layten()
16

{
string ten = "";
ArrayList ar = laygoc();
ten = (string)ar[2];
return ten;
}
//lay cac nut trong bn

string ten = (string)nut[2];
st += ten + "(F= " + nut[5].ToString() + ") ";
}
return st;
}

//tính F của các nút
//
public void tinhF_Bn()
{
for (int i = 0; i < ALLNut.Count; i++)
{
ArrayList root = ALLNut[i];
if ((int)root[1] == 0) root[5] = root[4];
for (int j = 0; j < ALLNut.Count; j++)
{
ArrayList rootchild = ALLNut[j];
int idcha = (int)rootchild[1];
if (idcha == (int)root[0])
{
rootchild[3] = (int)root[3] + (int)rootchild[3];
17

rootchild[5] = (int)rootchild[3] + (int)rootchild[4];
}
}
}
}

//Thêm các phần tử vào các mảng con Bn,MO,DONG

MO.Add(nodeBn[i]);
}
}

//thêm phần tử vào MO nếu chưa có phần tử nào
public void themMO(ArrayList n)
{
MO.Add(n);
}

public void themDONG(string nutduyet)
{
for (int i = 0; i < ALLNut.Count; i++)
{
ArrayList ar = ALLNut[i];
if (nutduyet == (string)ar[2])
{
DONG.Add(ar);
}
}
}
18
//kiểm tra tồn tại nút
//
public bool Tontainut(string nuttim)
{
for (int i = 0; i < ALLNut.Count; i++)

if ((int)az[0] == (int)nuts[1])
{
if ((int)az[1] == 0)
{
st = String.Concat(az[2].ToString(), s1, nuts[2].ToString(),
st);
}
else
{
st = String.Concat(s1, nuts[2].ToString(), st);
}

s = (string)az[2];
duongdi_chiphi(s);
}
}
}
}
return st;
}
19

3. sGiao diện chương trình
20 Tài liệu tham khảo