BÀI TẬP LỚN MÔN TRÍ TUỆ NHÂN TẠO " AKT ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY "

Chia sẻ: Saucaca | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

787
lượt xem 118
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trí tuệ là gì? Theo từ điển Bách khoa toàn thư Webster: Trí tuệ là khả năng: Phản ứng thích hợp lại những tình huống mới thông qua điề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ằm đưa ra những hành vi phù hợp để đạt được mục đích.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI TẬP LỚN MÔN TRÍ TUỆ NHÂN TẠO " AKT ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY "

BÀI TẬP LỚN MÔN: TRÍ TUỆ NHÂN TẠO ĐỀ TÀI: AKT ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY Sinh viên thực hiện: Trịnh Minh Châu. 1. Trần Thị Minh Hải. 2. Nguyễn Bá Nguyện. 3. Vũ Quý Thăng. 4. Phạm Trọng Toàn. 5. Giảng viên hướng dẫn: Ths Trần Hùng Cường. 1
LỜI NÓI ĐẦU....................................................................................................3 Phân tích bài toán................................................................................................4 Mục đích bài toán............................................................................................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ớp khai báo đối tượ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 Hàm xác đ ịnh tọa độ 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ện chương trình ...................................................................................... 19 Tài liệu tham khảo ............................................................................................ 20 2
LỜI NÓI ĐẦU Trí tuệ là gì? Theo từ điển Bách khoa toàn thư Webster: Trí tuệ là khả năng:  Phản ứng thích hợp lại những tình huống mới thông qua điề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ằm đưa ra những hành vi phù hợp để đạt được mục đích. Vậy trí tuệ nhân tạo là gì? Thuật ngữ trí tuệ nhân tạo(Artifical Intellegence) được Jonh McCarthly đưa ra trong hội thảo ở Darthouth vào mùa hè năm 1956. Đã có rất nhiều định nghĩa khác nhau về trí tuệ nhân tạo. Với trí tuệ nhân tạo, máy tính đã giúp con người giải quyết các vấn đề một cách thông minh nhất. Ta s ẽ tìm hiểu một s ố phương pháp giải quyết vấn đề cơ bản. Cụ thể là phương pháp tìm kiếm trong không gian trạng thái với thuật giải AKT . 3
1. P hân tích bài toá n. Mục đích bài toán. 1.1. Giả s ử ta có một đồ thị dạng cây như hình vẽ: A B C D E F G H I J Ta c ần tìm đường đi từ điểm A J. Biết g(n) là chi phí thực từ n0 n. Thuật giải AKT là mở rộng c ủa thuật giải AT bằng cách s ử dụng thêm thông tin ước lượng h(n). Thuật giải AT là thuật giải tìm đường đi tối ưu mà nó chỉ xét đến đỉ 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ột lượng nút lớn(có kích thước bài toán tăng theo hàm mũ từ đó d ẫn đến bùng nổ về tổ hợp) đ ể khắc phục nhược điểm này người ta s ử dụng thêm các thông tin b ổ sung xuất phát từ bản thân bài toán đ ể tìm ra các đ ỉ nh có triển vọng, tức là đường đi tối ưu s ẽ tập trung xung quanh đường đi tốt nhất nếu s ử dụng các thông tin đ ặ tả về bài toán. 4
Vậy theo đ ịnh nghĩa các thông tin này được gọi là các Heuristics: h(n) hay chính là chi phí ước 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ể đưa ra các mẹo giải sau: - Chọn toán tử xây dựng cung sao cho có thể loại bớt các đ ỉ nh không liên quan và tìm ra các đ ỉ 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. Để làm được việc này, người ta phải đưa ra đ ộ đo, tiêu chuẩn đề tìm ra các điểm triển vọng. Các hàm s ử dụng các kỹ thuật này gọi là hàm đánh giá. Sau đây, ta đưa ra một s ố phương pháp xây d ựng hàm đánh giá: - Dựa vào xác suất c ủa đỉ nh trên đường đi tối ưu. - Dựa vào kho ảng cách, s ự sai khác c ủa trạng thái đang xét với trạng thái đích hoặc các thông tin liên quan tới trạng thái đích. Để tìm được phương án tối ưu ta s ử dụng đại lượng hàm ước lượng f(n) và f(n)= g(n)+ h(n) là đ ộ tốt c ủa lời giải. 1.2. Cách làm. Thuật giải AKT Bước 1: Mọi đỉ nh, cũng như các hàm g, h, f chưa biết. - Mở đỉ nh đầu tiên S, gán g(S) = 0 - Sử dụng tri thức bổ sung đ ể ước tính hàm h(S) - - Tính f(S) = g(S) + h(S) Bước 2: Chọn đỉ nh mở có f là nhỏ nhất và gọi là đ ỉ nh N - Nếu N là đích: đường đi từ đỉ nh ban đầu đến đỉ nh N là ngắn nhất và và bằng g(N). Dừng (Success). - Nếu không tồn tại đỉ nh mở nào: cây biểu diễn vấn đề không tồn tại đường đi tới mục tiêu. Dừng (Fail).  Nếu có 2 đ ỉ nh mở trở lên có cùng giá trị f nhỏ nhất: Chúng ta phải kiểm tra xem những đỉ nh đó có đ ỉ nh nào là đích hay không. 5
o + Nếu có: đường đi từ đỉ nh ban đ ầu đến đỉ 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ột trong các đ ỉ nh đó và gọi đỉ nh đó là N. Bước 3: - Đóng đỉ nh N, mở mọi đỉ nh sau N. Với mỗi đỉ nh S sau N, tính: - g(S) = g(N) + cost(S N) - Sử dụng tri thức bổ sung đ ể tính h(S) và f(S): f(S) = g(S) + h(S) Bước 4: - Quay lại bước 2. Thủ tục tìm kiếm: Vào: - Đồ thị G =(N,A) trong đó N là tập đỉ nh, A là tập cung. - f : N  R+ (f là hàm ước lượng). - Đỉ nh đầu là n0 và tập các đ ỉ nh ĐICH. Ra: - Đường đi p: n0  nk ĐICH. ư : Sử dụng 2 danh sách M và D NG {MO = {n0}; tính f(n0) = g(n0) + h(n0) While M ≠ do {n getmoi(MO) // Lấy đỉ nh n sao cho f(n)  min DONG = DONG U{n} DICH then exit (“thành công”) If n If B(n) ≠ then For each m B(n) do 6
If m MO DONG then { MO =MO {m} Tính f(m) } Else if fcu(m) >fmoi(m) then MO = MO {m} } Write(“không thành công”) } 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 7
{ 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ải thích: class này dùng đ ể khai báo các đ ối tượ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 + ser1)
i > 0 && (i + ser2)
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 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) { 10
int f = 0; ArrayList addn = new ArrayList(){ ID,IDcha,ten,g,h,f }; ALLNut.Add(addn); } 4. Hàm xác định tọa độ c ho 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); } } } 11
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) 12
{ 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 ALLNut = new List();//mảng chính List nodeBn = new List(); List MO = new List(); List DONG = new List(); 13
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!"); } 14
Các hàm cho giải thuật 7. //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]
{ 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]; 16
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); } } } 17
//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; } 18
3. sGiao diệ n chương trình 19
Tài liệ u tham khảo Trần Hùng Cường_Giáo trình – slide TRÍ TUỆ NHÂN TẠO(Artificial 1. Intellegence – AI) Geogre F. Luger, William A. Stubblefield – Albuquerque – Artifical 2. Intelligence – Wesley Pubblishing Conpany, Inc – 1997 (Chapter 1) 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 3. trúc và chiện lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần 1) PTS. Nguyễn Thanh Thủy – Trí tuệ nhân tạo – Các phương pháp giải quyết 4. vấn đề và kỹ thuật xử lí tri thức – NXB Giáo dục , 1995 (Chương 1) Wikipedia – Bách khoa to àn thư mở - Lịch s ử ngành Trí tuệ nhân tạo 5. 6. www.codeproject.com 7. www.congdongcviet.com 20