ĐỀ 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
- Điều hướng trang này:
- Các thuật toán tìm MST
Cơ sở lý thuyếtCây bao trùm Giả định ban đầu ta có một đồ thị có dạng như Hình 3: Hình 3. Ví dụ về đồ thị với các đỉnh 1, 2, 3, 4, 5, 6 Nhắc đến định nghĩa, cây bao trùm (spanning tree) là đường đi mà ở đó có đi qua tất cả các đỉnh của đồ thị, sao cho đường đi này không đóng thành vòng. Như vậy ta dễ dàng suy ra được một số cây bao trùm tùy thuộc vào đỉnh gốc được chọn ban đầu như Hình 4. Hình 4. Một số ví dụ về cây bao trùm Cây bao trùm tối thiểu Một biểu đồ có trọng số cạnh, chi phí ứng với mỗi cạnh trong cây, ký hiệu tổng quát d(u, v) với u, v là điểm đầu và điểm cuối. Minh họa ở Hình 5, ta chọn cây bao trùm có điểm xuất phát từ 1, sau đó đi đến 2, 3 rồi 4, vậy chi phí của đường đi này chính bằng chi phí đi từ 1 đến 2 ký hiệu d(1, 2), cộng với chi phí đi từ 2 đến 3, … và ta có tổng là d(1, 2) + d(2, 3) + d(3, 4) = 4 + 6 + 3 = 13. Hình 5: Ví dụ về đồ thị có trọng số cạnh Áp dụng tính chất về cách tính trọng số cho một cây bao trùm cho một đồ thị nói chung, thì MST của đồ thị phải có trọng số cạnh (hay tổng trọng số của các cạnh) không lớn hơn trọng số của bất kỳ cây bao trùm nào khác và có thể có nhiều MST trong một đồ thị. Vậy để giải quyết bài toán tìm MST, cách đơn giản áp dụng từ tính chất trên, ta sẽ liệt kê ra tất cả các cây bao trùm và tìm xem cây bao trùm nào có tổng trọng số nhỏ nhất sẽ kết luận đó là MST. Nhưng nếu làm theo cách đó với một đồ thị có quy mô phức tạp hơn thì sẽ không thể khả thi, cũng như mất nhiều thời gian và công sức. Phần tiếp theo, sẽ là một số thuật toán tìm MST được sử dụng rộng rãi thông qua nghiên cứu của nhóm. Các thuật toán tìm MST3.1. Thuật toán không ngẫu nhiên Thuật toán PRIM Ý tưởng của thuật toán: Thuật toán Prim sẽ bắt đầu bằng việc chọn ngẫu nhiên một đỉnh bất kì và tiếp tục thêm các cạnh có trọng số nhỏ nhất cho đến khi có đủ tập hợp các đỉnh. Các bước để thực hiện được diễn giải mô phỏng với đồ thị có dạng như Hình 6: Hình 6: Đồ thị minh họa cho thuật toán tìm MST Chú thích: Đồ thị G=(V, E) có V đỉnh và E cạnh. Tập hợp các đỉnh của đồ thị V = {1, 2, 3, 4, 5, 6} (Viết tắt của vertex nghĩa là đỉnh). Tập hợp các cạnh của E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6)} (Viết tắt của edge nghĩa là cạnh). Ta tạo ra 2 tập hợp U và T, U là tập hợp các đỉnh và T là tập hợp các cạnh tạo ra cây khung nhỏ nhất. Bước 1: Khởi tạo tập hợp đỉnh V rỗng U={Ø}, tập hợp cạnh E rỗng T={Ø}. Bước 2: Chọn ngẫu nhiên 1 đỉnh và thêm vào tập hợp các đỉnh V. ví dụ chúng ta chọn đỉnh 1. Sau bước này, ta có U={1} và T={Ø}. Bước 3: Chọn 1 đỉnh chưa có trong tập V mà có kết nối với 1 đỉnh trong V, cạnh tạo từ 2 đỉnh đó phải là cạnh có trọng số nhỏ nhất và thêm vào tập hợp các cạnh E. Ở đây, ta sẽ tìm được cạnh (1, 3) do khoảng cách nhỏ nhất với giá trị là 1. Sau bước này ta có U={1, 3} và T={(1, 3)}. Bước 4: Lặp lại bước 3 cho đến khi cây khung hoàn thành (Cách nhận biết cây khung hoàn thành là tất cả các đỉnh của cây khung đều đã xuất hiện trong V), cây khung nhỏ nhất là cây khung được tạo từ tập các cạnh trong E. Kết quả là ta tìm ra cạnh (3, 6) với giá trị 4. Sau bước này ta có U={1, 3, 6} và T={(1, 3), (3, 6)}. Bước 5. Do tập U mới chỉ có 3/6 đỉnh, ta tiếp tục đi tìm cạnh nhỏ nhất chưa khám phá mà 1 đỉnh của nó trong U. Kết quả là ta tìm được cạnh (6, 4). Bây giờ U={1, 3, 6, 4} và T={(1, 3), (3, 6), (6, 4)}. Bước 6. Do tập U mới chỉ có 4/6 đỉnh, tiếp tục tìm cạnh nhỏ nhất chưa có trong T mà 1 đỉnh của nó trong U. Ta tìm được cạnh (3,2) với giá trị 5. Sau buớc này U={1, 3, 6, 4, 2} và T={(1, 3), (3, 6), (6, 4), (3, 2)}. Bước 7. Do tập U mới chỉ có 5/6 đỉnh, tiếp tục tìm cạnh nhỏ nhất chưa có trong T mà 1 đỉnh của nó trong U. Ta tìm được cạnh (2, 5) với giá trị 3. Lúc này tập U đã có 6/6 đỉnh nên thuật toán kết thúc. Sau khi áp dụng xong thuật toán Prim, ta có U={1, 3, 6, 4, 2, 5} và T={(1, 3), (3, 6), (6, 4), (3, 2), (2, 5)}. Tập hợp các cạnh T={(1, 3), (3, 6), (6, 4), (3, 2), (2, 5)} tạo thành cây khung có tổng trọng số nhỏ nhất. Tổng trọng số của cây khung nhỏ nhất là:1 + 4 + 2 + 5 + 3 = 15. Hình 7: MST của đồ thị Hình 6. Mã giả: Ở một dạng tổng quát, với T là tập hợp khởi tạo ban đầu, lưu trữ các đỉnh theo thứ tự của MST, s là đỉnh ban đầu được chọn.
Độ phức tạp của thuật toán Một cách lập trình đơn giản sử dụng ma trận kề và tìm kiếm toàn bộ mảng để tìm cạnh có trọng số nhỏ nhất có thời gian chạy O(V2). Bằng cách sử dụng cấu trúc dữ liệu đống nhị phân và danh sách kề, có thể giảm thời gian chạy xuống O(ElogV). Bằng cách sử dụng cấu trúc dữ liệu đống Fibonacci phức tạp hơn, có thể giảm thời gian chạy xuống O(E + V log V), nhanh hơn thuật toán trước khi đồ thị có số cạnh E=ω(V). Thuật toán Kruskal Là thuật toán tham lam tìm điểm tối ưu cục bộ với hy vọng tìm ra điểm tối ưu toàn cục. Chúng tôi bắt đầu từ các cạnh có trọng lượng thấp nhất và tiếp tục thêm các cạnh cho đến khi đạt được mục tiêu. Các bước để triển khai thuật toán của Kruskal như sau: 1. Sắp xếp tất cả các cạnh từ trọng lượng thấp đến cao 2. Lấy cạnh có trọng số thấp nhất và thêm nó vào cây khung. Nếu thêm cạnh tạo ra một chu trình, thì bỏ cạnh này. Ngược lại, thêm vào cây khung. 3. Tiếp tục thêm các cạnh cho đến khi chúng ta đạt được cây bao trùm tối thiểu * Bắt đầu với một đồ thị có trọng số: B ước 1: Tiến hành sắp các cạnh có trọng số từ thấp đến cao Bước 2: Tìm và kết nối các cạnh có trong số từ thấp đền cao
* Mã giả thuật toán: tải về 0.76 Mb. Chia sẻ với bạn bè của bạn:
| ||||||||||||||||||||||||||||||||