Tiểu luận Môn phân tích thiết kế thuật toán: Một số thuật toán cặp ghép trên đồ thị hai phía

A/ MỞ ĐẦU Trong cuộc sống, chúng ta thường gặp nhữmg vấn đề mà trong đó ta cần tìm phương án thực hiện sao cho đạt được mục đích của mình một cách tốt nhất. Chẳng hạn, bài toán tìm lộ trình đi từ một điểm này đến một điểm khác sao cho quãng đường đi là ngắn nhất hoặc lộ phí rẻ nhất... Một trong những bài toán đó là tìm phương án tối ưu trên một mạng lưới. Bài toán luồng cực đại trong mạng là một trong những bài toán tối ưu trên đồ thị có nhiều ứng dụng trong thực tế và trong lý thuyết tổ hợp. Bài toán này đã được hai nhà toán học Mỹ là Ford và Fulkerson tập trung giải quyết và đã đưa ra thuật giải chính xác. Tuy nhiên, đối với những mạng trong đó đồ thị có dạng “hai phía”, thuật toán trên chi phí quá nhiều bộ nhớ mà thực ra không cần thiết. Tiểu luận này nhằm đưa ra thuật toán hữu hiệu của một số bài toán liên quan đến đồ thị hai phía mà trong đó có sự cải tiến để sử dụng một cách tối đa hiệu quả của bộ nhớ. Tiểu luận gồm 4 phần. Phần 1: Giới thiệu một số khái niệm chung. Phần2: Trình bày thuật toán tìm cặp ghép đầy đủ tối ưu. Phần 3: Trình bày thuật toán tìm cặp ghép tối đa. Phần 4: Trình bày hai chương trình ví dụ, đó là chương trình tìm cặp ghép đầy đủ có tổng trọng số đạt max và chương trình tìm cặp ghép tối da. B/ NỘI DUNG I. Một số khái niệm chung Xét hai tập hữu hạn X, Y gồm n phần tử: X = {x1, x2, ..., xn} Y = {y1, y2, ..., xn} -Cặp phần tử (x, y) với x Î X, y Î Y được gọi là một cặp ghép. -Hai cặp ghép (x, y) và (x’, y’) được gọi là rời nhau nếu x ¹ x’ và y ¹ y’. ----Tập M gồm các cặp ghép rời nhau được gọi là một tập cặp ghép. Thông thường bài toán xây dựng các cặp ghép được tiếp cận theo 2 hướng: Hướng thứ nhất: Khi ghép cặp phải thỏa mãn điều kiện nào đấy, khi đó người ta quan tâm đến khả năng ghép cặp tối đa. Hướng thứ hai: lượng hóa việc ghép cặp, khi đó người ta quan tâm đến phương án ghép cặp tối ưu theo các giá trị đã lượng hóa. Vì số tập cặp ghép là hữu hạn, nên có một phương pháp xây dựng tầm thường là thử tất cả các khả năng. Tuy nhiên, số khả năng như vậy là rất lớn (cỡ n!). Vì thế, người ta quan tâm đến việc tìm kiếm những thuật giải hữu hiệu, dễ cài đặt chương trình và có tính khả thi cao. Bài này nhằm giới thiệu một số mô hình ghép cặp như vậy. II. Cặp ghép đầy đủ tối ưu 2.1. Giới thiệu bài toán Một tập cặp ghép, sao cho tất cả các phần tử của X và Y đều được ghép cặp (nghĩa là có đủ n cặp với n là số phần tử của X và Y), được gọi là một tập cặp ghép đầy đủ. Rõ ràng mỗi song ánh p: X ® Y xác định một tập cặp ghép đầy đủ, trong đó mỗi cặp ghép được viết dưới dạng (x, p(x)), x Î X. Từ đó suy ra có tất cả n! cách xây dựng tập cặp ghép đầy đủ khác nhau. Với các tập cặp ghép đầy đủ, một cách tự nhiên, người ta quan tâm đến tập cặp ghép “tốt nhất” theo một nghĩa nào đó đã được lượng hóa. Tập cặp ghép này được gọi là tập cặp ghép đầy đủ tối ưu. Bài toán tìm cặp ghép đầy đủ tối ưu có nhiều mô hình ứng dụng thực tế. Một trong những mô hình này là người ta quan tâm đến việc ghép cặp sao cho có hiệu quả nhất. Để lượng hóa việc ghép mỗi phần tử x Î X với một phần tử y Î Y, người ta đưa vào ma trận trọng số Ci j (i, j = 1, 2, ..., n) với ý nghĩa Ci j mô tả hiệu quả của việc ghép xi với yj. Bài toán được đặt ra là: xây dựng một tập cặp ghép đầy đủ có tổng hiệu quả lớn nhất. Bài toán vừa nêu thường được phát biểu dưới dạng một mô hình thực tế là bài toán phân công dưới đây: Bài toán phân công: Có n người và n công việc. Biết Ci j là số tiền làm ra nếu giao công việc j cho người i thực hiện. Hãy tìm cách phân công mỗi người mỗi việc để tổng số tiền làm ra là lớn nhất. 2.2. Phương pháp tham lam Đây là một phương pháp gần đúng, xuất phát từ việc chọn tối ưu trong từng bước vì thế nó không đảm bảo tính tối ưu toàn cục. Tuy nhiên, nó cho ngay một phương án, gần với phương án tối ưu: Xuất phát từ bảng Ci j đóng vai trò bảng hiện hành. Tập cặp ghép được khởi gán rỗng. Tìm dòng i cột j của bảng hiện hành, thỏa mãn Ci j là giá trị lớn nhất của bảng. Thêm cặp (xi, yj) vào tập cặp ghép. Xóa dòng i, cột j ra khỏi bảng hiện hành và lặp lại bước 2 cho đến khi bảng rỗng. Thí dụ, xét bảng trọng số với n = 4: 2 5 1 6 8 7 6 4 6 9 3 5 5 1 2 7 các cặp ghép được chọn lần lượt là (tương ứng với các ô có khoanh tròn): (x3, y2), (x2, y1), (x4, y4), (x1, y3), có tổng trọng số 25. Trường hợp này, các cặp ghép tìm được chưa phải là các cặp ghép đầy đủ tối ưu (ta quay lại ví dụ này ở dưới). 2.3. Định lý cơ sở Việc xây dựng tập cặp ghép đầy đủ tối ưu dựa vào dấu hiệu nhận biết một tập cặp ghép đầy đủ khi nào là tối ưu. Dĩ nhiên việc thử dấu hiệu này không phải là việc so sánh với tất cả các cặp ghép, mà phải được xây dựng mang tính khả thi. Để làm điều này, người ta xây dựng hàm số F, xác định trên tập các phần tử xi Î X, yj Î Y, mà ta sẽ gọi là nhãn của các phần tử. Nhãn F được gọi là chấp nhận được nếu thỏa mãn bất đẳng thức F(xi)+F(yj) ³ Ci j với mọi xi Î X, yj Î Y. Tập cặp ghép M và nhãn F được gọi là tương thích với nhau nếu thoả mãn đẳng thức F(xi)+F(yj) = Ci j với mọi (xi, yj) Î M. Đặc biệt, tập cặp ghép rỗng được xem như tương thích với mọi nhãn. Định lý. Tập cặp ghép đầy đủ M* là tối ưu khi tồn tại nhãn F chấp nhận được là tương thích với nó. Chứng minh. Giả sử M là một tập cặp ghép đầy đủ nào đó, gọi C(M) là tổng hiệu quả của M: C(M) = Vì mỗi cặp (xi, yj)ÎM đi qua các phần tử của X và Y, mỗi phần tử đúng một lần, và nhãn F thỏa mãn bất đẳng thức F(xi)+F(yj) ³ Ci j nên C(M) = £ Riêng đối với mọi cặp (xi, yj)ÎM*, nhãn F thỏa mãn đẳng thức F(xi)+F(yj) = Ci j nên = = C(M*) từ đó nhận được C(M) £ C(M*) nghĩa là M* là tập cặp ghép đầy đủ tối ưu. Dựa vào định lý vừa chứng minh, người ta có 2 hướng tiếp cận cặp ghép đầy đủ tối ưu: Một là, xuất phát từ một cặp ghép đầy đủ M nào đó, người ta xây dựng một nhãn F tương thích với M. Nếu F là chấp nhận được, thì M là tối ưu. Trái lại, người ta điều chỉnh M cho đến khi F tương thích là chấp nhận được và khi đó M là tối ưu. Hai là, xuất phát từ một nhãn F chấp nhận được và một tập cặp ghép M bất kỳ tương ứng với F (có thể rỗng), người ta tăng dần số cặp ghép của M sao cho vẫn đảm bảo tìm được nhãn F tương thích với M là chấp nhận được. Quá trình tăng sẽ kết thúc khi M đầy đủ và khi đó M là tối ưu. Dưới đây trình bày một thuật toán tìm cặp ghép đầy đủ tối ưu theo hướng thứ hai. 2.4. Thuật toán Kuhn-Munkres Nội dung chủ yếu của phương pháp là xuất phát từ một tập cặp ghép nào đó chưa đầy đủ (có thể là tập rỗng), ta tăng dần số cặp ghép sao cho khi trở thành đầy đủ, các cặp ghép thu được cũng đồng thời thỏa mãn tính tối ưu. Có nhiều hình thức trình bày phương pháp này. Dưới đây là cách trình bày trên ngôn ngữ đồ thị với các thao tác tìm kiếm. Cách này có nhiều ưu điểm: trực giác, dễ phát biểu, dễ chứng minh và đặc biệt, dễ cài đặt chương trình vì việc tìm đường đi trên đồ thị là một thao tác cơ bản và quen thuộc. Giả sử F là một nhãn chấp nhận được và M là một tập cặp ghép tương thích với F. Xem các phần tử của X và Y như những đỉnh của một đồ thị có hướng hai phía (một phía X và một phía Y). Các cạnh của đồ thị này được xác định tuỳ thuộc nội dung của nhãn F và tập cặp ghép M như sau: - Mỗi cặp phần tử xi Î X, yj Î Y thoả mãn đẳng thức F(xi)+F(yj) = Ci j sẽ xác định một cạnh của đồ thị, - Cạnh này có hướng từ X sang Y nếu cặp (xi, yj) không thuộc M (gọi là cạnh thuận) và ngược lại, có hướng từ Y sang X nếu cặp (xi, yj) thuộc M (gọi là cạnh nghịch). Đồ thị xây dựng theo quy tắc vừa nêu được gọi là đồ thị cân bằng tương ứng với F, M và được ký hiệu là G(F, M). Bước 1. Khởi tạo: Xây dựng nhãn F chấp nhận được như sau: F(xi) := Max{Ci j, yj Î Y } xi Î X F(yj) := 0 yj Î Y M là tập cặp ghép rỗng. Chú ý rằng, có thể xuất phát từ bất kỳ nhãn F nào chấp nhận được và bất kỳ một tập cặp ghép M nào tương ứng với F. Bước 2. Tìm đỉnh tự do thuộc X: tìm đỉnh u Î X chưa được ghép cặp. Nếu không còn đỉnh nào của X chưa ghép cặp thì kết thúc: tập cặp ghép M hiện hành là tập cặp ghép đầy đủ tối ưu. Trái lại sang bước kế tiếp. Bước 3. Tìm đường tăng cặp ghép: xuất phát từ u, thực hiện việc tìm kiếm trên đồ thị G(F, M). Kết quả tìm kiếm có hai trường hợp: - Nếu đến được một đỉnh z Î Y chưa ghép cặp thì ghi nhận đường đi từ u đến z (gọi là đường tăng cặp ghép) và chuyển sang bước tăng cặp ghép trên đường đi này. - Nếu không tồn tại một đường đi như vậy thì chuyển sang bước sửa nhãn F. Bước 4. Tăng cặp ghép: Điều chỉnh M như sau: - Giữ nguyên những cặp ghép của M nằm ngoài đường tăng cặp ghép, - Trên đường tăng cặp ghép, thay những cặp ghép của M (cạnh ngược) bằng những cặp ghép trên cạnh thuận (về mặt đồ thị nghĩa là đảo chiều các cạnh trên đường tăng cặp ghép). Sau bước này, số cặp ghép thuộc M được tăng thêm 1 và đỉnh u trở thành đã ghép cặp, ngoài ra, tính tương thích giữa F và M vẫn được bảo toàn. Sau đó quay về bước 2 để lặp lại với đỉnh tự do khác. Bước 5. Sửa nhãn: gọi S là tập các đỉnh thuộc X và T là tập các đỉnh thuộc Y đã được đi đến trong quá trình tìm kiếm ở bước 3. Việc sửa nhãn F được tiến hành như sau: - Tìm lượng sửa nhãn: d := Min{F(xi)+F(yj)-Ci j, xi Î S, yj Ï T} - Gán lại nhãn: F(xi) := F(xi)-d với xi Î S F(yj) := F(yj)+d với yj Î T Sau đó, quay về bước 3 để lặp lại việc tìm đường tăng cặp ghép (với đỉnh xuất phát u cũ và nhãn F mới). Ta thấy rằng, sau khi thay đổi, nhãn F vẫn giữ nguyên tính chấp nhận được và tính tương thích với M. Ngoài ra có thêm ít nhất một cặp (xi, yj) thoả mãn F(xi)+F(yj) = Ci j, vì thế, sau một số lần sửa nhãn, chắc chắn sẽ tăng được cặp ghép. Dưới đây là sơ đồ khối mô tả các bước đã nêu: Khởi tạo M là cặp ghép đầy đủ tối ưu không thấy Tìm đỉnh tự do thuộc X Sửa nhãn thấy không thấy Tìm đường tăng cặp ghép thấy Tăng cặp ghép Nhận xét: khi tăng cặp ghép, các đỉnh đã được ghép cặp rồi không bao giờ trở thành tự do, vì thế việc tìm đỉnh tự do có thể tiến hành tuần tự. Quá trình tìm tập cặp ghép đầy đủ tối ưu có thể mô tả qua đoạn chương trình tựa Pascal sau: ; FOR DO IF THEN BEGIN WHILE NOT DO ; ; END; 2.5. Ví dụ Quay trở lại thí dụ trước. Nhãn F chấp nhận ban đầu là: F 0 0 0 0 6 2 5 1 6 8 8 7 6 4 9 6 9 3 5 7 5 1 2 7 Xuất phát từ tập cặp ghép M rỗng, lần lượt tăng cặp ghép cho các đỉnh tự do x1, x2, x3, ta nhận được M = {(x1, y4), (x2, y1), (x3, y2)} và đồ thị G(F, M) tương ứng: x1 y1 x2 y2 y3 x3 x44 y4 Việc tìm đường tăng cặp ghép đối với đỉnh tự do x4 không thành công và cho ta các tập S = {x1, x4}, T = {y4}. Tiến hành sửa nhãn trên các tập này, ta được d = 1 và nhãn F mới là: F 0 0 0 1 5 2 5 1 6 8 8 7 6 4 9 6 9 3 5 6 5 1 2 7 nhãn F này thêm được cặp x1, y2 thoả mãn F(x1)+F(y2) = C12 và được đồ thị G(F, M): y1 x1 x2 y2 x3 y3 y4 x44 Đường tăng cặp ghép đối với x4 vẫn không tồn tại. Tuy nhiên S và T đã được mở rộng thêm: S = {x1, x3, x4}, T = {y2, y4}, và lượng nhãn được sửa trên các tập này là d = 1: F 0 1 0 2 4 2 5 1 6 8 8 7 6 4 8 6 9 3 5 5 5 1 2 7 Lần này F thêm được cặp x4, y1 thoả mãn F(x4)+F(y1) = C41 và được đồ thị G(F, M): x1 y1 y2 x2 x3 y3 y4 x44 Việc tìm kiếm vẫn chưa kết thúc và cho S = {x1, x2, x3, x4}, T = {y1, y2, y4}. Lượng nhãn được sửa lần này là 2, và ta nhận được: F 2 3 0 4 2 2 5 1 6 6 8 7 6 4 6 6 9 3 5 3 5 1 2 7 cùng với đồ thị G(F, M) (thêm cạnh x2, y3): x1 y1 x2 y2 y3 x3 y4 x44 Việc tìm kiếm trên đồ thị này kết thúc tại y3 cho ta đường tăng cặp ghép: x4 ® y1 ® x2 ® y3 và trên đường này, cặp ghép cũ (x2, y1) được thay bằng 2 cặp ghép mới (x2, y3) và (x4, y1). Kết quả cuối cùng cho tập cặp ghép đầy đủ tối ưu M = {(x1, y4), (x2, y3), (x3, y2), (x4, y1)} với tổng trọng số là 6+6+9+5 = 26. 2.6. Một số dạng của bài toán cặp ghép đầy đủ. a/ Cặp ghép đầy đủ với chi phí nhỏ nhất. Trong một số tình huống, các cặp ghép đầy đủ được tìm sao cho có tổng trọng số là nhỏ nhất. Trường hợp này có thể xem Ci j mô tả chi phí của việc ghép xi với yj và lời giải của bài toán cho ta cách ghép cặp đầy đủ ít tốn kém nhất. Vì thuật toán vừa nêu không phụ thuộc vào dấu của các Ci j nên bài toán tìm min được dẫn về bài toán tìm max với việc đổi dấu tất cả các trọng số Ci j ở đầu vào. Cũng có thể trực tiếp giải bài toán tìm min từ các Ci j đã cho mà không phải đổi dấu chúng bằng cách đối ngẫu lại ý nghĩa của các bất đẳng thức: 1. Nhãn F được gọi là chấp nhận được nếu F(xi)+F(yj) £ Ci j. 2. Nhãn F được xây dựng ban đầu: F(xi) := 0 xi Î X F(yj) := Min{Ci j, xi Î X} yj Î Y 3. Công thức sửa nhãn: d := Min{Ci j-F(xi)-F(yj), xi Î S, yj Ï T} F(xi) := F(xi)+d với xi Î S F(yj) := F(yj)-d với yj Î T b/ Cặp ghép tối ưu trên các tập có số phần tử khác nhau. Trong các phần trên, ta đã giả thiết tập cặp ghép đầy đủ được xây dựng trên các tập X, Y có số phần tử bằng nhau. Tuy nhiên có thể không cần giả thiết này nếu hiểu tập cặp ghép đầy đủ là tập cặp ghép quét hết các phần tử của tập có ít phần tử hơn. Giả thiết X và Y có số phần tử khác nhau. Khi đó bổ sung cho tập ít hơn một số phần tử giả để hai tập trở nên cân bằng và gán trọng số 0 cho tất cả các cặp ghép có phần tử giả, sau đó tiến hành xây dựng tập cặp ghép đầy đủ tối ưu (max hoặc min) trên các tập này. Dễ thấy rằng, lúc đó nghiệm tìm được của bài toán sau cũng là nghiệm của bài toán trước bằng cách bỏ đi các cặp ghép có phần tử giả. II. Cặp ghép tối đa Trong một số bài toán ghép cặp, việc ghép một đối tượng này với một đối tượng khác phải thoả mãn những điều kiện nào đó. Khi đó người ta quan tâm đến bài toán tìm được nhiều nhất các cặp ghép thoả mãn những điều kiện đã nêu. 3.1. Phát biểu bài toán Cho 2 tập hữu hạn X và Y (không nhất thiết có số phần tử bằng nhau) và điều kiện ghép cặp giữa các phần tử của X và Y (những phần tử nào của X ghép được với những phần tử nào của Y). Cần xác định cách ghép cặp tối đa có thể được. Bài toán tìm cặp ghép tối đa thường được gặp trong thực tế dưới dạng những bài toán tìm phương án phân công (hay tìm phương án phục vụ) được nhiều đối tượng nhất. 3.2. Cách giải Bài toán tìm cặp ghép tối đa được dẫn về bài toán tìm cặp ghép đầy đủ tối ưu bằng cách xây dựng bảng trọng số như sau: Ci j = 1 nếu xi ghép cặp được với yj và Ci j = 0 nếu trái lại. Giải bài toán tìm cặp ghép đầy đủ với tổng trọng số lớn nhất và tìm được tập cặp ghép đầy đủ tối ưu M. Khi đó tập cặp ghép tối đa sẽ là tập các cặp (xi, yj) Î M thoả mãn Ci j = 1. Tuy nhiên, nhận xét rằng, trong trường hợp này, ta không cần so sánh trọng số của việc ghép cặp mà chỉ cần quan tâm đến vấn đề có ghép được hay không. Vì thế, có thể tiến hành trực tiếp việc ghép cặp mà không cần thông qua việc xây dựng và điều chỉnh nhãn F. Cách làm này tiết kiệm được các thao tác về nhãn trong mô hình tìm cặp ghép đầy đủ tối ưu. Giả thiết M là một tập cặp ghép nào đó (có thể rỗng). Gọi G(M) là đồ thị có hướng hai phía, gồm tập các đỉnh là X và Y, và tập các cạnh là các cặp xi Î X, yj Î Y thoả mãn điều kiện ghép cặp. Hướng của cạnh được xác định bởi M: đi từ X sang Y nếu cặp đỉnh tương ứng không thuộc M (cạnh thuận) và đi từ Y sang X nếu cặp đỉnh tương ứng thuộc M (cạnh nghịch). Việc ghép cặp được tiến hành như sau: - Xuất phát từ tập cặp ghép M rỗng, - Lần lượt duyệt các đỉnh của X, nếu đỉnh này còn tự do thì tìm đường tăng cặp ghép từ đỉnh này trên đồ thị G(M) tương ứng. Nếu tìm thấy đường tăng thì tiến hành tăng cặp ghép trên đường này như đã trình bày trong mục trước. Nếu tìm không thấy thì bỏ qua đỉnh đang xét để duyệt đỉnh tiếp. - Khi duyệt hết các đỉnh thuộc X, ta nhận được M là tập cặp ghép tối đa. Có thể mô tả quá trình ghép cặp tối đa qua đoạn chương trình tựa Pascal sau: ; FOR DO IF THEN IF THEN ; Chú ý: - Nếu đỉnh được duyệt đã ghép cặp hoặc không có đường tăng cặp ghép từ đỉnh này, thì bỏ qua để xét đỉnh tiếp theo. - Mỗi khi tăng cặp ghép (M thay đổi), đồ thị G(M) sẽ thay đổi hướng của một số cạnh: một số cạnh thuận sẽ trở thành nghịch và ngược lại. Khi kết thúc, G(M) sẽ có số cạnh nghịch tối đa. - Việc duyệt các đỉnh của X để tăng cặp ghép được tiến hành không phụ thuộc vào số phần tử của X có bằng số phần tử của Y hay không, vì thế khi kết thúc, ta cũng nhận được tập cặp ghép tối đa trong trường hợp X và Y có số phần tử khác nhau, mà không cần bổ sung những phần tử giả. 3.3. Ví dụ y1 x1 Cho X = {x1, x2, x3} và Y = {y1, y2, y3, y4}. Điều kiện ghép cặp được cho bởi đồ thị sau (đồ thị G(M) với M rỗng): y2 x2 x3 y3 y4 Lần lượt duyệt các đỉnh của X: x1 y1 - Đỉnh x1: đường tăng cặp ghép x1® y1, M = {(x1, y1)}, đồ thị G(M) x2 y2 y3 x3 y4 y1 x1 - Đỉnh x2: đường tăng cặp ghép x2® y1® x1® y2, M = {(x1, y2), (x2, y1)}, đồ thị G(M) x2 y2 x3 y3 y4 Đỉnh x3: đường tăng cặp ghép x3® y2® x1® y4, M = {(x1, y4), (x2, y1), (x3, y2)}, đồ thị G(M) x1 x2 y1 y2 y3 y4 x3 Các đỉnh của X đã duyệt hết, tập M (tương ứng với đồ thị G(M)) nhận được sau cùng là tập cặp ghép tối đa. Nếu số cặp ghép tối đa bằng số phần tử của X thì mọi phần tử của X đều được ghép cặp với các phần tử của Y theo điều kiện ghép cặp đã cho. Đây cũng là một cách thử hiệu quả cho việc khẳng định hay phủ định sự tồn tại của hệ đại diện phân biệt - một dạng riêng của ghép cặp có nhiều ứng dụng - được trình bày trong mục dưới đây. IV. Các chương trình ví dụ Mục này trình bày các cài đặt trên Turbo Pascal nhằm giải các bài toán: tìm cặp ghép đầy đủ có tổng trọng số đạt max, tìm cặp ghép tối đa và tìm tập cặp ghép đầy đủ sớm nhất theo các mô hình đã nêu. 4.1. Chương trình tìm cặp ghép đầy đủ có tổng trọng số đạt max Chương trình dưới đây tìm tập cặp ghép đầy đủ có tổng trọng số đạt max trên các tập X và Y (có cùng số lượng) theo các trọng số đã cho. Các tập X, Y được đồng nhất với tập các số nguyên {1, 2, ...}. Chương trình dùng biến n để lưu trữ số phần tử của X (Y), và mảng C[i, j] để lưu trữ các trọng số. Các số liệu này được đọc (thủ tục Nhap) từ một file văn bản có cấu trúc: n C11 C12 . . . C1n C21 C22 . . . C2n . . . . . . . . . . . . . . . Cn1 Cn2 . . . Cnn trong đó n là số phần tử của X (Y) và Ci j là trọng số của cặp ghép phần tử i của X với phần tử j của Y. Tập cặp ghép đầy đủ tối ưu được lưu trữ trong mảng px[x], x =1, 2, ..., n, trong đó px[x] ghi nhận phần tử y của Y được ghép với phần tử x của X. Mệnh đề px[u] = 0 có nghĩa đỉnh u thuộc X còn tự do (hàm TuDo). Mảng py[y], y = 1, 2, ..., n cũng để lưu trữ tập cặp ghép nhưng theo chiều ngược lại: py[y] ghi nhận phần tử x của X được ghép với phần tử y của Y. Về mặt lôgic, mảng này có vẻ thừa nhưng nó làm đơn giản và tiết kiệm được một số thao tác tìm kiếm. Ban đầu px và py được khởi gán bằng 0 với mọi thành phần (thủ tục KhoiTao). Chương trình đưa ra màn hình tập cặp ghép đầy đủ tối ưu tìm được và tổng trọng số tương ứng (thủ tục InKq). Một số biến (toàn thể) khác dùng để lưu trữ các thông tin trung gian trong quá trình tìm kiếm. Mảng F ghi nhận nhãn, nó được xác định ban đầu nhờ thủ tục KhoiTao và được điều chỉnh nhờ thủ tục SuaNhan. Mảng q ghi nhận các đỉnh trong quá trình tìm đường tăng cặp ghép. Các biến u và z ghi nhận các đỉnh đầu và cuối của đường tăng cặp ghép. Việc tăng cặp ghép trên đường này được tiến hành nhờ thủ tục TangCapGhep. Quá trình tìm kiếm được thực hiện nhờ hàm TimThayDuongTangCapGhep, trong đó việc tìm kiếm được thiết kế theo chiều rộng. Biến (địa phương) queue dùng để lưu trữ hàng đợi trong quá trình tìm. Các lời giải thích khác được viết trong văn bản chương trình. {tim cap ghep day du toi uu dat max} const max = 150; {kich thuoc toi da} type trongso = array[1..max, 1..max] of integer; arr1 = array[1..max] of integer; arr2 = array[1..2*max] of integer; var C: trongso; n, u, z: integer; {u: dinh dau, z: dinh cuoi} px, py: arr1; {mo ta cap ghep: px: X --> Y py: Y --> X} F, q: arr2; {F: mo ta nhan F[x]: x thuoc X: 1..n, F[y]: y thuoc Y: n+1..n+n q: danh dau duong di} procedure Nhap; var fvar: text; fname: string; i, j : integer; begin write('Doc du lieu tu file: '); readln(fname); assign(fvar, fname); reset(fvar); readln(fvar, n); for i:=1 to n do for j:=1 to n do read(fvar, C[i, j]); close(fvar); end; procedure KhoiTao; var x, y, xx: integer; begin {khoi tao F: F(x) = max(C[x, y], y thuoc Y), voi moi x thuoc X F(y) = 0 voi moi y thuoc Y} fillchar(F, sizeof(F), 0); for x := 1 to n do begin xx := C[x, 1]; for y := 2 to n do if xx < C[x, y] then xx := C[x, y]; F[x] := xx; end; {khoi tao cap ghep rong} fillchar(px, sizeof(px), 0); fillchar(py, sizeof(py), 0); end; function TuDo: boolean; {tra lai TRUE neu dinh u la tu do} begin TuDo := px[u] = 0; end; function TimThayDuongTangCapGhep: boolean; {tra lai TRUE neu tim thay duong tang cap ghep tu u va gui dinh cuoi cua duong di nay vao z} var dau, cuoi, v, w: integer; queue: arr2; begin {xuat phat tu dinh tu do u thuoc X} fillchar(q, sizeof(q), 0); dau := 1; cuoi := 1; queue[1] := u; q[u] := u; while cuoi-dau+1 > 0 do begin v := queue[dau]; inc(dau); if v < n+1 then {thuoc X} begin for w := n+1 to n+n do if (F[v]+F[w] = C[v, w-n]) and (q[w] = 0) then begin inc(cuoi); queue[cuoi] := w; q[w] := v; end; end else {thuoc Y} if py[v-n] = 0 then {v la dinh tu do thuoc Y} begin TimThayDuongTangCapGhep := true; z := v; exit; end else begin w := py[v-n]; inc(cuoi); queue[cuoi] := w; q[w] := v; end; end; TimThayDuongTangCapGhep := false; end; procedure TangCapGhep; var x, y: integer; thuocY: boolean; begin {dieu chinh cap ghep tren duong tang cap ghep} y := z; thuocY := true; while y u do begin x := q[y]; if thuocY then begin px[x] := y-n; py[y-n] := x; end; y := x; thuocY := not thuocY; end; end; procedure SuaNhan; var x, y, d, h: integer; begin {tim luong sua nhan} d := maxint; for x := 1 to n do if q[x] > 0 then for y := n+1 to n+n do if q[y] = 0 then begin h := F[x]+F[y]-C[x, y-n]; if h < d then d := h; end; {sua nhan} for x := 1 to n do if q[x] > 0 then F[x] := F[x]-d; for y := n+1 to n+n do if q[y] > 0 then F[y] := F[y]+d; end; procedure InKq; var x, t: integer; begin write('Cap ghep toi uu: '); t := 0; for x := 1 to n do begin t := t+C[x, px[x]]; write(x, '-', px[x], ' '); end; writeln('Tong trong so: ', t); readln; end; BEGIN Nhap; KhoiTao; for u := 1 to n do if TuDo then begin while not TimThayDuongTangCapGhep do SuaNhan; TangCapGhep; end; InKq; END. 4.2. Chương trình tìm cặp ghép tối đa Chương trình dưới đây tìm tập cặp ghép tối đa trên các tập X và Y (không cùng số lượng) theo các trọng số đã cho. Các tập X, Y được đồng nhất với các tập các số nguyên {1, 2, ...}. Chương trình dùng các biến m và n để lưu trữ số phần tử của X và Y. Điều kiện ghép cặp được lưu trữ trong mảng lôgic C[i, j]. Các số liệu vào được đọc từ một file văn bản có cấu trúc: m n C11 C12 . . . C1n C21 C22 . . . C2n . . . . . . . . . . . . . . . Cm1 Cm2 . . . Cmn trong đó m là số phần tử của X, n là số phần tử của Y, Ci j là các giá trị nhị phân, bằng 1 nếu i (thuộc X) ghép được với j (thuộc Y) và bằng 0 nếu trái lại. Thủ tục Nhap biến đổi các giá trị nhị phân Ci j thành các giá trị lôgic C[i, j] tương ứng. Việc tổ chức còn lại giống như trong cài đặt trước, ngoại trừ loại bỏ các thao tác trên nhãn. Các giải thích chi tiết được viết trong văn bản chương trình. {tim cap ghep toi da} const max = 150; {kich thuoc toi da} type dieukien = array[1..max, 1..max] of boolean; arr1 = array[1..max] of integer; arr2 = array[1..2*max] of integer; var C: dieukien; {C[i, j] = true i ghep duoc j} m, n, u, z: integer; {m: so phan tu cua X, n: so phan tu cua Y u: dinh dau, z: dinh cuoi} px, py: arr1; {mo ta cap ghep: px: X --> Y py: Y --> X} q: arr2; {danh dau duong tang cap ghep} procedure Nhap; var fvar: text; fname: string; i, j, k: integer; begin write('Doc du lieu tu file: '); readln(fname); assign(fvar, fname); reset(fvar); readln(fvar, m, n); for i := 1 to m do for j := 1 to n do begin read(fvar, k); C[i, j] := k = 1; end; close(fvar); end; procedure KhoiTao; begin {khoi tao cap ghep rong} fillchar(px, sizeof(px), 0); fillchar(py, sizeof(py), 0); end; function TuDo: boolean; {tra lai TRUE neu dinh u la tu do} begin TuDo := px[u] = 0; end; function TimThayDuongTangCapGhep: boolean; {tra lai TRUE neu tim thay duong tang cap ghep tu u va gui dinh cuoi cua duong di nay vao z} var dau, cuoi, v, w: integer; queue: arr2; begin {xuat phat tu dinh tu do u thuoc X} fillchar(q, sizeof(q), 0); dau := 1; cuoi := 1; queue[1] := u; q[u] := u; while cuoi-dau+1 > 0 do begin v := queue[dau]; inc(dau); if v < m+1 then {thuoc X} begin for w := m+1 to m+n do if C[v, w-m] and (q[w] = 0) then begin inc(cuoi); queue[cuoi] := w; q[w] := v; end; end else {thuoc Y} if py[v-m] = 0 then {v la dinh tu do thuoc Y} begin TimThayDuongTangCapGhep := true; z := v; exit; end else begin w := py[v-m]; inc(cuoi); queue[cuoi] := w; q[w] := v; end; end; TimThayDuongTangCapGhep := false; end; procedure TangCapGhep; var x, y: integer; thuocY: boolean; begin {dieu chinh cap ghep tren duong tang cap ghep} y := z; thuocY := true; while y u do begin x := q[y]; if thuocY then begin px[x] := y-m; py[y-m] := x; end; y := x; thuocY := not thuocY; end; end; procedure InKq; var x, t: integer; begin write('Cap ghep toi da: '); t := 0; for x := 1 to m do if px[x] > 0 then begin inc(t); write(x, '-', px[x], ' '); end; writeln('So cap ghep: ', t); readln; end; BEGIN Nhap; KhoiTao; for u := 1 to m do if TuDo then if TimThayDuongTangCapGhep then TangCapGhep; InKq; END. KẾT LUẬN Bài toán luồng cực đại trong mạng là một trong số những bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp. Để tìm luồng cực đại trong mạng, thuật toán Ford-Fulkerson đã cho ta một phương pháp chung. Bất cứ bài toán nào có dạng tìm đường đi trong mạng đều có thể áp dụng được thuật toán này. Tuy nhiên trong một số bài toán đặc biệt, việc máy móc áp dụng thuật toán này đã dẫn đến những tình huống lãng phí bộ nhớ cũng như thời gian thực hiện chương trình. Tiểu luận đã phân tích để đưa ra hai thuật toán cho hai dạng bài toán ghép cặp trên đồ thị hai phía, một trường hợp đặc biệt của bài toán luồng cực đại trong mạng. Tiểu luận cũng giới thiệu hai chương trình minh họa cho hai thuật toán cơ bản này. TÀI LIỆU THAM KHẢO 1-Nguyễn Tô Thành-Nguyễn Đức Nghĩa-Toán rời rạc-NXBGD-1997 2-Nguyễn Thị Thanh Hương-Bài toán luồng cực đại và các bài tập kinh điển-Khóa luận tốt nghiệp-2003 MỤC LỤC