ĐỀ TÀI: CÂy bao trùm nhỏ nhất học viên thực hiệN
tải về 0.76 Mb.
|
ATHTTT DDOS
| MST-KRUSKAL (G = (V,E), w)
1. A := ∅ -> O(1) 2. for each vertex v ∈ V[G] 3. do MAKE-SET(v) 4. Quick sort random – sắp xếp theo trọng số tăng dần w -> O (E log E) 5. for each edge (u,v) ∈ E, theo thứ tự của trọng số tăng dần -> O(E lg V) 6. do if FIND-SET(u) ≠ FIND-SET(v) -> O(E lg V) 7. then A := A U {(u,v)} -> O(E lg V) 8. UNION( u,v ) -> O(E lg V) 9. return A + MAKE-SET(v) 1. p[v] := v 2. rank[v] := 0 + FIND_SET (v) 1. if v ≠ p[v] 2. then p[v]:= FIND-SET(p[v]) 3. return p[v] + UNION ( u ,v) 1. LINK ( FIND-SET(u) , FIND-SET(v) ) LINK ( u ,v) 1. if rank[u] > rank[v] 2. then p[v] := u 3. else p[u] := v 4. if rank[u]=rank [v] 5. then rank[v] := rank [v] +1 Độ phức tạp: T(n) =O (E log E) + O(E log V) c) Thuật Toán Boruvka Thuật toán này được xuất bản lần đầu năm 1926 bởi Otakar Boruvka dưới dạng một phương pháp để xây dựng mạng lưới điện cho Moravia. Thuật toán này được tìm ra lại nhiều lần sau đó bởi Choquet năm 1938; bởi Florek, Łukasiewicz, Perkal, Steinhaus, và Zubrzycki năm 1951; và một lần nữa bởi Sollin năm 1965. Do Sollin là nhà nghiên cứu khoa học máy tính duy nhất trong danh sách trên sống ở một quốc gia nói tiếng Anh, nên thuật toán này thường được gọi là thuật toán Sollin, đặc biệt là trong tính toán song song. Ban đầu thuật toán khởi tạo cây bao trùm cần tìm là một tập rỗng và dần dần từng bước thêm các cạnh vào tập hợp đó. Trong mỗi bước, thuật toán kiểm tra một đỉnh bất kì của đồ thị, thêm vào cây bao trùm cạnh nhỏ nhất kề với đỉnh đó, và hợp hai đỉnh ở hai đầu cạnh mới thêm lại làm một. Lặp lại bước trên cho tới khi đồ thị chỉ còn đúng một đỉnh. Mã giả thuật toán: Input: Một đồ thị liên thông G có các cạnh có trọng số BorUvka(G(V,E),w) T←∅ while V≠1 X← set of safe edges T←T∪X G←G/X return Độ phức tạp: O((n+m)log2(n)) 3.2. Thuật toán ngẫu nhiên Randomized Algorithms là những thuật toán sử dụng mức độ ngẫu nhiên như một phần của logic. Thuật toán thường sử dụng các bit ngẫu nhiên như một đầu vào phụ trợ để hướng dẫn hành vi của nó, với kỳ vọng đạt được hiệu suất tốt trong "trường hợp trung bình" trên tất cả các lựa chọn ngẫu nhiên được xác định; do đó thời gian chạy hoặc đầu ra (hoặc cả hai) đều là các biến ngẫu nhiên. Trong thực tế, các thuật toán ngẫu nhiên được tính gần đúng bằng cách sử dụng bộ tạo số giả ngẫu nhiên thay cho nguồn bit ngẫu nhiên thực sự; việc triển khai như vậy có thể sai lệch so với dự kiến. Các thuật toán ngẫu nhiên cung cấp các giải pháp đơn giản và hiệu quả cho một số vấn đề. Kỹ thuật này được áp dụng cho quicksort, từ điển andomised và thuật toán hình học: Binary planar partiontions và bao lồi trên mặt phẳng… Tất cả các thuật toán đều đơn giản, nhưng nếu không có kỹ thuật thích hợp, phân tích có thể khá lộn xộn. Có thể nói, thuật toán ngẫu nhiên sẽ cho ta một thời gian kì vọng thực hiện tốt nhất. Có hai lợi thế chính đối với các thuật toán ngẫu nhiên: + Chạy nhanh hơn các thuật toán xác định. + Dễ mô tả và triển khai hơn các thuật toán xác định có hiệu suất tương đương. 3.2.1 Randomized quicksort Quicksort là một thuật toán quen thuộc, thường được sử dụng trong các bài toán sắp xếp. Nhiều phiên bản xác định của thuật toán này yêu cầu thời gian O (n2) để sắp xếp n số cho một mảng bất kỳ. Tuy nhiên, cùng với bài toán sắp xếp như thế cùng bô dữ liệu đầu vào thì khi chọn randomized-quicksort thì nó có xác suất hoàn thành trong thời gian O (n log n). * Mô tả: Randomized quicksort giống với quy trình Sắp xếp Quicksort. Điểm khác biệt duy nhất là phần tử chốt được chọn ngẫu nhiên. Đầu vào: Một tập hợp các phần tử A Dữ liệu ra: Các phần tử của A được sắp xếp theo thứ tự tăng dần (giảm dần). 1. Chọn ngẫu nhiên một phần tử chốt i từ A: mọi phần tử trong S đều có xác suất được chọn bằng nhau. 2. Bằng cách so sánh từng phần tử của A với i, hãy xác định tập A1 gồm các phần tử nhỏ hơn i và tập A2 là các phần tử lớn hơn i. 3. Tính đệ quy A1 và A2. Xuất ra dãy đã sắp xếp của A1, tiếp theo là dãy đã sắp xếp của A2. Hình: Randomize Quick sort *Mã thuật toán: tải về 0.76 Mb. Chia sẻ với bạn bè của bạn:
|