Đánh giá độ phức tạp của thuật toán kruskal
|
Nội dung Định nghĩa đồ thị có trọng số Bài toán tìm cây khung nhỏ nhất Bài toán tìm đường đi ngắn nhất Giới thiệu Mục tiêu Một trong những ứng dụng quan trọng của lý thuyết đồ thị là nó cung cấp một số mô hình tối ưu có nhiều ý nghĩa thực tế. Trên những mô hình này, người ta đã nghiên cứu khá nhiều những thuật toán hiệu quả và cài đặt thuận tiện, được ứng dụng trong nhiều lĩnh vực hiện đại. Do thời lượng có hạn, trong bài này, chúng tôi chỉ giới thiệu được hai mô hình tối ưu tiêu biểu của lý thuyết đồ thị là bài toán tìm cây khung nhỏ nhất và bài toán tìm đường đi ngắn nhất. Một số mô hình tối ưu nổi tiếng khác như bài toán ghép cặp, bài toán luồng cực đại, ..., chúng tôi hy vọng sẽ được giới thiệu trong những dịp thuận tiện hơn Thời lượng học 6 tiết Sau khi học bài này, các bạn có thể: Hiểu rõ thế nào là đồ thị có trọng số. Biểu diễn được đồ thị có trọng số trên máy tính. Sử dụng được thuật toán Kruskal, thuật toán Prim để tìm cây khung nhỏ nhất. Sử dụng được thuật toán Dijkstra để tìm đường đi ngắn nhất. TÌNH HUỐNG DẪN NHẬP Tình huống: Chọn đường bay Một mạng hàng không gồm 6 sân bay đặt tại 6 thành phố A, B, C, D, E, F và một số tuyến bay giữa các sân bay cùng với giá vé tương ứng: Một hành khách muốn đi từ thành phố F đến thành phố C. Câu hỏi Hãy giúp vị hành khách đó chọn hành trình có tổng chi phí (chỉ tính giá vé) là nhỏ nhất. Ma trận trọng số. Ma trận trọng số là mở rộng tự nhiên của ma trận kề. Nếu như phần tử dòng i cột j của ma trận kề được xác định là 1 hay 0, tùy thuộc vào đỉnh j có kề với đỉnh i hay không thì phần tử này của ma trận trọng số chính là W(i, j). Chú ý: ma trận trọng số W xác định không đầy đủ, chỉ tại những vị trí (i, j) là cạnh, W(i, j) mới xác định. Trong những cài đặt, người ta thường bổ sung vào những vị trí không xác định, một giá trị đặc biệt mang tính quy ước để ma trận W là đầy đủ mà không ảnh hưởng đến tính toán chung. Rõ ràng một đồ thị có trọng số được xác định từ ma trận trọng số của nó và ngược lại. Giống như ma trận kề, nếu đồ thị là vô hướng thì ma trận trọng số của nó là đối xứng. Ví dụ, đồ thị có hướng dưới đây mô tả một mạng hàng không gồm 6 sân bay A, B, C, D, E, F và một số tuyến bay cùng với giá vé tương ứng (đóng vai trò trọng số): có ma trận trọng số là (những chỗ để trống là những chỗ không xác định): A B C D E F A 8 9 B 6 3 C 5 D 7 E 5 4 F 3 Chú ý: Ma trận này chỉ xác định tại 9 vị trí (ứng với 9 cạnh) và không đối xứng. Để bổ sung những chỗ không xác định trong những cài đặt mà vẫn đảm bảo ý nghĩa của bài toán, ta có thể xem những giá trị trên đường chéo chính bằng 0 (với ý nghĩa không tốn tiền mua vé) còn những giá trị khác ta xem bằng cực lớn (với ý nghĩa không thể mua vé được). Danh sách cạnh – trọng số. Danh sách cạnh thông thường được mô tả mỗi phần tử là một cặp đỉnh (có thứ tự nếu đồ thị là có hướng). Bây giờ mỗi phần tử của danh sách cạnh, ta bổ sung thêm một trường thứ ba ghi nhận trọng số cạnh tương ứng. Khi đó ta nhận được danh sách cạnh – trọng số của đồ thị đã cho. Một đồ thị có trọng số được hoàn toàn xác định khi biết danh sách cạnh-trọng số của nó và ngược lại. Chẳng hạn, trong thí dụ trên, danh sách cạnh – trọng số gồm 9 phần tử, mỗi phần tử gồm ba trường, hai trường đầu ghi cặp đỉnh tạo thành cạnh (theo thứ tự), trường cuối ghi trọng số của cạnh này: {AB8, AD9, BC6, BD3, CD5, DE7, EA5, EF4, FA3}. Danh sách kề – trọng số. Danh sách kề của mỗi đỉnh bao gồm các đỉnh kề với đỉnh đó. Bây giờ ta thêm vào mỗi phần tử của danh sách này, trọng số của cạnh tương ứng. Khi đó ta nhận được danh sách kề – trọng số của đỉnh đang xét. Tập hợp các danh sách kề-trọng số của tất cả các đỉnh của đồ thị được gọi là danh sách kề-trọng số của đồ thị. Một đồ thị có trọng số được hoàn toàn xác định khi biết danh sách kề-trọng số của nó và ngược lại. Chẳng hạn, danh sách kề-trọng số của đồ thị trong thí dụ trên gồm: o Danh sách kề-trọng số đỉnh A: {B8, D9} o Danh sách kề-trọng số đỉnh B: {C6, D3} o Danh sách kề-trọng số đỉnh C: {D5} o Danh sách kề-trọng số đỉnh D: {E7} o Danh sách kề-trọng số đỉnh E: {A5, F4} o Danh sách kề-trọng số đỉnh F: {A3} Giống như danh sách kề, các danh sách này thường được cài đặt bằng cấp phát động dưới dạng một danh sách liên kết. Điều này giúp cho việc xử lý đồ thị được mềm dẻo và linh hoạt, phù hợp với những bài toán liên quan đến những đồ thị luôn thay đổi.
8.2. Phát biểu bài toán Cho một đồ thị vô hướng liên thông có trọng số: G = (V, E, W) trong đó V là tập đỉnh, E là tập cạnh và W là trọng số. Với mỗi cây khung T của G, ta định nghĩa trọng số của T là W(T) xác định bởi tổng trọng số các cạnh thuộc T: e T W(T) W(e) Bài toán đặt ra là tìm cây khung T của G sao cho W(T) là nhỏ nhất. Cây khung tìm được, được gọi là cây khung nhỏ nhất của đồ thị đã cho. Trong bài toán tìm cây khung nhỏ nhất, một cách hình ảnh, các trọng số còn được gọi là các “độ đo” (độ đo của cạnh, độ đo của cây khung). Như vậy, cây khung nhỏ nhất là cây khung có độ đo ngắn nhất. Thông thường, trọng số của cạnh đánh giá chi phí của cạnh đó (thời gian, tiền bạc, ...). Với ý nghĩa này, cây khung nhỏ nhất cho ta một mô hình xây dựng một mạng liên thông có chi phí rẻ nhất. Để thí dụ, ta xét bài toán xây dựng mạng đường sắt dưới đây: “Có n thành phố (đánh số từ 1 đến n). Cần xây dựng một hệ thống đường sắt nối các thành phố này sao cho từ một thành phố ta có thể đến mọi thành phố khác bằng phương tiện xe hỏa. Biết chi phí xây dựng tuyến đường nối thành phố i với thành phố j là W(i, j), 1 ≤ i, j ≤ n. Hãy tìm một phương án xây dựng hệ thống thỏa mãn yêu cầu đã nêu với chi phí là rẻ nhất”. Lời giải của bài toán là xây dựng cây khung nhỏ nhất của đồ thị đầy đủ n đỉnh (mỗi đỉnh là một thành phố) với trọng số cạnh (i, j) là W(i, j). Một giải pháp tầm thường để tìm cây khung nhỏ nhất là xây dựng tất cả các cây khung của đồ thị đang xét rồi sau đó so sánh các độ đo của chúng. Tuy nhiên điều này là sẽ được khởi tạo từ một đỉnh đầu tiên nào đó được chọn vào cây khung, sau đó chúng sẽ được điều chỉnh mỗi khi xong một bước kết nạp, sao cho từ các nhãn này, ta xác định được đỉnh sẽ được nạp ở bước kế tiếp. Đỉnh đã được kết nạp vào cây khung dĩ nhiên không được xét tiếp để đảm bảo không có chu trình. Khi các đỉnh được xét hết cũng là lúc nhận được cây khung cần tìm. Với kỹ thuật gán nhãn (có thể dùng mảng để lưu trữ các nhãn này), thuật toán Prim dễ dàng được thực hiện bằng một chương trình. Để giúp các bạn đọc thuận tiện trong việc triển khai các ứng dụng, chúng tôi giới thiệu chi tiết nội dung này. Giả thiết đồ thị đang xét có n đỉnh và có ma trận trọng số là W (chú ý W là đối xứng). Để khỏi phải loại trừ những chỗ không xác định trong khi phát biểu thuật toán, ta bổ sung ma trận W cho đầy đủ, trong đó những giá trị trên đường chéo chính bằng 0 và những giá trị tại những chỗ không có cạnh bằng cực lớn (điều này không ảnh hưởng gì đến tính toán chung vì cây khung nhỏ nhất không bao giờ đi qua những cạnh này). Khi đó, các bước của thuật toán Prim có thể phát biểu cụ thể như sau: Bước 1. Khởi tạo: chọn đỉnh xuất phát s (tùy ý), gán nhãn cho mọi đỉnh u theo công thức: a(u) := s; b(u) := W(s, u). Cây khung T lúc ban đầu chưa có cạnh nào. Tập đỉnh còn lại U bao gồm mọi đỉnh ngoại trừ s (s là đỉnh đầu tiên vào cây khung). Bước 2. Kiểm tra điều kiện dừng: Nếu U rỗng (tất cả các đỉnh đã vào cây khung) thì kết thúc, T là cây khung nhỏ nhất cần tìm. Trái lại sang bước 3. Bước 3. Kết nạp: chọn u* trong U sao cho b(u*) đạt nhỏ nhất trong tập {b(u), u thuộc U}, sau đó kết nạp cạnh (a(u*), u* ) vào T và loại u* ra khỏi U (u* đã vào cây khung). Bước 4. Sửa nhãn: với mọi đỉnh u thuộc U, thực hiện quy tắc sửa nhãn sau đây: nếu u thỏa mãn b(u) > W(u*, u) thì sửa nhãn u theo công thức: a(u) := u*, b(u) := W(u*, u). Sau đó quay về bước 2 để thực hiện lần lặp mới. Các bước của thuật toán có thể mô tả trong đoạn chương trình (mô phỏng Pascal): (Khởi tạo); WHILE (U khác rỗng) DO BEGIN (Kết nạp); (Sửa nhãn); END; (ghi nhận cây khung ngắn nhất); Để kiểm tra tính đúng đắn của thuật toán Prim, bạn đọc có thể tham khảo [3]. Quay lại thí dụ trên nhưng đồ thị được cho bởi ma trận trọng số W (chỉ viết một nửa vì đối xứng): A B C D E F A 0 8 ∞ 9 5 3 B 0 6 3 ∞ ∞ C 0 5 ∞ ∞ D 0 7 ∞ E 0 4 F 0 Trong đó W đã được bổ sung đầy đủ (ký hiệu ∞ chỉ giá trị cực lớn). Chọn đỉnh đầu tiên vào cây khung là A. Kết quả tính toán theo từng bước của thuật toán được ghi vào bảng sau (mỗi cột của bảng ứng với một đỉnh được xét, mỗi dòng của bảng ứng với các nhãn của đỉnh trong từng bước tính, đỉnh nào được chọn có dấu , đỉnh nào bị loại (không tham gia xét tiếp) các dòng sau bỏ trắng) B C D E F A, 8 A, ∞ A, 9 A, 5 A, 3 A, 8 A, ∞ A, 9 F, 4* A, 8 A, ∞ E, 7* D, 3* D, 5 D, 5* Kết quả nhận được cây khung nhỏ nhất gồm các cạnh AF, FE, ED, DC và DB với độ đo bằng 3 + 4 + 7 + 3 + 5 = 22. Bạn đọc có thể làm lại thí dụ trên bằng một đỉnh xuất phát khác để so sánh kết quả. Dễ dàng thấy rằng, nếu số đỉnh của đồ thị là n thì vòng lặp thực hiện đúng n − 1 lần. Mỗi lần lặp, các khối Kết nạp và Sửa nhãn đều phải duyệt U, vì thế độ phức tạp của thuật toán Prim cài đặt theo mô hình trên, có cỡ O(n 2 ). Chú ý Cây khung nhỏ nhất được tìm là không duy nhất ngay cả khi dùng Kruskal hay Prim vì có nhiều khả năng chọn cạnh (hay đỉnh) được kết nạp. Khi dùng Kruskal hay Prim, không cần kiểm tra trước tính liên thông của đồ thị (để đảm bảo sự tồn tại của cây khung). Nếu duyệt hết danh sách cạnh mà không kết nạp đủ n−1 cạnh (Kruskal) hay phải kết nạp cạnh có độ đo ∞ (Prim) vào cây khung thì đồ thị đang xét là không liên thông. Không có giả thiết gì về dấu của trọng số, vì thế thuật toán Kruskal hay Prim cũng được dùng để tìm cây khung lớn nhất (bằng cách đổi dấu lại trọng số).
8.3. Phát biểu bài toán Cho một đồ thị (có hướng hoặc vô hướng), có trọng số: G = (V, E, W) trong đó V là tập đỉnh, E là tập cạnh và W là trọng số. Trọng số của đường đi P từ đỉnh s đến đỉnh t, ký hiệu W(P), được định nghĩa là tổng trọng số các cạnh thuộc P: e P W(P) W(e) .Đường đi P được gọi là đường đi ngắn nhất từ đỉnh s đến đỉnh t nếu trọng số của nó là nhỏ nhất. Bài toán đặt ra là từ đỉnh xuất phát s cho trước, hãy tìm tất cả các đường đi ngắn nhất từ đỉnh này đến các đỉnh còn lại. Sau khi kết thúc, thông tin của các đường đi ngắn nhất từ s đều được phản ánh trong các nhãn (đều là cố định) của các đỉnh: độ dài của đường đi ngắn nhất từ s đến t được cho bởi b(t), còn các đỉnh trên đường đi này được xác định bằng cách lần ngược theo thành phần thứ nhất của nhãn: t ← u 1 = a(t) ← u 2 = a(u 1 ) ← ... ← s = a(uk). Các bước của thuật toán được cho bởi đoạn chương trình (mô phỏng Pascal) sau: (Khởi tạo); WHILE (U khác rỗng) DO BEGIN (Sửa nhãn); (Cố định nhãn); END; (ghi nhận các đường ngắn nhất); Để chứng minh tính đúng đắn của thuật toán Dijkstra, bạn đọc có thể tham khảo [2]. Ví dụ. Tìm đường đi ngắn nhất từ đỉnh A đến mọi đỉnh còn lại trên đồ thị có hướng với ma trận trọng số W (chú ý không đối xứng): A B C D E F A 0 1 ∞ ∞ ∞ ∞ B ∞ 0 5 2 ∞ 7 C ∞ ∞ 0 ∞ ∞ 1 D 2 ∞ 1 0 4 ∞ E ∞ ∞ ∞ 3 0 ∞ F ∞ ∞ ∞ ∞ 1 0 Giải. Lập bảng (giống như trong thuật toán Prim) gồm mỗi cột ứng với một đỉnh tạm thời, mỗi dòng ứng với các nhãn của đỉnh tạm thời trong từng bước tính, đỉnh nào được cố định có dấu *, đỉnh bị loại (không tham gia xét tiếp) các dòng sau bỏ trắng: B C D E F A, 1* A, ∞ A, ∞ A, ∞ A, ∞ B, 6 B, 3* A, ∞ B, 8 D, 4* D, 7 B, 8 D, 7 C, 5* F, 6* Kết quả nhận được các đường đi ngắn nhất từ A đến các đỉnh khác là: Từ A đến B: B ← A (độ dài 1) Từ A đến C: C ← D ← B ← A (độ dài 4) Từ A đễn D: D ← B← A (độ dài 3) Từ A đến E: E ← F ← C ← D ← B ← A (độ dài 6) Từ A đến F: F ← C ← D ← B ← A (độ dài 5) Giống như Prim, độ phức tạp của thuật toán Dijkstra cài đặt theo mô hình trên có cỡ O(n 2 ), trong đó n là số đỉnh của đồ thị. Chú ý Bài toán tìm đường đi ngắn nhất theo nghĩa ít cạnh nhất là trường hợp riêng của bài toán đang xét khi đặt trọng số của mỗi cạnh là 1. Nếu chỉ cần tìm một đường đi ngắn nhất từ s đến t thì có thể dừng khi t được cố định mà không cần làm hết bảng. Nếu đường đi ngắn nhất từ s đến t có chứa cạnh độ dài vô cùng thì đường đi này không tồn tại. Thuật toán Dijkstra chỉ đúng khi các trọng số là không âm vì thế không thể dùng nó để tìm đường đi dài nhất. Cho đến nay, chưa có một thuật toán hữu hiệu nào giải quyết bài toán tìm đường đi ngắn nhất trong trường hợp trọng số tổng quát ngoài giải pháp tầm thường là duyệt toàn bộ. Tuy nhiên, hiện nay người ta đã đạt khá nhiều kết quả cho việc tìm hiểu và phát triển các thuật toán hiệu quả giải bài toán này trong một số trường hợp riêng có nhiều ứng dụng. Chẳng hạn trong trường hợp đồ thị có hướng không có chu trình, người ta có thuật toán tương tự như Dijkstra với độ phức tạp cỡ O(n 2 ) giải bài toán tìm đường đi ngắn nhất với trọng số có dấu bất kỳ nghĩa là giải được bài toán tìm đường đi dài nhất. Kết quả này có một ứng dụng quan trọng trong việc giải bài toán điều khiển thực hiện các dự án lớn (PERT − Project Evalutation and Review Technique). Về những vấn đề này, bạn đọc có thể tham khảo trong [2] hay trong một số tài liệu chuyên sâu khác. BÀI TẬP
Cho một mạng truyền tin gồm một số trạm và một số cạnh nối (hai chiều) các trạm này. Với mỗi cạnh nối trạm i với trạm j, người ta cho biết P(i, j) là độ tin cậy khi truyền tin của cạnh đó (P(i, j) được định nghĩa là một số thực nằm giữa 0 và 1 với ý nghĩa càng gần 0 thì độ tin cậy càng kém, càng gần 1 thì độ tin cậy càng cao). Một đường truyền tin từ trạm s đến trạm t là một dãy các cạnh nối kế tiếp nhau bắt đầu từ s và kết thúc tại t. Người ta định nghĩa độ tin cậy của một đường truyền tin là tích các độ tin cậy của các cạnh thuộc đường truyền tin đó. a) Chứng minh rằng bài toán tìm đường truyền tin có độ tin cậy cao nhất từ s đến t được dẫn về bài toán tìm đường đi ngắn nhất từ s đến t. b) Viết các bước của thuật toán Dijkstra giải bài toán đã cho. c) Viết một chương trình minh họa các bước đã nêu trong câu b. |
