Hướng dẫn thuật toán akt python

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.

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

Hàm v  th 12
Hàm gii thut AKT 13
Các hàm cho gii thut 15
Giao di 19
Tài liu tham kho 20

LỜI NÓI ĐẦU
Trí tu là gì?
Theo t 
Trí tu là kh 
 Phn ng thích hp li nhng tình hung mu chnh hành vi
mt cách thích hp.
 Hiu rõ mi liên h gia các s kin ca th gii bên ngoài nh 
nhng hành vi phù h c m
Vy trí tu nhân to là gì?
Thut ng trí tu nhân t      
trong hi tho  t nhi
nhau v trí tu nhân to. Vi trí tu nhân t      i gii
quyt các v mt cách thông minh nht. Ta s tìm hiu mt s 
gii quyt v n. C th m trong không gian trng
thái vi thut gii A
KT
.

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

toán phc tp do phi tháo mng nút ln(c
 n bùng n v t h khc phi ta s
dng thêm các thông tin b sung xut phát t b nh
có trin vng, t tp trung xung quanh t nht nu
s d t v bài toán.
A
B
C
D
G
E
F
I
H
J
5

Vc gi là các Heuristics: h(n) hay chính là
ng t n  G.
Các k thut s dng h(n) gi là các mo gii, ta có th o gii sau:
- Chn toán t xây dng cung sao cho có th loi bnh không liên
nh có trin vng.
- S dng thêm các thông tin b sung nhm xây dng tp MO và cách ly các
nh trong tp MO.
 c vii ta ph , tiêu chu m
trin vng. Các hàm s dng các k thut này g
ra mt s 
- Da vào xác sut c
- Da vào khong cách, s sai khác ca trt vi tr
hoc các thông tin liên quan ti tr

         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:

Vào:
-  th nh, A là tp cung.
- f : N  R
+
ng).
- u là n
0
và t
Ra:
- 
0
 n
k
 
: 
{MO = {n
0
}; tính f(n
0
) = g(n
0
) + h(n
0
)
 do
{n getmoi(MO) // Lnh n sao cho f(n)  min
DONG = DONG U{n}
If n 
If  then
For each m  B(n) do

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;

_G = g;
_H = h;
_Ten = ten;
}

public string Ten
{
get { return _Ten; }
set { _Ten = value; }
}

public int G
{
get { return _G; }
set { _G = value; }
}

public int H
8

{
get { return _H; }
set { _H = value; }
}

public int ID
{
get { return _ID; }
set { _ID = value; }

}

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);

ser2 = rdNumber(58, i, ser2);
text += string.Format("\r\n{0}\t{1}\t{2}{0}\t{3}\t{4}", i + 1, i > 0 && (i +
ser) <= 0 ? i : (i + ser), title,
i > 0 && (i +
ser1) <= 0 ? i : (i + ser1),
9

i > 0 && (i +
ser2) <= 0 ? i : (i + ser2));
}
return text;
}
//tạo lấy số
private int rdNumber(int max, int i, int last)
{
int avr = max / 2;
int mod = i % avr;
int range = (mod - i) / avr;
last += (range + (last % 2));
return last;
}

3. Hàm xử lý chuỗi nhập vào
//Xử lý chuỗi nhập vào
public TreeNode TaoCayTuChuoi(string text)
{
//loại bỏ các ký tự xuống dòng
string[] lines = text.Split(new char[] { '\r', '\n' },
StringSplitOptions.RemoveEmptyEntries);
//trả về mảng chuỗi vẫn còn các ký tự tab

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);
}

curNode.Text = chuoi[2];
//them nut
10

curNode.Tag = new Nut(int.Parse(chuoi[0]), int.Parse(chuoi[1]),
curNode.Text, int.Parse(chuoi[3]), int.Parse(chuoi[4]));

//kiểm tra trùng tên
//if (kiemtratennut(chuoi[2])) break;

// thêm vào mảng
addnode(int.Parse(chuoi[0]), int.Parse(chuoi[1]), curNode.Text,
int.Parse(chuoi[3]), int.Parse(chuoi[4]));

