Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 3 - Chương 3

Cặp ghépLớp các bài toán xác định một tương ứng giữa hai tập phần tử A và B cho trước, thí dụ như tập A gồm các em thiếu nhi và tập B gồm các món quà như trong bài toán Chị Hằng dưới đây được gọi là các bài toán cặp ghép và thường được kí hiệu là f:
Nội dung trích xuất từ tài liệu:
Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 3 - Chương 3 Chương 3 Cặp ghépLớp các bài toán xác định một tương ứng giữa hai tập phần tử A và B cho trước, thí dụ như tập A gồm cácem thiếu nhi và tập B gồm các món quà như trong bài toán Chị Hằng dưới đây được gọi là các bài toán cặpghép và thường được kí hiệu là f: AB với ý nghĩa là cần xác định một ánh xạ, tức là một phép đặt tươngứng mỗi phần tử i của tập A với duy nhất một phần tử j của tập B, f(i) = j. Một trong các thuật toán giải cácbài toán này có tên là thuật toán Ghép cặp. Thuật toán đòi hỏi thời gian tính toán là n.m phép so sánh trongđó n là số phần tử (lực lượng) của tập A, m là số phần tử của tập B, n = ||A||, m = ||B||.Chương này trình bày thuật toán ghép cặp và các biến thể của nó.3.1 Chị HằngNhân dịp Tết Trung Thu Chị Hằng rời Cung Trăng mang m món quà khác nhau mã số 1..m đến vui TrungThu với n em nhỏ mã số 1..n tại một làng quê. Trước khi Chị Hằng phát quà, mỗi em nhỏ đã viết ra giấynhững món quà mà em đó mơ ước. Yêu cầu: giúp Chị Hằng chia cho mỗi em đúng 1 món quà mà em đóyêu thích.Dữ liệu vào: file văn bản autum.inp Dòng đầu tiên: hai số n m Dòng thứ i trong số n dòng tiếp theo: k b 1 b2 ... bk - k là số lượng quà em i yêu thích; b1 b2 ... bk là mã số các món quà em i yêu thích.Dữ liệu ra: file văn bản autum.out Dòng đầu tiên: v – số em nhỏ đã được nhận quà. v dòng tiếp theo: mỗi dòng 2 số i b cho biết em i được nhận món quà b.Thí dụ,autum.inp autum.out Ý nghĩa55 5 Có 5 em và 5 món quà. Em 1 thích 2 món quà: 1 và 5; em 2 thích 2215 11 món quà: 2 và 4; em 3 thích 2 món quà: 1 và 2; em 4 thích 3 món quà:224 24 1, 4 và 5; em 5 thích 2 món quà: 1 và 3. Một phương án xếp em nhỏ quà như sau: 11; 24; 32; 45;212 32 53.3145 45213 53Thuật toánGiả sử các phần tử của tập nguồn A (các em nhỏ) được mã số từ 1 đến n và các phần tử của tập đích B (cácgói quà) được mã số từ 1 đến m. Sau khi đọc dữ liệu và thiết lập được ma trận 0/1 hai chiều c với các phầntử c[i,j] = 1 cho biết em i thích món quà j và c[i,j] = 0 cho biết em i không thích quà j. Nhiệm vụ đặt ra làthiết lập một ánh xạ 11 f từ tập nguồn vào tập đich, f: A  B. Ta sử dụng phương pháp chỉnh dần các cặpđã ghép để tăng thêm số cặp ghép như sau.Ta cũng sử dụng hai mảng một chiều A và B để ghi nhận tiến trình chia và nhận quà với ý nghĩa như sau:A[i] = j cho biết em i đã được nhận quà j; B[j] = i cho biết quà j đã được chia cho em i; A[i] = 0 cho biếtem i chưa được chia quà và B[j] = 0 cho biết quà j trong túi quà B còn rỗi (chưa chia cho em nào).Giả sử ta đã chọn được quà cho các em 1, 2, ..., i1. Ta cần xác định f(i) = j, tức chọn món quà j cho em i. Nếu ta tìm ngay được món quà j  B thỏa đồng thời các điều kiện sau:  B[j] = 0: j là món quà còn trong túi quà B, tức là quà j chưa được chia,  c[i,j] = 1, tức là em i thích quà j thì ta đặt f(i) = j và việc chia quà cho em i đã xong. Trường hợp ngược lại, nếu với mọi quà j thỏa c[i,j] = 1 (em i thích quà j) đều đã được chia cho một em t nào đó (B[j] = t ≠ 0) thì ta phải tiến hành thủ tục thương lượng với toàn bộ các em đang giữ quà mà bạn i thích như sau:  Tạm đề nghị các em dang giữ quà mà bạn i thích, đặt quà đó vào một túi riêng bên ngoài túi có đề chữ i với ý nghĩa sẽ trao 1 món quà trong túi này cho bạn i;  Đưa những em vừa trả lại quà vào một danh sách st gồm các em cần được ưu tiên tìm quà ngay.Như vậy, em i sẽ có quà nếu như ta tiếp tục tìm được quà cho một trong số các em trong danh sách st nóitrên. Với mỗi em trong danh sách st ta lại thực hiện các thủ tục như đã làm với em i nói trên.Ta cần đánh dấu các em trong danh sách để dảm bảo rằng không em nào xuất hiện quá hai lần và như vậysẽ tránh được vòng lặp vô hạn.Sau một số bước lặp ta sẽ thu được dãy t1  t2 …tk1  tkvới ý nghĩa là em t1 sẽ nhận quà từ em t2, em t2 sẽ nhận quà từ em t3, … em tk-1 sẽ nhận quà từ em tk. và sẽ gặp một trong hai tình huống loại trừ nhau sau đây:Tình huống 1: Ta tìm được một món quà cho em t k, nghĩa là với em tk ta tìm được một món quà j còn rỗi(B[j] = 0) và tk yêu thích (c[tk,j] = 1). Ta gọi thủ tục Update(tk, j) thực hiện dãy các thao tác chuyển quàliên hoàn từ em này cho em kia như sau: em tk trao quà qk của mình cho bạn tk1 để nhận quà mới j em tk1 trao quà qk1 của mình cho bạn tk-2 để nhận quà mới qk từ tay bạn tk; … em t2 trao quà q2 của mình cho bạn t1 để nhận quà mới q3 từ tay bạn t3; em t1 nhận quà j. Đây chính là em i mà ta cần chia quà.Ta thu được: f(i) = ...