Báo cáo Nghiên cứu khoa học Cấu trúc đống và ứng dụng

Mục Lục Phần 1:MỞ ĐẦU Lí do chọn đề tài. Hiện nay, công nghệ thông tin với tốc độ phát triển rất nhanh. Các nhà khoa học khẳng định rằng chưa có một ngành khoa học - công nghệ nào lại có nhiều ứng dụng như công nghệ thông tin. Việc ứng dụng công nghệ thông tin vào trong giáo dục đã trở thành mối ưu tiên hàng đầu của nhiều quốc gia trong đó có Việt Nam. Trong quá trình học các giải thuật nói chung và môn cấu trúc dữ liệu nói riêng, chúng ta rút ra một nhận định chung là: nhiều giải thuật phức tạp trừu tượng, khó hiểu, khó hình dung vấn đề. Do đó chúng ta luôn mong muốn trong quá trình học giải thuật nên có những mô phỏng trực quan để chúng ta có thể tiếp thu giải thuật một cách dễ dàng hơn. Tuy nhiên, việc học tốt giải thuật có rất nhiều thận lợi dó là giúp cho quá trình tư duy giải thật tốt hơn, phát hiện vấn đề nhanh hơn, đặc biệt giúp cho việc học các môn học khác có tính logic cao được thuận lợi hơn. Nhưng để học tốt giải thuật thì không dễ dàng với nhiều người. Vậy để giúp người học tiếp thu một cách dễ dàng các giải thuật thì phải xây dựng các phần mền mô phỏng thuật toán. Cấu trúc đống có rất nhiều ứng vào các giải thuật nhưgiả thuật sắp xếp đống, vào hàng đợi ưu tiên. Nghiên cứu cấu trúc đống để hiểu thêm về nó phục vụ trong việc giải quyết các bài toán Phần 2:Nội Dung Chương 1 : Cơ sở lý thuyết về cây nhị phân. I. Định nghĩa và các ví dụ 1. Định nghĩa. Cây là một cấu trúc phi tuyến tính. Một cây (tree) là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là nút gốc (root), giữa các nút có một mối quan hệ phân cấp gọi là quan hệ “cha - con”. Có thể định nghĩa cây một cách đệ quy như sau: Một nút là một cây. Nút đó cũng là gốc của cây ấy. Nếu T1, T2, ..., Tn là các cây, với n1, n2, ... nk lần lượt là các gốc, n là một nút và n có quan hệ cha - con với n1, n2, ... nk thì lúc đó một cây mới T sẽ được tạo lập, với n là gốc của nó. n được gọi là cha của n1, n2, ... nk ; ngược lại n1, n2, ... nk  được gọi là con của n. Các cây T1, T2, ..., Tn được gọi là các cây con (substrees) của n. Ta quy ước : Một cây không có nút nào được gọi là cây rỗng (null tree). Có nhiều đối tượng có cấu trúc cây. 2.Ví dụ . a) Mục lục của một cuốn sách, hoặc một chương trong sách, có cấu trúc cây. b) Biểu thhức số học x + y * (z – t) + u/v, ta có thể biểu diến dưới dạng cây như hình 1. Hình 1 II. Cây nhị phân. 1. Định nghĩa và các tính chất. Cây nhị phân là một dạng quan trọng của cấu trúc cây. Cây nhị phân có các đặc điểm là: Mọi nút trên cây chỉ có tối đa là 2 con. Đối với cây con của một nút người ta cũng phân biệt cây con trái (left subtree) và cây con phải (right subtree). Như vậy cây nhị phân là cây có thứ tự. Ví dụ : Cây ở hình 1 là cây nhị phân với toán tử ứng với gốc, toán hạng 1 ứng với cây con trái, toán hạng 2 ứng với cây con phải. Các cây nhị phân sau đây là khác nhau, nhưng nếu coi là cây không có thứ tự thì chúng chỉ là 1. 2. Biểu diễn cây nhị phân Lưu trữ kế tiếp Nếu có một cây nhị phân đầy đủ, ta có thể dễ dàng đánh số cho các nút trên cây đó theo thứ tự lần lượt từ mức 1 trở lên, hết mức này đến mức khác và từ trái sang phải đối với các nút ở mỗi mức. Ví dụ : Với hình .... cây f) có thể đánh số như sau : Hình 2 Ta thấy ngay một quy luật đệ quy trái như sau : Con của các nút thứ i là các nút thứ 2i và 2i + 1 hoặc Cha của nút thứ j là ëj/2û Nếu như vậy thì ta có thể lưu trữ cây nhị phân đầy đủ bằng một vectơ V, theo nguyên tắc: nút thứ i của cây được lưu trữ ở V[i]. Đó chính là cách lưu trữ kế tiếp đối với cây nhị phân. Với cách lưu trữ này nếu biết được địa chỉ nút cha sẽ tính được địa chỉ nút con và ngược lại. Như vậy với cây đầy đủ nêu trên thì hình ảnh lưu trữ sẽ như sau : Tất nhiên với cây nhị phân hoàn chỉnh, mà các nút ở mức cuối đều đạt về phía trái (để việc đánh số các nút này được liên tục ) thì cách lưu trữ này vẫn thích hợp. Còn với cây nhị phân dạng khác thì cách lưu trữ này có thể gây lãng phí do có nhiều phần tử nhớ bị bỏ trống(ứng với cây con rỗng). Chẳng hạn đối với cây lệch trái thì phải lưu trữ bằng một véc tơ . Ngoài ra nếu cây luôn biến động nghĩa là có phép bổ sung, loại bỏ các nút thường xuyên tác động, thì cách lưu trữ này tất không tránh được các nhược điểm như đã nêu trên. Cách lưu trữ móc nối sau đây vừa khắc phục được nhược điểm này, vừa phản ánh được dạng tự nhiên của cây. Lưu trữ móc nối Trong cách lưu trữ này, mỗi nút ứng với một phần tử nhớ có quy cách như sau : LPTR INFO RPTR Trong đó : Trường INFO ứng với thông tin (dữ liệu) của nút. Trường LPTR ứng với con trỏ, trỏ tới cây con trái của nút đó. Trường RPTR ứng với con trỏ, trỏ tới cây con phải của nút đó. Ví dụ : Cây nhị phân Hình 3 Cây nhị phân trong hình 3 có dạng lưu trữ móc nối như hình sau : Hình 4 Để có thể truy nhập vào các nút trên cây cần có một con trỏ T, trỏ tới nút gốc của cây đó. Người ta quy ước : Nếu cây nhị phân rỗng thì T = Null. Với cách biểu diễn này từ nút cha có thể truy nhập trực tiếp vào nút con, nhưng ngược lại thì không làm được. Chương 2. Cấu trúc đống. I. Định nghĩa . 1.Định nghĩa. Đống (Heap) là một cây nhị phân gắn nhãn với các nhãn là các giá trị thuộc tập hợp được sắp thứ tự tuyến tính, sao cho những điều kiện sau đây được thực hiện: 1.Tất cả các mức của cây đều đầy, trừ mức thấp nhất có thể thiếu một số đỉnh. 2.Ở mức thấp nhất, tất cả các lá đều xuất hiện liên tiếp từ bên trái. 3. Giá trị ở mỗi đỉnh không lớn hơn giá trị của các đỉnh con của nó Với điều kiện này thì không đảm bảo Heap là một cây nhị phân tìm kiếm. 2. Heap có các tính chất sau : Tính chất 1 : Nếu ap , a2 ,... , aq là một Heap thì khi cắt bỏ một số phần tử ở hai đầu của Heap, dãy con còn lại vẫn là một Heap. Tính chất 2 : Mọi dãy ap , a2 ,... , aq, dãy con aj, aj+1,…, ar tạo thành một Heap với j=(q div 2 +1). 3. Ví dụ : Đống được lưu trong máy bởi một mảng a[1..n], với gốc ở phần tử thứ nhất, con bên trái của đỉnh a[i] là a[2*i] con bên phải là a[2*i+1] (với 2*i<=n và 2*i+1<=n). Khi đó nếu như a[i] <= a[2*i] và a[2*i+1] với mọi i = 1.. int(n/2). thì trong đống a[1] (tương ứng là gốc của cây) là phần tử nhỏ nhất. Đây là Heap (Hình 5) 4) Thuật giải. 1.Xem mảng ban đầu là một cây nhị phân. Mỗi nút trên cây lưu trữ một phần tử mảng, trong đó a[1] là nút gốc và mỗi nút không là nút lá a[i] có con trái là a[2*i] và con phải là a[2*i+1]. Với cách tổ chức này thì cây nhị phân thu được sẽ có các nút trong là các nút a[1]…, a[n DIV 2]. Tất cả các nút trong đều có hai con, ngoại trừ nút a[n DIV 2] có thể chỉ có một con trái (trong trường hợp n là một số chẵn). 2.Sắp xếp dãy ban đầu thành Heap căn cứ vào giá trị khoá của các nút. 3.Hoán đổi a[1] cho phần tử cuối cùng. 4.Sắp lại cây sau khi đã bỏ đi phần tử cuối cùng để nó trở thành một heap mới. Lặp lại quá trình (3) và (4) cho tới khi cây chỉ còn một nút ta sẽ được mảng sắp theo thứ tự giảm II. Các phép toán của Heap. 1. Thêm một phần tử vào Heap. Để xen một phần tử mới vào Heap, đầu tiên ta thêm một lá mới liền kề với các lá ở mức thấp nhất, nếu mức thấp nhất chưa đầy; còn nếu mức thấp nhất đầy, thì ta thêm vào một lá ở mức mới sao cho các điều kiện 1 và 2 của Heap được bảo tồn.Trong hình 6a dưới sau khi thêm nút lá có giá trị 3 vào mức cuối cùng thì cây không còn là Heap. Nếu sau khi thêm vào lá mới cây không còn là heap, thì ta theo đường từ lá mới tới gốc cây. Nếu một đỉnh có giá trị nhỏ hơn đỉnh cha của nó, thì ta trao đổi đỉnh đó với cha của nó. Sau quá trình biến đổi đó thì ta có một Heap hình 6c. Hình 6a Hình 6b Hình 6c 2. Xoá một phần tử nhỏ nhất khỏi Heap. Sét một Min Heap thì hiển nhiên gốc của cây sẽ có giá trị nhỏ nhất. Tuy nhiên nếu loại bỏ gốc thì cây không còn là cây nữa. Do đó ta tiến hành như sau: đặt vào gốc phần tử của hàng ưu tiên chứa trong lá ngoài cùng bên phải ở mức thấp nhất, sau đó loại bỏ lá này ra khỏi cây. Hình 6a minh hoạ cây nhận được từ cây trong hình 6 sau phép biến đổi.Tới đây cây không còn là heap vì điều kiện 3 của định nghĩa Heap bị vi phạm ở gốc cây. Bây giờ ta đi từ gốc xuống. Giả sử tại một bước nào đó ta đang ở đỉnh a và hai đỉnh con của nó tại b và c. Để xác định, ta giả sử rằng giá trị ưu tiên của ít nhất hơn giá trị ưu tiên của đỉnh c pri(b) <= pri(c). Khi đó ta sẽ trao đổi đỉnh a với đỉnh b và đi xuống đỉnh b. Quá trình đi sẽ dừng lại cùng lắm là khi ta đạt tới một lá của cây. Có thê thấy quá trình diễn ra ở hình 7b và 7c (a) (b) (c) Hình 7 Chương 3: Các ứng dụng của Đống I. Ứng dụng của Heap trong giải thuật Heap_sort. 1.Giải thuật. HeapSort là một giải thuật dựa vào cấu trúc đống và để sắp xếp theo thứ tự giảm dần của các giá trị khoá là số. Giải thuật Heapsort trải qua 2 giai đoạn : Giai đoạn 1 :Hiệu chỉnh dãy số ban đầu thành heap; Giai đoạn 2: Sắp xếp dãy số dựa trên heap: Bước 1:      Ðưa phần tử nhỏ nhất về vị trí đúng ở cuối dãy:       r = n; Hoán vị (a1 , ar ); Bước 2 Loại bỏ phần tử nhỏ nhất ra khỏi heap: r = r-1;  Hiệu chỉnh phần còn lại của dãy từ a1 , a2 ... ar thành một heap. Bước 3:  Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2       Ngược lại : Dừng  Ví dụ: Với một dẫy số Cho dãy số a: Sắp xếp dẫy theo thứ tự giảm dần 5 6 2 2 12 12 9 10 9 3 Mảng này được xem như là một cây nhị phân ban đầu như sau: Hình 8 Giai đoạn 1: hiệu chỉnh dãy ban đầu thành heap Việc sắp xếp cây này thành một heap sẽ bắt đầu từ việc đẩy xuống nút a[5] (vì 5= 10 div 2). Xét nút 5 ta thấy a[5] chỉ có một con trái và giá trị khoá tương ứng của nó lớn hơn con trái của nó nên ta đổi chỗ hai nút này cho nhau và do con trái của a[5] là a[10] là một nút lá nên việc đẩy xuống của a[5] là kết thúc Hình 9 Tiếp theo xét nút a[4] và a[3] đã đúng vị trí nên không phải thực hiện sự hoán đổi nữa. Xét nút a[2], so sánh thấy giá trị a[2] = 6 > a[4] = 2 và a[4] < a[5] = 3 (a[4], a[5] là con trái và con phải của nút a[2] )nên ta hoán đổi nút a[2] cho nút con trái của nó là a[4], sau hoán đổi xét thấy nút a[4] vẫn đúng vị trí nên việc đẩy a[2] là kết thúc. Hình 10 Cuối cùng ta xét nút a[1], ta thấy giá trị khoá của nút a[1] = 5 lớn hơn khoá của con trái ( a[2] = 2) và giá trị khoá của con trái bằng giá trị khoá của con phải ( a[2] = 2, a[3] = 2) nên hoán đổi a[1] cho nút con trái của nó là nút a[2]. Sau khi thực hiện phép hoán đổi thấy nút a[2] có giá trị khoá lớn hơn giá trị khoá của nút con con phải cua nó là a[5] và con phải của nó có giá trị nhỏ hơn khoá của con trái nên phải thực hiên phép hoán đổi nút a[2] cho nút a[5]. Xét lại thấy nút a[5] thì nó vẫn đúng vị trí. Tương tự xét tiếp các nút còn lại thấy đã dúng vị trí nên cuối cùng được cây đã là một heap. Cây đã là một heap (Hình 11) Giai đoạn 2: Sắp xếp dãy số dựa trên heap : Trong giai đoạn thứ hai, chúng ta thấy rằng gốc của cây (cũng là phần tử đầu tiên của mảng hay cũng là đỉnh heap) là phần tử có khoá nhỏ nhất. Vị trí đứng cuối cùng của phần tử này là ở cuối mảng. Như vậy chúng ta sẽ di chuyển phần tử này về cuối mảng, sau khi thực hiện phép biến đổi này thì một khoá trong mảng đã vào đúng vị trí của nó trong sắp xếp. Nếu không kể khoá nhỏ nhất này thì phần còn lại của mảng ứng với cây nhị phân hoàn chỉnh sẽ không còn là đống nữa, ta lại phải thực hiện lại phép vun đống cho cây và lại thực hiện tiếp việc đổi chỗ cho khoá ở đỉnh đống với khoá ở đáy đống .... Cho đến khi cây chỉ còn một nút thì các khoá đã được sắp xếp vào đúng vị trí của nó. Cụ thể với Heap ở trên Từ heap ở trên, hoán đổi giá trị của a[1] =2 với a[10] = 12 ta đã có a[10] = 2 là giá trị nhỏ nhất vào đúng vị trí. Cắt bỏ nút a[10] ra khỏi cây, như vậy phần cuối cùng của mản chỉ gồm một phần tử a[10] đã được sắp. Hình 12 Sau khi thực hiện hoán đổi cây không còn là heap thực hiện việc vun đống đổi vị trí của a[1] về đúng vị trí ta có đống mới. Hình 13 Tiếp tục hoán đổi giá trị a[1] với a[9] ta đã sắp được a[9] = 2 vào đúng vị trí trong mảng. Cắt bỏ nút a[9] ra khỏi cây, như vậy phần cuối cùng của mảng gồm hai phần tử a[9], a[10] đã được sắp. Hình 14 Sau khi đổi chỗ cây không còn là đống thực hiện phép vun đống ta được đống mới. Hình 15 Tiếp tục thực hiện quá trình trên ta được một mảng sắp theo thứ tự giảm là Hình 16 II.Ứng dụng đống tổ chức hàng đợi có ưu tiên 1.Ứng dụng của đống trong giải thuật Hufman. a) Giới thiệu về thuật toán Huffman: -Trong khoa học máy tính và lý thuyết thông tin, mã Hufffman là một thuật toán mã hoá dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hieenk các kí tự cần mã hoá để xây dựng bộ một bộ ã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hoá là nhỏ nhất. - Thuật toán được đề xuất bởi Đavi A.Huffman khi ông còn là sinh viên Ph.D.tại MIT, và công b ố năm 1952 trong bài báo “ A Methord for the Construction of Minimum- Redundancy Codes”. Sau này Huffman đã trở thành một giảng viên ở MIT và sau đó ở khoa Khoa học máy tính của Đại học California, Santa Cruz, Trường Ký nghệ Baskin. - Mã Huffman là một mã tiền tố. Sau đây là khái niệm về mã tiền tố: b) Mã tiền tố (prefix-free binary code) - Khi mã hoá một tài liệu có thể không sử dụng đến tát cả 256 kí hiệu. Hơn nữa trong tài liệu chữ cái “a” chỉ có thể xuất hiện 1000000 lần còn chữ cái “A” có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hoá ký hiệu, hơn nữa độ dài (số bít) dành cho mỗi kí hiệu có thể khác nhau, kí hiệu nào xuất hiện nhiều lần thì nên dùng số bit ít, ký hiệu nào xuất hiện ít thì có thể mã hía bằng từ mã dài hơn. Như vậy ta có việc mã hoá với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, khi giải mã ta làm thế nào phân biệt được xâu bít nào là mã hoá của kí hiệu nào. Một trong các giải pháp là dùng các dấu phẩy (“,”) hoặc một kí hiệu quy ước nào đó để tách từ mã của các ký tự đứng cạnh nhau. Nhưng như thế số các dấu phẩy sẽ chiếm một khoảng đáng kể trong bản mã. Một cách giải quyết khác dẫn đến khái niệm mã tiền tố. - Mã tiền tố là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố ( phần đầu) của từ mã một ký hiệu khác trong bộ mã ấy. - Đương nhiên mã hoá với độ dài không đổi là mã tiền tố. - Ví dụ : Giả sử mã hoá từ “HONGHAI”, tập các ký hiệu cần mã hoá gồm 6 chữ cái “H”,”O”,”N”,”G”,”A”,”I” -Nếu mã hoá cho một chữ cái chẳng hạn “H”=00, “O”= 01, “N” = 100,”G”=101,”A”=110,”I”=111. Khi đó mã hoá của cả từ là 000110010100110111. Để giải mã ta đọc bit và đối chiếu với bảng mã. -Nếu mã hoá “H”=0, “O”=01, “N” = 100,”G”=101,”A”=110,”I”=111 thì bộ từ mã này không là mã tiền tố vì từ mã của “H” là tiền tố của từ mã của “O”. Để mã hoá cả từ HONGHAI phải đặt dấu ngăn cách vào giữa các từ mã 0,01,100,101,110,111. Nếu mã hoá “H”=00, “O”= 01, “N” = 100,”G”=101,”A”=110,”I”=111 thì bộ mã này là tiền tố. Với bộ mã tiền tố này khi mã hoá xâu “HONGHAI” ta có 000110010100110111. Biểu diễn mã tiền tố trên cây nhị phân: Nếu có một cây nhị phân n lá ta có thể tạo một bộ mã tiền tố cho n ký hiệu bằng cách đặt mỗi ký hiệu voà một lá. Từ mã của một ký hiệu được tạo ra khi đi từ gốc tới lá chứa ký hiệu đó, nếu đi qua cạnh trái thì ta thêm số 0, đi qua cạnh phải thì thêm số 1. Ví dụ: Cây sau đây biểu diễn bộ mã của H, O, N, G, A, I trong ví dụ trên. Hình 17 c) Giải thuật Huffman Một ứng dụng nữa của Heap là vào giải thuật Huffman. Thành lập cây nhị phân từ tập hợp các ký hiệu trong thông báo, mỗi ký hiệu là một nút lá cây. Cách thành lập cây như sau: *Dữ liệu: + Input: Bảng n chữ cái Ch[1..n] .Tập các trọng số (tần suất xuất hiện) của n ký tự cho dưới dạng mảng count[1..n] + Output : Cây T biểu diễn mã tiền tố tối ưu của n ký tự đã cho. *Giải thuật: Trong giải thuật tham lam giải bài toán xây dựng cây mã tiền tố tối ưu của Huffman, ở mỗi bước ta chọn hai chữ cái có tần số thấp nhất để mã hóa bằng từ mã dài nhất. Giả sử có tập A gồm n ký hiệu và hàm trọng số tương ứng W(i),i = 1..n. Khởi tạo: Tạo một rừng gồm n cây, mỗi cây chỉ có một nút gốc, mỗi nút gốc tương ứng với một kí tự và có trọng số là tần số/tần suát của kí tự đó W(i). Lăp: Mỗi bước sau thực hiện cho đến khi rừng chỉ còn một cây: Chọn hai cây có trong số ở gốc nhỏ nhất hợp thành một cây bằng cách thêm một gốc mới nối với hai gốc đã chọn. Trọng số của gốc mới bằng tổng trọng số của hai gốc tạo thành nó. Như vậy ở mỗi bước số cây bớt đi một. Khi rừng chỉ còn một cây thì cây đó biểu diễn mã tiền tố tối ưu với các ký tự đặt ở các lá tương ứng.Trong mỗi bước của thuật toán xây dựng cây Huffman, ta luôn phải chọn ra hai gốc có trọng số nhỏ nhất. Để làm việc này ta sắp xếp các gốc vào một hàng đợi ưu tiên theo tiêu chuẩn trọng số nhỏ nhất. Một trong các cấu trúc dữ liệu thuận lợi cho tiêu chuẩn này là cấu trúc Heap (với phần tử có trọng số nhỏ nhất nằm trên đỉnh của Heap). Trong đoạn giả mã này ta dựa trên một mảng các ký hiệu A[1..n] có tần suất tương ứng là W[1..n]. + Tạo hàng đợi bằng đống: Ta tạo một đống trên cơ sở sắp xếp lại các chỉ số của A và W. Ta lưu trữ đống dưới dạng mảng, kí hiệu nó là Heap[1..n]. Trước hết đưa chỉ số của các chữ cái theo thứ tự ban đầu vào mảng Heap[1..n] với Heap[i]=i . với mọi i=1..n. Ta sẽ lưu trữ cấu trúc của cây mã Huffman vào một mảng. Cây Huffman gồm n lá mỗi lá chứa chỉ số của chữ cái tương ứng. Mỗi lần ghép 2 cây thành một ta phải thêm một đỉnh, như vậy cây biểu diễn mã Huffman gồm 2.n-1 đỉnh. Ta kí hiệu cây này là Huff[1..2n-1]. Vì mỗi gốc mới bổ sung đều có trọng số nên ta mở rộng mảng W[1..n] các trọng số thành mảng W' [1..2n+1]. Gọi m là số đỉnh của cây sẽ xây dựng. lúc đầu ta có n lá, đỉnh bổ sung lần đầu sẽ là n+1, lần thứ 2 là n+2, ... Khi lấy ra hai kí tự có tần số nhỏ nhất chẳng hạn kí tự thứ i làm con trái và kí tự thứ j làm con phải của đỉnh mới bổ sung có chỉ số m ta đặt Huff[i]=-m, Huff[j]=m. d)Thời gian thực hiện: -Việc tạo hàng đợi ưu tiên dưới dạng đống cực tiểu mất O(n) thời gian. -Vòng lặp for gồm n-1 bước. - Mỗi bước trong vòng for thực hiện việc xuất hiện phần tử nhỏ nhất và vun lại đống mất O(ln n) thời gian. - Do đó vòng for mất O(nlogn) thời gian. - Do đó độ thời gian thực hiện giải thuật là O(nlogn) 2.Ứng dụng của đống trong giải thuật xây dựng cây bao trùm nhỏ nhất của đồ thị liên thông : Tìm cây bao trùm nhỏ nhất (tiếng Anh: minimum spanning tree) là bài toán tối ưu có nhiều ứng dụng trong thực tế. Nó có thể là bài toán tìm hệ thống liên thông với chi phí nhỏ nhất, hoặc ngược lại, vói lợi nhuân lớn nhất. Hai thuật toán tìm cây bao trùm nhỏ nhất và lớn nhất thường được nhắc đến là thuật toán Prim và thuật toán Krusskal. a)Bài toán Cho G=(X,E) là một đồ thị liên thông. Ngoài ra, một hàm trọng số W(e) nhận các giá trị thực, xác định trên tập các cạnh E của G. Cả hai thuật toán Prim và Kruskal đều dựa trên tư tưởng của các giải thuật tham lam: Ở mỗi bước của thuật toán ta chọn và bổ sung vào cây cạnh có trọng số nhỏ nhất có thể. b)Giải thuật Prim Giải thuật Prim dựa trên cấu trúc của giải thuật tìm cây bao trùm theo chiều rộng hoặc chiều sâu, chỉ thay đổi về tiêu chuẩn chọn đỉnh sẽ bổ sung vào cây ở tưng bước. Robert Clay Prim (sinh 1921 tại Sweetwater, Texas) là một nhà toán học và khoa học máy tính Mỹ. Năm 1941 ông đã lấy bằng cử nhân ở khoa kỹ thuật điện đại học Princeton. Sau này năm 1949, ông nhận bằng Ph.D. về toán học cũng tại đây. Giải thuật mang tên Prim được tìm ra từ năm 1930 bởi nhà toán học Vojtěch Jarník và do Prim hoàn thiện vào năm 1957. c)Mô tả Gọi T là cây bao trùm sẽ xây dựng 1.Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có cạnh nào. 2.Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc. 3.Nếu G còn có các đỉnh không thuộc T, vì G liên thông nên có các cạnh nối một đỉnh trong T với một đỉnh ngoài T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T. Quay lại 2. d)Giả mã Giải thuật trình bày Prim ở trên dễ dàng thực hiện khi ta quan sát một đồ thị được biểu diễn trên mặt phẳng với một số ít đỉnh. Liệu có thể sử dụng một hàng đợi (queue) giống như trong giải thuật tìm cây bao trùm theo chiều sâu không? Có. Nhưng điều khác biệt là ta sẽ sử dụng một hàng đợi có ưu tiên, tiêu chuẩn ưu tiên ở đây là cạnh nối đỉnh sẽ được bổ sung vào T là nhỏ nhất. Một cấu trúc thuận lợi cho hàng đợi có ưu tiên là cấu trúc đống (heap) như đã sử dụng trong giải thuật sắp xếp vun đống hoặc giải thuật xây dựng mã Huffman. Giả sử G=(X,E) là đồ thị liên thông, Ajd(u), là danh sách đỉnh kề của đỉnh u. L(e) là hàm trọng số xác đinh với moi cạnh . Trong đoạn mã sau ta dùng hàm COLOR(u) để tô màu các đỉnh của G bằng các màu WHITE, GRAY, BLACK để chỉ các trạng thái chưa xét, đang xét và đã xét xong của mỗi đỉnh, hàm PARENTS(u) chỉ đỉnh cha của đỉnh u trong cây, hàm DISTAN(u,T) chỉ trọng số nhỏ nhất của các cạnh nối từ đỉnh u ngoài T đến các đỉnh trong T. Ta cũng sử dụng một cấu trúc HEAP làm hàng đợi ưu tiên chứa các đỉnh đang chờ xét. Ở bước khởi tạo, một đỉnh r bất kỳ được đưa vao Heap. Số các phần tử của đống là n=1. Cho đến khi hàng đợi Heap còn khác rỗng ta thực hiện các bước sau: lấy đỉnh u nằm ở gốc Heap ra để đưa vào cây. Đối với đỉnh u mới được bổ sung vào cây ta duyệt qua tất cả các đỉnh v thuộc danh sách kề với nó. Nếu đỉnh v chưa thuôch T và không nằm trong đống ta chèn v vào đống, nếu đỉnh v đã nằm trong đống đợi ta tính lại khoảng cách từ v của nó với tập các đỉnh đã nằm trong T, và vun lại đống. Sau khi tất cả các đỉnh ) đã duyệt qua bằng cách ấy thì thì đỉnh u đã được duyệt xong và được đưa vào cây. Chương 4: Mô phỏng và cài đặt cấu trúc đống và ứng dụng. I.Mô phỏng thuật toán. 1.Khái niệm chung về mô phỏng thuật toán. a)Khái niệm về thuật toán. Thật toán được hiểu là tập hợp các quy tắc dùng cho một lớp bài toán nào đó để từ số liệu ban đầu qua một quá trình thao tác dẫn đến kết quả xác định Thuật toán để giải một bài toán là một hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thựch hiện dãy thao tác ấy, từ input của bài toán ta nhận được output cần tìm. b) Mô phỏng thuật toán là gì? Mô phỏng thuật toán là quá trình tách dữ liệu, thao tác và tạo giao diện đồ hoạ mô phỏng cho quá trình đó. 2.Mục đích của mô phỏng thuật toán. Mô phỏng thuật toán sử dụng đồ hoạ để mô tả các cấu trúc dữ liệu bên trong của thuật toán được thực hiện trong chương trình và biểu diễn sự thay đổi của các cấu trúc dữ liệu trong mỗi trạng thái thực thi và các hoạt động của chương trình. Trong suốt quá trình mô tả, người sử dụng có thể thấy từng bước thực hiện của chương trình và có thể thấy được những chi tiết nhỏ của thuật toán và hiểu sâu hơn về nó. Vì thế, mô phỏng thuật toán giúp cho người sử dụng hiểu thuật toán. Trong quá trình mô phỏng, người sử dụng có thể thấy chương trình của họ được thi hành như thế nào, đánh giá sự thay đổi của dữ liệu qua mỗi bước và nó sẽ ảnh hưởng đến bước tiếp theo như thế nào. Nó giúp người sử dụng phát hiện ra lỗi của chương trình (nếu có), Từ đó có thể tìm ra lỗi và sửa lại chương trình để nó chạy chính xác và ổn định hơn. a) Các yêu cầu về mô phỏng thuật toán. * Phản ánh đúng nội dung của thuật toán. * Có thể thực hiện giải thuật theo từng bước 1 để theo dõi giá trị của các biến và các đối tương trong bài toán. * Có hình ảnh động (có thể có âm thanh khi cần) để mô tả trực tiếp quá trình thi hành của thuật toán. * Có thể kiểm định thuật toán trong trường hợp ngẫu nhiên, trường hợp xấu nhất, trường hợp tốt nhất. *Tạo mức độ sử dụng khác nhau cho người học. 3.Cấu trúc tổng quan của mô phỏng thuật toán: 4. Quy trình thiết kế nhiệm vụ của mô phỏng thuật toán. Quy trình thiết kế nhiệm vụ mô phỏng thuật toán được tiến hành theo sơ đồ sau: a) Nghiên cứu phân tích giải thuật. Trong khi giải bài toán chúng ta có thể có một số giải thuật khác nhau nên cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt nhất. Thông thường ta sẽ căn cứ vào các tiêu chuẩn sau: Giải thuật đúng đắn. Giải thuật đơn giản. Giải thuật thực hiện nhanh. b) Xây dựng mô hình dữ liệu vào và dữ liệu ra. Khi xây dựng mô phỏng dữ liệu và dữ liệu ra của bài toán chúng ta cần xác định đặc điểm của dữ liệu vào: dừng dữ liệu có sẵn của chương trình, dùng dữ liệu sinh ngẫu nhiên, hoặc dùng dữ liệu do người dùng tự nhập vào. Dữ liệu vào được xem là giả thuyết của bài toán. c) Cơ chế sinh dữ liệu vào cho bài toán. Như đã nói ở trên thì chúng ta có 3 cơ chế sinh dữ liệu cho bài toán, đó là dữ liệu sinh ngẫu nhiên, dữ liệu mẫu, và dữ liệu do người dùng nhập vào Dữ liệu sinh ngẫu nhiên do sử dụng hàm Rundom để sinh giá trị của dữ liệu hạn chế trong một khoảng nào đó, hoặc mặc định sinh bao nhiêu tuỳ theo mong muốn của người lập trình. Dữ liệu ngẫu nhiên thường để kiểm định tính đúng đắn của chương trình trong các trường hợp bất kì. Dữ liệu mẫu là dữ liệu đã được ghi lại từ trước, khi muốn sử dụng chỉ việc lấy ra. Có tác dụng là cho người sử dụng đỡ mất công nhập lại dữ liệu (trong trường hợp dữ liệu quá lớn thì mất thời gian), hoặc để kiểm định thuật toán trong các trường hợp xấu, trung bình hoặc tốt. Dữ liệu nhập là dữ liệu do người dùng nhập vào từ bàn phím, đa số thì dạng dữ liệu này thường được sử dụng vì người dùng muốn kiểm định dữ liệu do chính mình nhập vào. d) Phân tích dữ l