//
TreeNode parentNode = null;
try { parentNode = sortnodes[chuoi[1]]; }
catch (Exception) { parentNode = null; }

if (parentNode == null)
{
parentNode = new TreeNode(chuoi[1]);
sortnodes.Add(chuoi[1], parentNode);
}
parentNode.Nodes.Add(curNode);
}

IEnumerator<KeyValuePair<string, TreeNode>> nodesEnum =
sortnodes.GetEnumerator();
nodesEnum.Reset();

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

private void addnode(int ID, int IDcha, string ten, int g, int h)
{
11

int f = 0;
ArrayList addn = new ArrayList(){
ID,IDcha,ten,g,h,f
};
ALLNut.Add(addn);

}

4. Hàm xác định tọa độ cho các nút vẽ
//tọa độ
public class ToaDo
{
public ToaDo(Object tag)
{
Tag = tag;
}
public Size sz;//text size
public string Text;
public Object Tag;//Tham chiếu đến đối tượng liên quan
public static Font font = new Font("Times New Roman", 9);
public static int KCgiuaTang = 60;
public static int TangX = 10;
public static int TangY = 10;
public int delta = 0, kidsW = 0, prevW = 0;
public Point ViTri = new Point(0, 0);

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);
}
}
}

5. Hàm vẽ đồ thị
//Vẽ cây
//
public Bitmap VeCay(TreeNode node)
{
int tangX = ToaDo.TangX, kcachtang = ToaDo.KCgiuaTang, w = ToaDo.TangX, h =
ToaDo.KCgiuaTang;
Font fnt = ToaDo.font;

Bitmap bmp = new Bitmap(w, h);
Graphics gr = Graphics.FromImage(bmp);
//vẽ nút
LayNutCay laynut = (tnode) =>
{
Boolean first = true;

ToaDo cb = new ToaDo(tnode);
((Nut)tnode.Tag).Tag = cb;

cb.Text = " g= " + ((Nut)tnode.Tag).G.ToString() + "\n " + tnode.Text +
"\n h= " + ((Nut)tnode.Tag).H.ToString();

cb.sz = Size.Ceiling(gr.MeasureString(cb.Text, fnt));
cb.delta = tangX;//tăng chiều rộng bởi thêm các nút con

cb.ViTri = new Point(tangX / 2, ((tnode.Level - 1) * kcachtang));
//vòng lặp
while (tnode.Parent != null && tnode.Parent.Tag != null)

{
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

{
cb.ViTri.Offset(w, 0);
w = Math.Max(cb.ViTri.X + cb.sz.Width + cb.delta, w);
}
};
NutLap(node, laynut);//lặp lại các nút để lấy tọa độ các nút
gr.Dispose();
bmp.Dispose();

bmp = new Bitmap(w, h);
gr = Graphics.FromImage(bmp);
LayNutCay draw = (tnode) =>
{
Brush mau_nut = new SolidBrush(Color.Ivory);
Brush mau_chu = new SolidBrush(Color.Black);
Brush mau_trang = new SolidBrush(Color.White);

Nut mpttNode = (Nut)tnode.Tag;
int level = tnode.Level;
ToaDo b = (ToaDo)((Nut)tnode.Tag).Tag;
Rectangle rect = b.vien;
//Vẽ nhánh
if (tnode.Parent.Tag != null)
{
gr.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;
Pen pen = new Pen(new SolidBrush(Color.Red), 1.0F);
gr.DrawLine(pen, ((ToaDo)((Nut)tnode.Parent.Tag).Tag).diemCuoi,
b.diemDau);
}

//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)

{
if (dem == 0)
{
tinhF_Bn();
dem++;
}
ListViewItem itemlv;
if (Tontainut(nodesearch))
{
if (root == "")//nếu chưa có nút nào mở thì thêm nút gốc
{
themMO(laygoc());

itemlv = new ListViewItem(root);
lv.Items.Add(itemlv);
itemlv.SubItems.Add("");
itemlv.SubItems.Add(layMO());
itemlv.SubItems.Add("");
akt_search(laynutMo(), nodesearch, lv);
}
else
{
if (root != nodesearch)
{
daduyet(root);//xóa nút ra khỏi MO

themBn(root);
themMO();
themDONG(root);

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()

{
ArrayList goc = null;
for (int i = 0; i < ALLNut.Count; i++)
{
ArrayList node = ALLNut[i];
if ((int)node[1] == 0)
return node;
}
return goc;
}

//xóa nút đã duyệt khỏi MO
public void daduyet(string tennut)
{
for (int i = 0; i < MO.Count; i++)
{
ArrayList ar = MO[i];
if ((string)ar[2]==tennut)
MO.RemoveAt(i);
}
}

//Lấy tên nút có F nhỏ nhất trong MO
public string laynutMo()
{
string st = "";
for (int j = 0; j < MO.Count; j++)
{
ArrayList arr1 = MO[j];
if ((int)arr1[5] == lay_min_f())

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

public string laybn()
{
string st="";
for (int i = 0; i < nodeBn.Count; i++)
{
ArrayList nut = nodeBn[i];
string ten = (string)nut[2];
st += ten + "(F= " + nut[5].ToString() + ")\r\n";
}
return st;
}
//lay cac nut trong MO
public string layMO()
{
string st = "";
for (int i = 0; i < MO.Count; i++)
{
ArrayList nut = MO[i];
string ten = (string)nut[2];
st += ten + "(F= " + nut[5].ToString() + ")\r\n";
}
return st;
}
//lay cac nut trong DONG
public string layDONG()
{
string st = "";
for (int i = 0; i < DONG.Count; i++)
{
ArrayList nut = DONG[i];

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

public void themBn(string nut)
{
//xóa sạch bn
nodeBn.Clear();
for (int i = 0; i < ALLNut.Count; i++)
{
//lấy nút n
ArrayList anut = ALLNut[i];
string tennut = (string)anut[2];
if (tennut == nut)//nếu phần tử trong mảng có tên là n
{
for (int j = 0; j < ALLNut.Count; j++)
{//thêm vào bn phần tử từ mảng gốc
ArrayList node = ALLNut[j];
int idcha = (int)node[1];
if (idcha == (int)anut[0])
{
nodeBn.Add(node);
}
}
}
}

}

public void themMO()
{
//MO sẽ thêm từ Bn
for (int i = 0; i < nodeBn.Count; i++)
{

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++)

{
ArrayList anut = ALLNut[i];
string str = (string)anut[2];
if (str == nuttim)//nếu có phần tử nào trong mảng đầu có tên trùng
{
return true;
}
}
return false;
}
//Hàm lấy đường đi và chi phí

public int f=0;
string st = "";

public string duongdi_chiphi(string nodesearch)
{
string s1=" > ";
string s = nodesearch;
//ArrayList az;
for (int i = 0; i < ALLNut.Count; i++)
{
ArrayList nuts = ALLNut[i];
if (s == (string)nuts[2])
{
if (f == 0) f = (int)nuts[3];
for (int j = 0; j < ALLNut.Count; j++)
{

ArrayList az = ALLNut[j];

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

Tài liệu tham khảo

1. Trng_Giáo trình  slide TRÍ TU NHÂN TO(Artificial
Intellegence  AI)
2. Geogre F. Luger, William A. Stubblefield  Albuquerque  Artifical
Intelligence  Wesley Pubblishing Conpany, Inc  1997 (Chapter 1)
3. Bùi Xuân Toi  Trng Gia Vit (Biên dch)  Trí tu nhân to  Các cu
trúc và chin lc gii quyt vn  - NXB Thng kê, 2000 (Phn 1)
4. PTS. Nguyn Thanh Thy  Trí tu nhân to  Các phng pháp gii quyt
vn  và k thut x lí tri thc  NXB Giáo dc, 1995 (Chng 1)
5. Wikipedia  Bách khoa toàn th m - Lch s ngành Trí tu nhân to
6. www.codeproject.com
7. www.congdongcviet.com