Đề tài : Thuật toán Mentor II

ĐẠI HỌC BÁCH KHOA HÀ NÔI VIỆN ĐIỆN TỬ - VIỄN THÔNG Đề tài: THUẬT TOÁN MENTOR II Giảng viên hướng dẫn: Trần Ngọc Lan Sinh viên thực hiên: 1. Lê Thái Hưng KSTN-ĐTVT-K52 2. Trần Hữu Cương KSTN-ĐTVT-K52 3. Phạm Văn Chí KSTN-ĐTVT-K52 4. Bùi Thị Thế Hà KSTN-ĐTVT-K52 Hà Nội, tháng 11 năm 2011 2 Mục Lục 1. Giới Thiệu ................................................................................................................................................. 3 YÊU CẦU CỦA BÀI TẬP ........................................................................................................................... 5 2. Lý thuyết ................................................................................................................................................... 6 2.1 Thuật toán Mentor ......................................................................................................................... 6 2.1.1 Xác định node backbone và node trung tâm ......................................................................... 6 2.1.2 Chuyển yêu cầu node sang xương sống. ............................................................................... 7 2.1.3 Xây dựng cây Prim-Dijkstra với tham số α........................................................................... 8 2.2 Thuật toán Mentor II ..................................................................................................................... 8 2.2.1 Đặt vấn đề .................................................................................................................................... 8 2.2.2 ISP(Incremental Shortest Path) ............................................................................................. 9 3. Triển khai thuật toán ........................................................................................................................... 13 3.1. Tổng quan về kiến trúc .................................................................................................................... 13 3.2. Xây dựng đồ thi cơ sở ...................................................................................................................... 13 3.2.1 Class Node ................................................................................................................................. 13 3.2.2 Class Arc ................................................................................................................................... 14 3.2.3. Class Graph ............................................................................................................................... 14 3.3. Thuật toán ................................................................................................................................... 15 3.3.1 classMentor ......................................................................................................................... 15 3.3.2 Class Prim – Dijkstra .......................................................................................................... 16 3.3.3 Class Floyd – Warshall ...................................................................................................... 16 3.3.4 Class ISP ............................................................................................................................. 16 3.4. Form chính ....................................................................................................................................... 18 4 Kết luận ............................................................................................................................................... 21 3 1. Giới Thiệu Như ta đã biết, “viễn thông” được hiểu là cách trao đổi dữ liệu thông qua kỹ thuật điện, điện tử và các công nghệ hiện đại khác. Và “hệ thống viễn thông” là tập hợp các trang thiết bị kỹ thuật để cung cấp dịch vụ viễn thông cho người sử dụng. Ngay từ ngày xa xưa, những người tiền sử đã biết dùng khói để báo hiệu, những người thổ dân ở những hòn đảo xa xôi dùng các cột khói để liên lạc, báo hiệu và truyền tin. Nhưng “viễn thông” được chính thức sử dụng khi con người phát minh ra điện báo và điện thoại. Công nghệ viễn thông từ đó ngày càng phát triển nhanh chóng và vượt bậc, ứng dụng trong mọi lĩnh vực. Trên quy mô xã hội, viễn thông đã làm nên một hệ thần kinh thông minh nhạy bén trên trái đất, làm thay đổi bộ mặt, tính cách của từng quốc gia và tự trong nó hình thành lên một mạng lưới liên kết mỗi người của mỗi quốc gia trên trái đất. Sự hội tụ công nghệ trong lĩnh vực viễn thông cùng sự phát triển tăng trưởng mạnh của kinh tế - xã hội, nhu cầu sử dụng cũng như truyền dữ liệu của con người cũng tăng lên theo hàm số mũ và ngày càng trở nên phức tạp, có khuynh hướng kỹ thuật cao với chất lượng cao. Vì vậy, việc tổ chức một mạng viễn thông đáp ứng được nhu cầu ấy và phát triển tổ chức mạng lưới này thành một thành phần cơ bản quan trọng của xã hội thông tin hóa cao trong tương lai nữa là không hề đơn giản, nó đóng một vai trò rất quan trọng. Để giải quyết bài toán trên, ta nhìn hệ thống viễn thông trên cả phương diện phần cứng và phần mềm:  Về phương diện phần cứng, hệ thống viễn thông gồm các thiết bị như: Thiết bị đầu cuối thông tin, thiết bị chuyển mạch, thiết bị truyền dẫn.  Về phương diện phần mềm, hệ thống viễn thông cho biết các phần cứng liên hệ với nhau thế nào ( Topo mạng, với topo mạng ta sẽ phân biệt được mạng AN(Access Network) và mạng lõi), các giao thức mạng, các giao thức để liên kết, giao thức để trao đổi thông tin (giữa hai giao thức này có thể tách rời, có thể kết hợp với nhau), quản lý và khai thác mạng. Trên phương diện phần mềm, để xây dựng mạng, ta phải xây dựng được cấu hình của các phần tử mạng. MENTOR (Mesh Network Topology Optimization Routing) là một thuật toán rất hữu ích cho việc thiết kế mạng thông tin vì nó không phụ thuộc vào đặc điểm của bất kỳ một công nghệ hay kiến trúc mạng nào. Nó chỉ phụ thuộc vào nguyên tắc thiết kế mạng. MENTOR có thể ứng dụng cho nhiều loại mạng, đặc biệt là mạng ATM (Asynchronous Transfer Mode). Và chương trình MENTOR là một ứng dụng tin học trong việc thiết kế Topology cho mạng bằng chính thuật toán MENTOR. 4 Trong đề tài này yêu cầu chúng em viết một chương trình MENTOR như thế. Chương trình chúng em viết trong thời gian ngắn và kiến thức có hạn nên có rất nhiều những hạn chế nhất định như chỉ có tính chất mô phỏng, các giả thiết, điều kiện chưa hoàn toàn giống với yêu cầu thực tế. Tuy nhiên, chúng em hy vọng chương trình này cũng giúp mọi người nắm được quá trình xây dựng Topology cho mạng. Trong quá trình thực hiện bài tập lớn, chúng em xin cảm ơn sự tận tình giúp đỡ của cô Trần Ngọc Lan đã giúp chúng em hoàn thành bài tập này. Chúng em rất mong nhận được những lời khuyên từ thầy để chúng em có thể khắc phục được những cái chưa làm được trong đề tài để chúng em có thể hiểu sâu sắc hơn về thuật toán cũng như chương trình MENTOR trong xây dựng Topology cho mạng viễn thông, đồng thời hiểu rõ hơn về môn học Tổ chức và quy hoạch mạng viễn thông. Chúng em xin chân thành cảm ơn cô! 5 YÊU CẦU CỦA BÀI TẬP Viết một phần mềm tạo topology mạng viễn thông theo thuật toán MENTOR 2. nn : Số lượng nút trong mạng: Cost: Chi phí kết nối giữa các nút là một ma trận [nxn] Req: Ma trận [nxn] yêu cầu Pc, W, R/D: Các tham số xác định nút BackBone α: Tham số xác định cây γ : Hệ số sử dụng băng thông Cmax [nxn]: Giá trị tối đa dung lượng của liên kết giữa các nút( hiệu dụng) - Tìm cây kết nối các nút, α cho biết cây là dạng MST hay PST, MENTOR. - Tổng chiều dài cây, chiều dài đường đi - Direct link: Tìm kết nối Direct link - Đường đi trên cây Tất cả thể hiện trên màn hình đồ họa. 6 2. Lý thuyết 2.1 Thuật toán Mentor 2.1.1 Xác định node backbone và node trung tâm Xác định MAXCOST Xác định node backbone thoả mãn điều kiện nw(i) > w Xác định node truy cập của node backbone đã xác định Tìm node trung tâm của node chưa phân loại, tính merrit từ đó tìm node backbone trong tập chưa xác định đó, cập nhật lại danh sách backbone và node truy cập Tính moment rồi xác định node root Bắt đầu Mentor Kết thúc Hình 2.2.1 Lưu đồ thuật toán xác định node backbone Bước 1: xác định node backbone thỏa mãn tiêu chuẩn trọng số: + Trọng số của một node là tổng của tất cả các lưu lượng vào và ra node + Trọng số chuẩn hóa dựa vào node i là NW(i) = W(i) / C +W là tham số + Node có NW(i) > W được chọn làm node xương sống Bước 2: xác định MAXCOST + MAXCOST = maxi,j cost(Ni,Nj) = maxi,j Bước 3: Xác đinh node truy cập của node backbone đã xác định + Tất cả các node không thảo mãn tiêu chuẩn trọng số và “gần” node xương sống sẽ được chọn làm node truy cập 7 + “ gần ” được định nghĩa là khi giá liên kết từ node truy cập “e” đến node xương sống là nhỏ hơn một phần của giá liên kết lớn nhất. cost(e,Ni) < MAXCOST * RPARM, hay < MAXCOST * RPARM. Bước 4: xác đinh node backbone và truy cập cho những node còn lại thuộc tập M + Tìm trung tâm của trọng lực (xctr, yctr). - xctr = - yctr = + Khoảng cách tới CG - dcn = - maxdc = max(dcn) - maxW = max (Wn) + Tính merit - merritn = + Phân loại các node còn lại - “merrit” đưa ra giá trị cân bằng giữa vị trí gần trung tâm và trọng số của nó. - Trọng số những node chưa được phân loại, chọn node có thưởng cao nhất và chuyển node này thành node xương sống. - Phân loại các node mới thành các node truy cập. - Cứ tiếp tục cho đến khi tất cả các node được phân loại. Bước 5: Tìm node trung tâm + lựa chọn node xương sống trung tâm với giá trị moment nhỏ nhất đến trung tâm - Moment(n) = 2.1.2 Chuyển yêu cầu node sang xương sống. 8 + xét ei là node truy cập của node bi, bi là node trước trong cây. Ví dụ xét e1,e2,b1và b2 nếu b1 = b2 thì không chuyển yêu cầu của e1 và e2 sang b1 và b2, và ngược lại. Hình 2.1.2 ví dụ về chuyển yêu cầu 2.1.3 Xây dựng cây Prim-Dijkstra với tham số α + các node đầu vào là node backbone đã xác định ở trên và root là node trung tâm. + Thuật toán: - Nhãn Prim = minneighbors dist(node, neighbor) - Nhãn Dijkstra = minneighbors [dist(root, neighbor) + dist(neighbor, node)] - Nhãn Prim-Dijkstra = minneighbors [α* dist(root, neighbor) + dist(neighbor, node)] 2.2 Thuật toán Mentor II 2.2.1 Đặt vấn đề Sau khi chúng ta thiết kế xong mạng, chúng ta xem xét xem lưu lượng sẽ đi qua đâu. Đưa ra một vấn đề mà trung tâm chính là chất lượng hoạt động của thuật toán định tuyến. Nếu chỉ sử dụng thuật toán Prim – Dijkstra, số lượng liên kết là ít nhất mà vẫn đảm bảo có một và chỉ một đường đi duy nhất giữa 2 node bất kì. Tuy nhiên với thiết kế như thế, sẽ tồn tại những liên kết mà lưu lượng đi qua nó rất lớn, điều đó đồng nghĩa với việc không đảm bảo tính ổn định cho mạng 9 Hình 2.2.1ví dụ mạng backbone sau mentor 1 Như hình vẽ trên, ta có thể thấy liên kết giữa node 8 và 9 có lưu lượng đi qua lớn do yêu cầu từ các các node backbone 9, 2, 14 đến node backbone 8, 4. Trong khi đó, liên kết giữa 2 node 2 và 14 lại ít do chỉ có các yêu cầu đi từ node 14 đến các node còn lại. Để khắc phục điều này, chúng ta có thể thêm các liên kết trực tiếp giữa các node. Ví dụ, node 14 và node 4. Như vậy, một số yêu cầu từ một số node (VD: node 2, 14) sẽ đi qua liên kết mới này. Tuy nhiên, nếu thêm các liên kết trực tiếp này thì khả năng một số liên kết đã có từ trước sẽ giảm lưu lượng (VD: trong trường hợp này là liên kết 9 – 8, 9 – 2) đôi lúc lưu lượng này trở về 0. Hay nói cách khác, thuật toán định tuyển sẽ tìm thấy đường đi ngắn nhất nhưng đường đi đó có thể không tìm thấy đường khả thi cho thiết kê mạng của chúng ta. Như vậy, cần cải thiệt giải thuật mentor thêm các liên kết trực tiếp nhưng vẫn phải xem xét luôn đến giới hạn của thuật toán đinh tuyển. Kết quả là thuật toán Mentor II ra đời. 2.2.2 ISP(Incremental Shortest Path) 10 Đây là bước cải tiến để đáp ứng phần nào yêu cầu đã trình bày ở trên. Mục đích của thuật toán ISP là xác định tất cả những cặp có thể sử dụng liên kết trực tiếp thay cho đường hiện thời. Bắt đầu Xác định sp_dist[][], sp_pred[][]. i=0;S(i) J=0;D(j) i< numBackbone j< numBackbone Xác định S_list && D_list Cập nhật sp_dist[][] && sp_pred[][] Tính maxL[n][m] Sắp xết theo thứ tự giản dần các cặp có maxL[n][m] > D J++ i++ Kết thúc + Đầu vào là các thông số kết thúc thuật toán Mentor no yes no yes ISP Hình 2.2.2 lưu đồ thuật toán ISP 2.2.2.1 Ma trận khoảng cách – thuật toán Floyd Warshall Để thực hiện điều này ta cần có 2 ma trận 11 Khoảng cách đường ngắn nhất Shortest-path distances giữa 2 node i, j(sp_dist)nxn Ma trận con trỏ node trên đường đi ngắn nhất giữa 2 node i, j(sp_pred)nxn Hai ma trận này luôn được cập nhật sau mỗi lần thêm liên kết. Cách xây dựng ma trận này với đồ thị bất kì rất giống trong thuật toán Floyd – Warshall Hình 2.2.2.1 ví dụ xây dựng sp_dist[][] và sp_pred[][] 2.2.2.2 Thứ tự xem xét các cặp cạnh Chúng ta sắp xết các cặp cạnh theo thứ tự bước nhảy. Và coi đó là thứ tự cần xét xem có thêm liên kết trực tiếp hay không Hình 2.2.2.2 ví dụ về sắp xếp các cạnh theo thứ tự 2.2.2.3 Xét cạnh thêm vào Khi xem xét liệu có thêm liên kết trực tiếp giữa node nguồn S và node đích D độ dài liên kết SD = L. ta xây dựng s_list và d_list o s_list với ý nghĩa tập node “được hưởng lợi” nếu muốn đi đến node khác nếu dùng liên kết trực tiếp SD 12 o d_list với ý nghĩa tập node “được hưởng lợi” nếu muốn đi đến node khác nếu dùng liên kết trực tiếp DS Với ý nghĩa như trên, cách xây dựng s_list và d_list như sau: o Thêm node vào s_list nếu: sp_dist[node, s] + L < sp_dist[node, d] o Thêm node vào d_list nếu: sp_dist[node, d] + L < sp_dist[node, s] Hình 2.2.2.3 ví dụ xây dựng s_list[] và d_list[] Xem xét tất cả các cặp (ni, nj) trong đó ni thuộc s_list và nj thuộc d_list. Khi đó, lưu lượng (ni, nj) sẽ chuyển sang liên kết dự định nếu sp_dist[ni, s] + L + sp_dist[d, nj] < sp_dist[ni, nj] Độ dài lớn nhất cho có thể ấn định lưu lượng (ni, nj) để chuyển đi theo đường này là maxL = sp_dist[ni, nj] - sp_dist[ni, s] + sp_dist[d, nj] Điều này có nghĩa là nếu đo dài liên kết (ni, nj) ấn định trong khoảng (L, maxL) thì lưu lượng sẽ chuyển đi theo đường đi SD mới này Với mỗi cặp (ni, nj) ta sẽ có số maxL. Ta sắp xếp các cặp này theo thứ tự từ trên xuống maxL(P1) = 2000 maxL(P2) = 1800 maxL(P3) = 1800 maxL(P4) = 1700 Ở đây, nếu chọn giá trị cạnh là bao nhiêu sẽ quyết định có bao nhiêu cặp (ni, nj) có thể sử dụng liên kết này. Ví dụ SD = 1750 thì có các cặp P1, P1, P3 sẽ dùng liên kết mới này. 13 3. Triển khai thuật toán 3.1. Tổng quan về kiến trúc 3.2. Xây dựng đồ thi cơ sở 3.2.1 Class Node + Thuộc tính: o public const int isRoot = -1; o public const int unknown = -2; o public const int drawIndex = 0x10; o public const int drawWeigh = 0x20; // thong so co ban o public int index; // thu tu node o public int x, y; // toa do o public double weigh; // trong luong nut o public int priority; // >=0 neu la nut truy nhap, = index la backbone, -1 neu la goc, - neu chua xac dinh // Ket noi voi cac nut khac o public int numNode; o public List otherNodes; o public List send, recv; o public List distance; o public List connected; + Operator: o public Node(int _index, double _weigh, int _priority = Node.unknown, int _x = 0, int _y = 0, int _numNode = 0, List _otherNodes = null,  List _send = null, List _recv = null, List _distance = null, List _connected = null) {} //hàm tạo o public bool IsOne(Node other, int r = 50) {} o public void SetPosition(int _x, int _y) {} o public double GetDistance(Node Other) {} // Lấy tọa độ thực trên Decac(chưa bị thay đổi bởi mentor) o public void ConnectNodes(Node Other) // chi dung trong ham CreateNodes. nhu vay se dung thu tu luon - chu y la no phai connet voi chinh minh o public void DrawNode(Graphics Grfx, int draw, double div = 2, int r = 7) {} //vẽ node // Hàm này sẽ hiển thị node với màu sắc của node và số thứ tự tương ứng với node 14 3.2.2 Class Arc + Thuộc tính: o public Node destination, source; //so thu tu 2 diem source, destination o public double distance; //do dai canh: distance o public double c; //dung luong 1 lien ket o public double ratio; //dung luong cuc dai ung voi moi lien ket (tinh theo %) o public double capacity; //dung luong tren canh nay voi moi lien ket capacity = c * ratio = 2 * 60% o public double flow; //tong luu luong tren canh nay: flow o public int paths; //so luong lien ket song song: paths o public int priority; o public const int drawDist = 0x01; o public const int drawCap = 0x02; o public const int drawFlow = 0x04; o public const int drawPaths = 0x08; + Operator: o public Arc(Node _source, Node _destination, double _flow = 0.0, double _c = 2.0, double _ratio = 0.6, int _priority = Node.unknown) {} // hàm tạo o public void DrawArc(Graphics Grfx, int div = 2) {} // vẽ cạnh o public void DrawParameter(Graphics Grfx, int draw, int div = 2, int r = 8) {} //vẽ cạnh, hiển thi các thông số cạnh 3.2.3. Class Graph + Thuộc tính: o const int MAX_X = 1500, MAX_Y = 1500; o public List LN; o public List LA; o public int numNode = 0, numArc = 0; o public double cost = 0.0; o public int root = -1; o private Random rd = new Random(); + Operator: o public Graph(){} // hàm tạo 15 o public void CreatNodes(int _numNode) {} // Khởi tạo node trên mặt phẳng tọa độ cùng các tham số tương tự class node o public void AddNode(Node node) {} // Thêm node mới vào đồ hình o public void ChangeDistNode(Node n1, Node n2, double dist) {} //Thay đổi khoảng cách giữa các node o public void DeleLightBluelArcs() {} o public void AddArc(Arc arc) {} o public void AddArc(Node source, Node destination, double flow = 0.0) {} // Thêm cạnh với các tham số cạnh: node nguồn, node đich, flow o public void ChangeFlowArc(Arc arc, double flow) {} // Thay đổi flow o public void ChangePriorityArcs() {} o public void DrawPath(Graphics Grfx, List nodes, int div = 2) {} // vẽ cạnh o public void CopyFromGraph(Graph _graph) {} o public void CopyToGraph(Graph _graph) {} o public void AllCopyFromGraph(Graph _graph) {} // copy toàn bộ graph tới từng vùng nhớ o public void ClearGraph() {} o public double TotalCost() {} // Tính tổng cost o public void DrawGraph(Graphics Grfx, int draw, int div = 2) {} o protected int Compare(Arc x, Arc y){} // so sánh các cạnh o public void SortDistArc(List Arcs){} // sắp xếp các cạnh 3.3. Thuật toán 3.3.1 classMentor + Kế thừa từ class Graph + Thuộc tính o private double[] merit; o private double[] moment; o private double[] dc; o private double W; o private double C; o private double R; o private double MAXCOST = 0; + Operator o private void FindAcessNode(Node node) {} 16 //chua add canh nhe. moi chi chinh nut truy cap thoi o public void Process(Graph _graph, double _W = 4.0, double _C = 2.0, double _R = 0.3) {} // hàm này có là xác định node backbone và node trung tâm o public Mentor(){} // hàm tạo 3.3.2 Class Prim – Dijkstra + Thuộc tính: o private int[] convertIndex; //anh xa nguoc. tu index cua node => thu tu luu trong List node (chu y la gio no khong theo thu tu) o const int vc = 2000000000; o private double alpha; o private int start; o private double[] label; o private bool[] free; o public double[] dist; o public int[] pred; + Operator: o public PrimDijkstra() {} // Thuật toán chính 3.3.3 Class Floyd – Warshall Tìm đường đi ngắn nhất, giữa 2 node bất kì, lưu vào mảng sp_dist, lưu lại truy vết sp_pred và số node để đi tới node đích sp_hop. + Thuộc tính: o private int[] convertIndex; //anh xa nguoc. tu index cua node => thu tu luu trong List node (chu y la gio no khong theo thu tu) o const double vc = 2000000000.0; o private double[,] sp_dist; o private int[,] sp_pred; o private int[,] sp_hop; +Operator: o public void Process(Graph _graph, double[,] _sp_dist, int[,] _sp_pred, int[,] _sp_hop){} //Thủ tục xử lý xử lý chính, thao tác trên đồ thị graph. //Lưu giá trị trả về _sp_dist, _sp_pred, _sp_hop 3.3.4 Class ISP Triển khai thuật toán ISP: 17 + Thuộc tính: o private int[] convertIndex; //anh xa nguoc. tu index cua node => thu tu luu trong List node (chu y la gio no khong theo thu tu) o private List findArc; o private double[,] sp_dist; o private int[,] sp_pred; o private int[,] sp_hop; o private List d_list; o private List s_list; o private List req_len; o private double esilon = 0.001; o private double d; // = 1.0 neu muon cho qua 100%. o private double alpha; o private double[,] NA; o double[] LW; o public int maxNumberOfAdd = 0; o private int numberOfAdd = 0; + Operator: o private bool ChangedDistArc(Arc arc) {} //Đặt giá trị cho cạnh (ni, nj) o public void UpdatePath(int src, int des, double flow){} //Trên đường đi từ node ni đến node nj thì tất cả các cạnh được update lưu lượng mới, các đỉnh được update trọng số mới o public void UpdateFlowGraph(){} //Update tất cả các cặp (ni, nj). Thủ tục này sẽ gọi void UpdatePath o private int CompareHop(Arc x, Arc y){} //So sánh các cặp đỉnh (ni, nj) theo số lượng bước nhảy o public void Process(Graph _graph, double _alpha = 0.4, double _d = 0.5){} //Xử lý chính trên đồ thị backbone với các tham số alpha và d o private void FindPath(int src, int des){} //Tìm đường đi ngắt nhất giữa 2 node backbone (optional) 18 o public void MainFindPath(Node src, Node des, List _path){} //Tìm đường đi giữa 2 node bất kì (optional). Thủ tục này gọi void FindPath(){} 3.4. Form chính Hình 3.4.1. Giao diện chính của chương trình Các chức năng: 1. Chọn các thông số đầu vào. 19 - Nhập số lượng node (mặc định là 90). Chương trình sẽ tạo ra N node được đánh số từ 0 đến N-1. - Lựa chọn các thông số đầu vào: o Hệ số dùng trong thuật toán Mentor o R: Bán kính của mạng truy nhập o D: Hệ số sử dụng dùng trong thuật toán Mentor Ngoài ra, giá trị W: ngưỡng để lựa chọn node Backbone xác định theo dữ liệu của bài tập. 2. Thực hiện Sau khi thiết lập các thông số, tại Box Control, ta lần lượt thực hiện các chức năng cần thiết: Mentor: Xác định các node Backbone và node truy nhập PrimDijkstra: Thiết lập mạng giữa các node Backbone Next: Thêm đường (theo thuật toán Mentor 2) Back: Quay trở về trạng thái trước khi Next Hình 3.4.2. (2a) Lựa chọn thông số đầu vào (2b) Thực hiện 20 Hình 3.4.3. Thay đổi các thông số - Để hiện thị các thuộc tính giữa các nút mạng: chí phí, lưu lượng, W, CMax, hay đường quá tải ta đánh dấu vào các ô trống nhỏ bên cạnh những thuộc tính muốn xem. 21 Hình 3.4.4. Thuộc tính mạng và thiết lập Chương trình còn cho phép tìm đường giữa 2 nút bất kỳ được nối với nhau như hình 1 là nút 67 và 16. 4 Kết luận Qua bài tập lớn này, chúng em đã phần nào hiểu rõ hơn về thuật toán MENTOR và cách hình thành cây theo thuật toán MENTOR cũng như xây dựng cây PST và MST. Đặc biệt, chúng em có cơ hội làm việc trên ngôn ngữ lập trình C#, một ngôn ngữ khá mạnh trong lập trình hướng đối tượng với đồ họa tốt. Qua bài tập lớn, chúng em một lần nữa phát huy và rèn luyện kỹ năng làm việc nhóm và độc lập cho mỗi cá nhân. Tuy nhiên, nhóm cũng có nhiều hạn chế chưa làm được trong bài tập lớn này, đó là mới chỉ lập trình được mạng Backbone, chưa lập trình được mạng Access (truy nhập). Do thời gian có hạn, nên quá trình thực hiện không tránh khỏi sai sót hoặc chưa được như mong muốn. Chúng em xin hứa sẽ làm tốt hơn vào các bài tập lớn khác. Chúng em xin cảm ơn cô Trần Ngọc Lan đã giúp đỡ chúng em trong quá trình thực hiện bài tập lớn này.