Đồ án Tìm hiểu một số phương pháp duyệt cây

BỘ CÔNG THƯƠNG TRƯỜNG ĐHCN TP.HỒ CHÍ MINH KHOA SAU ĐẠI HỌC bbbóaaa ĐỒ ÁN TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP DUYỆT CÂY GV h­íng dÉn : Đỗ Thị Hoµ Sinh viªn thùc hiÖn : Ng« V¨n Anh Líp : Đại học Tin Học 5 Liên Thông Thái Bình Th¸i B×nh, th¸ng 11 n¨m 2010 MỤC LỤC Lời mở đầu Cùng với sự phát triển của khoa học kĩ thuật, công nghệ thông tin nói chung và bộ môn cấu trúc dữ liệu và giải thuật nói riêng ngày càng được ứng dụng rộng trong nhiều lĩnh vực. Với một cơ sở dữ liệu khổng lồ, việc đưa ra một phương pháp nhằm giải quyết vấn đề tìm kiếm dữ liệu có hiệu quả và nhanh nhất luôn được sự quan tâm của các nhà phát triển phần mềm. Thông thường dữ liệu được biểu diễn dưới dạng các danh sách liên kết. Việc truy xuất dữ liệu chưa đạt hiệu quả cao. Sử dụng cấu trúc dữ liệu dạng cây là một giải pháp nhằm tăng hiệu xuất trong các thao tác xử lý. Vấn đề đặt ra: Với việc sử dụng cấu trúc dạng cây, chúng ta cần dùng giải thuật nào với từng dạng dữ liệu để đạt hiệu quả cao nhất. Để giải quyết vấn đề trên ta cùng tìm hiểu một số phương pháp duyệt cây. Phần I Tổng quan I. Cấu trúc cây. 1. Định nghĩa: Cây là một tập hợp T các phần tử (nút trên cây) trong đó có 1 nút đặc biệt T0 được gọi là gốc, các nút còn khác được chia thành những tập rời nhau T1, T2 , ... , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây. Nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. Cây không có phần tử nào gọi là cây rỗng. Ví dụ: 2. Một số khái niệm. 2.1. Bậc của một nút: Bậc của một nút là số cây con của nút đó. Ví dụ: nút T2 trong cây trên có bậc bằng 2 2.2. Bậc của một cây: Bậc của một cây là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phân Ví dụ: Cây trên có bậc bằng 3(bằng bậc của nút gốc) và cây trên được gọi là cây 3-phân 2.3. Nút gốc: Nút gốc là nút không có nút cha Ví dụ: nút gốc của cây trên là nút T2 2.4. Nút lá: Nút là là nút có bậc bằng 0. Nút lá không là cha của một nút khác. Ví dụ: cây trên có các nút lá: T5 , T6 , T11, T12, T13, T14, T15, T16, T10 2.5. Nút trung gian: Nút trung gian hay còn gọi là nút giữa là nút có bậc khác 0 và không phải là nút gốc. Ví dụ: Cây trên có các nút trung gian : T2 , T3 , T4, T7, T8, T9. 2.6. Nút cha, nút con Nút B được gọ là nút cha của nút C nếu nút B là nút trước của nút C và mức của nút C lớn hơn mức của nút B là 1. Khi đó nút C được gọi là nút con của nút B. Ví dụ: Trong cây trên Nút T3 là nút cha của các nút T7, T8, ngược lại các nút T7, T8 là nút con của nút T3. 2.7. Mức của một nút: Mức Nút gốc (T0) =1 Gọi T1, T2 , T3, … , Tn là các cây con của T0 Mức (T1) = Mức (T2) = Mức (T3) = … = Mức (T0) +1 Ví dụ: Mức của các nút trong cây trên Mức của các nút: T5, T6, T7 , T8, T9 , T10 bằng 3 Mức của các nút: T11, T12, T13 , T14, T15 , T16 bằng 4 2.8. Chiều cao của cây: Chiều cao của một cây hay còn gọi là chiều sâu của cây là mức cao nhất của các nút lá trong cây. Ví dụ: Cây trên nút chiều cao là 4, bằng mức lớn nhất của các nút lá. 2.9. Nút trước và nút sau của một mức: Nút T được gọi là nút trước của nút S nếu cây con có gốc là T chứa cây con có gốc là S. Khi đó nút S được gọi là nút sau của nút T. Ví dụ: nút T3 là nút trước của các nút T11, T12, T13, T14. Ngược lại các nút T11, T12, T13, T14 là nút sau của nút T3. 2.10. Chiều dài đường đi. Chiều dài đường đi của một nút là số nhánh cần đi qua tính từ nút gốc để đi đến nút đó. Chiều dài đường đi của nút gốc luôn bằng 1, chiều dài đường đi tới một nút bằng chiều dài đường đi tới nút cha cộng thêm 1. Ví dụ: Chiều dài đường đi tới nút T3 là 2. Chiều dài đường đi của một cây là tổng tất cả các chiều dài đường đi của tất cả các nút trên cây. Ví dụ: Chiều dài các nút trong cây trên: Nút gốc có chiều dài bằng 1. Các nút: T1, T2 , T3 bằng 2 -> tổng bằng 6. Các nút: T5, T6, T7 , T8, T9 , T10 bằng 3 -> tổng bằng: 18 Các nút: T11, T12, T13 , T14, T15 , T16 bằng 4 -> tổng bằng 24 Tổng đường đi của cây trên là : 1 + 6 + 18 + 24 = 49. 2.11. Rừng: Rừng là tập hợp các cây. Một cây khác rỗng khi mất gốc sẽ trở thành một rừng. 3.Biểu diễn cây. Có nhiều phương pháp biểu diễn cây. Cách thường dùng nhất là biểu diễn mỗi nút như một dữ liệu kiểu bản ghi, mỗi nút chứa các con trỏ tới các con hoặc cha của nó, hoặc cả hai. Cây cũng có thể biểu diễn bằng các mảng cùng với quan hệ giữa các vị trí trong mảng. 3.1 Biểu diễn bằng các nút với các con trỏ Mỗi nút là một dữ liệu kiểu bản ghi với ban trường: Một trường thường gọi là INFOR chứa thông tin lưu trữ tại nút đó. Thông tin này có thể chỉ là một số, một ký tự, cũng có thể là một tập hợp dữ liệu rất phức tạp. Hai trường Llink và Rlink chứa các liên kết trái và phải. Nếu cây là cây nhị phân Llink trỏ tới con trái của nút, Rlink trỏ tới con phải của nút. Nếu cây là cây tổng quá, Llink trỏ tới con cực trái và Rlink trỏ tới em kế cận phải của nút đó. Do đó danh sách các nút biểu diễn một cây tổng quát, khi được xem là biểu diễn của cây nhị phân sẽ cho một cây nhị phân. Cây nhị phân này được gọi là cây nhị phân tương đương với cây tổng quát ban đầu. 3.2 Biểu diễn cây nhị phân bằng mảng Cây nhị phân đầy đủ là cây nhị phân, trong đó mỗi nút trong chỉ có hai con. Cây nhị phân hoàn chỉnh là cây nhị phân đầy đủ trong đó tất cả các lá đề ở mức cao nhất. Một cây nhị phân hoàn chỉnh chiều cao h chỉ có 2h +1 – 1 nút. Người ta có thể dùng một mảng gồm 2h +1 -1 phần tử để biểu diễn cây hoàn chỉnh, bằng cách lần lượt lưu trữ thông tin của mỗi nút vào mảng theo thứ tự từ trên xuống dưới, từ trái sang phải. Khi đó Con trái của nút thứ i là phần tử thứ 2*i Con phải là phần tử thứ 2*i +1 Cha của phần tử thứ i là phần tử thứ int(i/2). Nếu cây là không hoàn chỉnh, ta gán giá trị Null cho các vị trí còn thiếu so với cây nhị phân hoàn chỉnh. Một cách khác, dùng mảng hai chiều trong dòng thứ nhất ghi các thông tin của nút, dòng thứ hai ghi chỉ số của nút cha của nút đó với dấu (+)nếu nút hiện tại là con trai, với dấu (–) nếu nút hiện tại là con phải cua nút cha. II. Các dạng cây thường gặp 1. Cây nhị phân 1.1 Định nghĩa Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con Cây nhị phân có thể ứng dụng trong nhiều bài toán thông dụng, Ví dụ 1.2. Một số tính chất của cây nhị phân: - Số nút ở mức I ≤ 2I-1. - Số nút ở mức lá ≤ 2h-1, với h là chiều cao của cây. - Chiều cao của cây h ≥ log2N (N - số nút trên trong cây). 1.3. Biểu diễn cây nhị phân T Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút, ta dùng một biến động lưu trữ các thông tin: + Thông tin lưu trữ tại nút. + Địa chỉ nút gốc của cây con trái trong bộ nhớ. + Địa chỉ nút gốc của cây con phải trong bộ nhớ. Khai báo như sau: typedef struct tagTNODE { Data Key;//Data là kiểu dữ liệu ứng với thông tin lưu tại nút struct tagNODE *pLeft, *pRight; 5 }TNODE; typedef TNODE *TREE; 1.4. Các thao tác trên cây nhị phân Thăm các nút trên cây theo thứ tự trước (Node-Left-Right) Thăm các nút trên cây theo thứ tự giữa (Left- Node-Right) Thăm các nút trên cây theo thứ tự sau (Left-Right-Node) 2. Cây nhị phân tìm kiếm Cây nhị phân tìm kiếm là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Ví dụ: Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Chi phí tìm kiếm trung bình chỉ khoảng log2N. Trong thực tế, khi xét đến CNP chủ yếu người ta xét CNPTK 2.1 Các thao tác trên cây 2.1.1 Thăm các nút trên cây 2.1.2 Tìm một phần tử X trong cây Dễ dàng thấy rằng số lần so sánh tối đa phải thực hiện để tìm phần tử X là bằng h, với h là chiều cao của cây Ví dụ: tìm phần tử 55 So sánh X=55 với gốc là 44 vì 55>44 nên sẽ tìm kiếm nhánh bên phải của cây Tiếp theo lại so sánh X với gốc của cây con nhỏ 88 vì 55 <88 nên tìm ở nhánh trái của cây có gốc 88 Tiếp tục so sánh với cây con gốc 59: 55 kết quả 2.1.3 Thêm một phần tử X vào cây Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vào nhiều vị trí khác nhanh trên cây, nhưng nếu thêm vào một nút là thì sẽ dễ nhất do ta có thể thực hiện quá trình tương tực thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm ta sẽ tìm đượ vị trí cần thêm. Hàm insert trả về giá trị –1, 0, 1 khi không đủ bộ nhớ, gặp nút cũ hay thành công: int insertNode(TREE &T, Data X) { if(T) { if(T->Key == X) return 0; //đã có if(T->Key > X) return insertNode(T->pLeft, X); else return insertNode(T->pRight, X); } T = new TNode; if(T == NULL) return -1; //thiếu bộ nhớ T->Key = X; T->pLeft =T->pRight = NULL; return 1; //thêm vào thành công } 2.1.4. Hủy một phần tử có khóa x Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK. Có 3 trường hợp khi hủy nút X có thể xảy ra: X - nút lá. X - chỉ có 1 cây con (trái hoặc phải). X có đủ cả 2 cây con Trường hợp thứ nhất: chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác. Trường hợp hai: Trước khi hủy X ta móc nối cha của X với con duy nhất của nó. Trường hợp cuối cùng: ta không thể hủy trực tiếp do X có đủ 2 con => ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y, Phần tử này có tối đa một con. Thông tin lưu tại Y sẽ được chuyển lên lưu tại X. Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu. Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK. Sẽ có 2 phần tử thỏa mãn yêu cầu: Phần tử nhỏ nhất (trái nhất ) trên cây con phải. Phần tử lớn nhất(Phải nhất)trên cây con trái/ Việc chọn lựa phần tử nào là phần tử thế mạng hoàn toàn phụ thuộc vào ý thích của người lập trình. Ở đây, chúng ta sẽ chọn phần tử(phải nhất) trên cây con trái làm phần tử thế mạng. Ví dụ: cần hủy phần tử 18 2.1.5 Đánh giá Tất cả các thao tác tìm kiếm, thêm mới, xóa trên CNPTK đều có độ phức tạp trung bình O(h) với h là chiều cao của cây Trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h=log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự. Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK, lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy có cải tiến cấu trúc của CNPTK để đạt được chi phí cho câc thao tác là log2(n). III Các phương pháp duyệt cây 1. Định nghĩa Duyệt một cây là một trình tự làm việc với các nút trong cây, trình tự này giống như một chuyến đi qua các nút trên cây theo các liên kết cha-con. Các giải thuật duyệt khác nhau về thứ tự “viếng thăm” giữa một nút cha và các nút con. 2. Một số phương pháp duyệt cây: Back tracking Breadth first search Depth first search. Node Left Right Left Node Right Left Right Node 2.1 Back tracking: -Giải thuật Back tracking phải có khả năng tìm kiếm ra tất cả các đường có thể có để tìm được nghiệm : PATH từ node khởi đầu đến goal. -Back tracking: thực hiện bằng cách “lần” theo các nhánh của đồ thị. Từ một trạng thái, sinh ra các node con, chọn một node con, xem đó là node xét kế tiếp. Lặp lại cho đến khi tìm thấy một node đích. -Nó thực hiện bằng cách“Lần” theo các node à Đi vào ngõ cụt? --Khi gặp nhánh không đi tiếp được, giải thuật phải có khả năng quay lui lại node trước đó để đi sang nhánh khác. Giải thuật: PROCEDURE backtrack; BEGIN SL:=[start]; NLS:=[start]; DE:=[ ]; CS:=start; WHILE (NSL[ ]) DO BEGIN IF CS = Goal THEN return(SL); IF CS has no children (Except node in DE, SL and NSL) THEN WHILE (SL[ ] AND CS=First element of SL) DO BEGIN add CS to DE remove first element from SL; remove first element from NSL; CS:= first element of NSL; END; add CS to SL; ELSE add children of CS (Except node in DE,SL and NSL) to NSL CS:= first element of NSL; add CS to SL; ENDIF; END Return FAIL; END; Trong đó: SL (State list): chứa danh sách các node trên đường hiện đang xét. Nếu tìm ra goal thì SL chính là nghiệm. NSL (New State List): chứa danh sách các node đang đợi xét. DE (Dead End): chứa các node mà con cháu của chúng không chứa đích. CS (Current State): chứa node đang xét. Hướng phát triển của quá trình tìm kiếm tùy theo cơ cấu tổ chức của NSL: FIFO, FILO hay Evaluated. Ví dụ: tìm nốt 71 của cây sau: Duyệt đi xuống từng cấp, đến nút lá thì đi lên từng cấp: Bảng lịch duyệt: Lần Lặp CS SL NSL DE 0 1 2 3 4 5 6 7 8 9 10 11 44 18 13 15 37 23 40 88 59 55 71 108 [44] [18 44] [13 18 44] [15 13 18 44] [37 18 44] [23 3718 44] [40 37 18 44] [88 44] [59 88 44] [55 59 88 44] [71 59 88 44] [108 88 44] [44] [18 88 44] [13 37 18 88 44] [15 13 37 18 88 44] [37 18 88 44] [23 37 18 88 44] [40 37 18 88 44] [88 44] [59 108 88 44] [55 71 59 108 88 44] [71 59 108 88 44] [88 44] [ ] [ ] [ ] [ ] [13 15] [13 15] [13 15 23] [18 37 40 2313 15] [18 37 40 23 13 15] [18 37 40 23 13 15] [18 37 40 23 13 15 55] [18 37 40 23 13 15 59 7155] 2.2-Breadth first search Là graph search với các nút “anh em” của nút hiện thời được xem xét trước các nút “con cháu” Giải thuật: Procedure Breath_first_search; BEGIN open :=[start]; close:=[ ]; WHILE (open [ ]) do BEGIN remove X which is the leftmost of Open; IF (X=goal) THEN return (Success) ELSE BEGIN generate children of X; Put X to close; remove children of X which is in Open or Close; Put remain children on RIGHT end of open; END; END; Return (FAIL); END; Ví dụ: Tìm nốt 108 của cây sau: Kết quả: 44 18 88 13 37 59 108 Bảng lịch duyệt: Đưa các nút của đồ thị vào bên phải nhất của Open và Close Lần Lặp X Open Close 0 1 2 3 4 5 6 7 44 18 88 13 37 59 108 [44 ] [18 88 ] [88 13 37 ] [13 37 59 108 ] [37 59 108 15 ] [59 108 15 23 40 ] [108 15 23 40 55 71 ] [15 23 40 55 71 ] [ ] [44] [44 18] [44 18 88 ] [44 18 88 13 ] [44 18 88 13 37 ] [44 18 88 13 37 59 ] [44 18 88 13 37 59 ] 2.3-Depth first search Là graph search với các nút “con cháu” của nút hiện thời được xem xét trước các nút “anh em”. Giải thuật: Procedure depth_first_search; Begin open :=[start]; close:=[ ]; While (open [ ]) do begin remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to close; remove children of X which is in Open or Close; Put remain children on LEFT end of open; End; End; Return (FAIL); End; Ví dụ: tìm nốt 108 của cây nhị sau: Bảng lịch duyệt: Lần Lặp X Open Close 0 1 2 3 4 5 6 7 8 9 10 11 12 44 18 13 15 37 23 40 88 59 55 71 108 [44] [18 88 ] [13 37 88 ] [15 37 88 ] [37 88 ] [23 40 88 ] [40 88 ] [88 ] [59 108 ] [55 71 108] [71 108] [108] [ ] [44] [44 18] [44 18 13] [44 18 13 15 ] [44 18 13 15 37 ] [44 18 13 15 37 23 ] [44 18 13 15 37 23 ] [44 18 13 15 37 23 88 ] [44 18 13 15 37 23 88 59] [44 18 13 15 37 23 88 59 55] [44 18 13 15 37 23 88 59 55 71] 2.4-Node Left Right Cách duyệt: Trước tiên thăm nốt gốc sau đó thăm các nốt của cây con trái rồi đến cây con phải. Giải thuật: Khai báo cây nhị phân: template class Binary_tree { public: Binary_tree( ); bool empty( ) const; void preorder(void (*visit)(Entry &)); void inorder(void (*visit)(Entry &)); void postorder(void (*visit)(Entry &)); int size( ) const; void clear( ); int height( ) const; void insert(const Entry &); Binary_tree (const Binary_tree &original); Binary_tree & operator = (const Binary_tree &original); ~Binary_tree( ); protected: Binary_node *root; }; Giải thuật duyệt: Algorithm recursive_NLR Input: subroot là con trỏ node gốc và hàm visit Output: kết quả phép duyệt 1. if (cây con không rỗng) 1.1. Duyệt node subroot bằng hàm visit 1.2. Call recursive_NLR với nhánh trái của subroot 1.3. Call recursive_NLR với nhánh phải của subroot End recursive_NLR Mã C++ template void Binary_tree ::recursive_NLR (Binary_node *sub_root, void (*visit)(Entry &)) { if (sub_root != NULL) { (*visit)(sub_root->data); recursive_NLR(sub_root->left, visit); recursive_NLR(sub_root->right, visit); } } Ví dụ: Tìm nốt 108 Kết quả: 44 18 13 15 37 23 40 88 59 55 71 108 Bảng lịch duyệt: Lần lặp X Open Close 0 1 2 3 4 5 6 7 8 9 10 11 44 18 13 15 37 23 40 88 59 71 108 [44] [18 88] [13 37 88 ] [15 37 88] [37 88] [23 40 88] [40 88] [88] [59 108] [55 71 108] [108] [ ] [44] [44 18] [44 18 13 ] [44 18 13 15 ] [44 18 13 15 37 ] [44 18 13 15 37 23 ] [44 18 13 15 37 23 40 ] [44 18 13 15 37 23 40 88] [44 18 13 15 37 23 40 88 59] [44 18 13 15 37 23 40 88 59 71] 2.5-Left Node Right Cách duyệt: Trước tiên thăm các nốt của cây con trái sau đó thăm nốt gốc rồi đến cây con phải. Giải thuật: Algorithm recursive_LNR Input: subroot là con trỏ node gốc và hàm visit Output: kết quả phép duyệt 1. if (cây con không rỗng) 1.1. Call recursive_LNR với nhánh trái của subroot 1.2. Duyệt node subroot bằng hàm visit 1.3. Call recursive_LNR với nhánh phải của subroot End recursive_LNR Mã C++ template void Binary_tree ::recursive_LNR (Binary_node *sub_root, void (*visit)(Entry &)) { if (sub_root != NULL) { recursive_LNR(sub_root->left, visit); (*visit)(sub_root->data); recursive_LNR(sub_root->right, visit); } } Ví dụ: Tìm nút 108 Kết quả: 13 15 18 23 37 40 44 55 59 71 88 108 Bảng lịch duyệt: Lần lặp X Open Close 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 13 15 18 37 23 37 40 44 88 59 55 59 71 88 108 [13] [15 18] [15 18 ] [37 44] [23 37 40 44] [37 40 44] [40 44] [44] [88] [59 88 108] [55 59 71 88 108] [59 71 88 108] [71 88 108] [88 108] [108] [ ] [13] [13 15] [13 15] [13 15 18 ] [13 1518 23 ] [13 15 18 23 ] [13 15 18 23 37 40 ] [13 15 18 23 37 40 44 ] [13 15 18 23 37 40 44 ] [13 15 18 23 37 40 44 ] [13 15 18 23 37 40 44 55 ] [13 15 18 23 37 40 44 55 59] [13 15 18 23 37 40 44 55 59 71 ] [13 15 18 23 37 40 44 55 59 71 88 ] 2.6-Left Right Node Cách duyệt: trước tiênn thăm các nốt của cây con trái sau đó thăm đến cây con phải rồi cuối cùng mới thăm nốt gốc. Giải thuật: Algorithm recursive_LRN Input: subroot là con trỏ node gốc và hàm visit Output: kết quả phép duyệt 1. if (cây con không rỗng) 1.1. Call recursive_LRN với nhánh trái của subroot 1.2. Call recursive_LRN với nhánh phải của subroot 1.3. Duyệt node subroot bằng hàm visit End recursive_LRN Mã C++ template void Binary_tree ::recursive_LRN (Binary_node *sub_root, void (*visit)(Entry &)) { if (sub_root != NULL) { recursive_LRN(sub_root->left, visit); recursive_LRN(sub_root->right, visit); (*visit)(sub_root->data); } } Ví dụ: Kết quả: 15 13 23 40 37 18 55 71 59 108 88 44 Bảng lịch duyệt: Lần lặp X Open Close 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15 13 18 37 23 40 37 18 44 88 59 55 71 59 108 [15] [13 18] [18] [37 18 44] [23 40 37 18 44] [40 37 18 44] [37 18 44] [18 44] [44] [88 44] [59 108 88 44] [55 71 59 108 88 44] [71 59 108 88 44] [59 108 88 44] [108 88 44] [88 44] [ ] [15] [15 13] [15 13] [15 13] [15 13 23] [15 13 23 40] [15 13 23 40 37] [15 13 23 40 37 18] [15 13 23 40 37 18 [15 13 23 40 37 18] [15 13 23 40 37 18] [15 13 23 40 37 18 55] [15 13 23 40 37 18 55 71] [15 13 23 40 37 18 55 59] [15 13 23 40 37 18 55 59 108] Phần II. Cài đặt I.Giao diện Chương trình được xây dựng bằng bộ công cụ Visual Studio 2008, ngôn ngữ C#. Với cấu trúc dữ liệu được mô tả như phần trên, giao diện chính của chương trình khi khởi động như sau: Giao diện chương trình. II. Hướng dẫn sử dụng 1.Mô tả chương trình Chương trình giải bài toán tìm kiếm trên đồ thị bao gồm các chức năng: - Tạo mới: cho phép tạo mới một đồ thị để xử lý - Mở file: Mở đồ thị từ tệp tin . txt đã lưu. - Lưu file: Cho phép lưu đồ thị đang xử lý thành dạng file .txt - Vẽ cạnh: Bật/ tắt chế độ cho phép thêm và xóa 1 cạnh vào đồ thị. Các nút lệnh: - Thêm: Cho phép thêm một nút vào đồ thị - Xóa: Xóa một nút từ đồ thị - Back tracking: Tìm kiếm nút theo kiểu Back tracking. - Breadth first search: Tìm kiếm nút theo kiểu Breadth first search - Depth first search: Tìm kiếm nút theo kiểu Depth first search - Thoát: Thoát khỏi chương trình. 2. Chi tiết sử dụng: 2.1 Tạo các node của đồ thị - Khởi động chương trình. Để tạo mới một đồ thị ta nhập các node vào khung “nhập node” sau đó nhấn enter hoặc kích nút thêm. Chú ý: mỗi lần chỉ nhập được một node. - Dùng chuột kéo thả và sắp xếp các node theo đồ thị. Thêm các node vào đồ thị 2.2.Cách tạo và xóa liên hệ giữa các node: - Click chọn nút “Vẽ cạnh” trên thanh công cụ con trỏ chuột chuyển thành dấu +. - Kéo chuột từ node bắt đầu đến node kết thúc để vẽ cạnh. Lưu ý: khi vẽ cạnh bắt đầu từ một trạng thái, nên vẽ từ trái sang phải để các bảng duyệt sẽ làm đúng thứ tự như trong hình đã vẽ. - Nếu muốn xóa cạnh giữa 2 node thì vẽ 1 cạnh đè lên 2 node đó và xác nhận đồng ý xóa. Thêm liên hệ giữa các node của đồ thị 2.3. Sử dụng các chức năng tìm kiếm: - Để tìm kiếm một node trong đồ thị, nhập tên node cần tìm vào ô text “Nhập NODE tìm kiếm”. - Lựa chọn phương pháp tìm tương ứng với một trong ba nút “Back tracking”, “Breadth first search”, “Depth first search”. - Xem kết quả. Sử dụng chức năng tìm kiếm Phần III. Kết Luận Sau một thời gian tìm hiểu, nghiên cứu và thực hiện đề tài, các yêu càu chính của đề tài cơ bản đã hoàn tất với những nội dung chủ yếu sau : *Ưu điểm Xây dựng được chương trình “Giải bài toán tìm kiếm trên đồ thị” sử dụng các thuật toán duyệt cây cơ bản đáp ứng được tìm kiếm các node trên đồ thị. Giao diện đơn giản dễ sử dụng. Chương trình đã minh họa được việc xây dựng đồ thị một cách trực quan thông qua các thao tác kéo thả với chuột. Chương trình xử lý nhanh và cho kết quả chính xác. *Khuyết điểm và hướng phát triển Mặc dù đã rất cố gắng nhưng do thời gian ngắn, kinh nghiệm còn hạn chế nên kết quả vẫn còn nhiều thiếu sót cần tiếp tục được hoàn thiện để có thể ứng dụng giả các bài toán đồ thị phức tạp hơn Chương trình còn nhiều lỗi về nhập liệu như: Các node phải nhập lần lượt từng lần. Hiển thị node bị chồng nhau, khó quan sát. Xây dựng hoàn thiện các chức năng giúp người sử dụng dễ dàng theo dõi kết quả các bước tìm kiếm và duyệt cây. Xử lý các lỗi cơ bản về nhập liệu cũng như xử lý. Trên đây là các kết quả đạt được cũng như một số tồn tại và hướng phát triển của phần mềm trong tương lai để ngày càng hoàn chỉnh hơn. Em xin chân thành cảm ơn sự quan tâm, giúp đỡ, hướng dẫn nhiệt tình của Cô Đỗ Thị Hòa để em hoàn thành đề tài này. Sinh viên thực hiện. Ngô Văn Anh