TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH
tải về 2.51 Mb.
|
- Điều hướng trang này:
- 3.1 Chị Hằng
- Ý nghĩa
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: AB 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ác bà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ó.
Thuật toán Giả 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ác gó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ần tử 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ạ 11 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ết em 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, ..., i1. 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:
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:
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ói trê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ậy sẽ 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 …tk1 tk vớ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 tk, 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 tk1 để nhận quà mới j em tk1 trao quà qk1 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) = f(t1) = q2; f(t2) = q3; ...; f(tk) = j và hoàn thành việc chia quà cho em i trên cơ sở thương lượng các em trong dãy trên nhừơng quà cho nhau. Tình huống 2: Không gặp tình huống 1, nghĩa là, với mọi em trong dãy t1, t2,…, tk mọi món quà các em yêu thích đều đã được chia cho em nào đó. Nói cách khác, chiến lược nhường quà cho nhau (để nhận quà khác) không mang lại kết quả. Ta kết luận: "không thể chia quà cho em i". Do không thể chia được quà cho em i ta tiếp tục chia quà cho các em khác. Tổ chức dữ liệu Mảng nguyên t[1..n], t[j] = i: em j sẽ nhường quà của mình cho bạn i; Mảng nguyên a[1..n], a[i] = j: em i đã được chia quà j; Mảng nguyên b[1..m], b[j] = i: quà j đang có trong tay em i. Để ý rằng a[b[j]] = j và b[a[i]] = i; Mảng nguyên st[1..n]: danh sách các em tạm trả lại quà và đang cần được ưu tiên nhận quà mới. Biến nguyên p: trỏ tới ngăn trên cùng của stack st. Mảng nguyên 2 chiều nhị phân c[1..n,1..m], c[i][j] = 1 khi và chỉ khi em i thích quà j; Hàm Xep(i): chia quà cho bạn i; Xep(i) = 1 nếu tìm được một cách chia, ngược lại, khi không tìm được Xep = 0. Hàm Par thực hiện ghép cặp cho các em theo thứ tự từ 1 đến n. (* Autum.pas *) uses crt; const fn = 'autum.inp'; gn = 'autum.out'; bl = #32; nl = #13#10; mn = 201; type mi1 = array[0..mn] of integer; mb2 = array[0..mn,0..mn] of byte; var n, m: integer; { n - so nguoi; m - so qua } a, b: mi1; t: mi1; st: mi1; p: integer; c: mb2; f,g: text; {f: input file; g: otput file } procedure Doc; var i,j,k,q: integer; begin assign(f,fn); reset(f); read(f,n,m); fillchar(c,sizeof(c),0); for i := 1 to n do begin read(f,k); for j := 1 to k do begin read(f,q); c[i][q] := 1 end; end; close(f); end; procedure Print; var i,j: integer; begin writeln(nl,n,bl,m); for i := 1 to n do begin for j := 1 to m do write(c[i,j]); writeln; end; end; procedure Update(i,j: integer); var q: integer; begin repeat q := a[i]; { i bỏ qùa q } a[i] := j; b[j] := i; { để nhận quà j } j := q; i := t[i]; { chuyển qua người trước } until q = 0; end; function Xep(i: integer): integer; var j: integer; begin Xep := 1; p := 0; inc(p); st[p] := i; { nạp st } fillchar(t, sizeof(t),0); t[i] := i; while p > 0 do begin i := st[p]; dec(p); { Lấy ngọn st } for j := 1 to m do if c[i,j] = 1 then { i thích qùa j } begin if b[j] = 0 then { qùa j chưa chia } begin Update(i,j); exit end else if t[b[j]] = 0 { b[j] chưa có trong st } then begin inc(p); st[p] := b[j]; t[b[j]] := i end; end; end; Xep := 0; end; procedure Ghi(v: integer); var i: integer; begin assign(g,gn); rewrite(g); writeln(g,v); for i := 1 to n do if a[i] > 0 then writeln(g,i,bl,a[i]); close(g); end; procedure Par; { Ghep cap } var i,v: integer; begin Doc; Print; v := 0; fillchar(a, sizeof(a),0); b := a; for i := 1 to n do v := v + Xep(i); Ghi(v); end; BEGIN Par; write(nl,' Fini '); readln; END. // DevC++: Autum.cpp #include #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "autum.inp"; const char * gn = "autum.out"; const int mn = 201; // so nguoi va so qua toi da int a[mn]; // a[i] = j: em i nhan qua j int b[mn]; // b[j] = i: qua j trong tay em i int t[mn]; // t[j] = i : em j nhuong qua cho ban i int c[mn][mn]; // c[i][j] = 1: i thich qua j int n; // so em nho int m; // so qua int st[mn]; // stack int p; // con tro stack // P R O T O T Y P E S int main(); void Doc(); void Print(); int Par(); int Xep(int); void Update(int, int); void PrintArray(int [], int , int ); void Ghi(int); // I M P L E M E N T A T I O N int main() { Doc(); Print(); int v = Par(); Ghi(v); cout << endl << "Xep duoc " << v << " em."; PrintArray(a,1,n); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Ghi(int v) { ofstream g(gn); g << v << endl; for (int i = 1; i <= n; ++i) if (a[i] > 0) g << i << " " << a[i] << endl; g.close(); } void PrintArray(int a[], int d, int c) { int i; cout << endl; for (i = d; i <= c; ++i) cout << a[i] << " "; } void Update(int i, int j){ int c; do { c = a[i]; // i bo qua c xuong a[i] = j; b[j] = i; // i nhan qua moi j i = t[i]; j = c; // chuyen qua nguoi khac } while (c > 0); } int Xep(int i) { // tim qua cho em i memset(t, 0, sizeof(t)); int j; p = 0; st[++p] = i; t[i] = i; while(p > 0) { i = st[p--]; // lay ngon stack for (j = 1; j <= m; ++j) { // duyet cac mon qua if (c[i][j] > 0) { // i thich qua j if (b[j] == 0) { // qua j chua chia Update(i,j); return 1; } if (t[b[j]] == 0) { //b[j] chua co trong danh sach st[++p] = b[j]; t[b[j]] = i; // nap } } } } return 0; // Khong chon duoc qua cho em i } int Par(){ // Cap ghep int v = 0, i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for (i = 1; i <= n; ++i) v += Xep(i); return v; } void Print() { // Hien thi ma tran c cout << endl << n << " " << m << endl; int i,j; for (i = 1; i <= n; ++i){ for (j = 1; j <= m; ++j) cout << c[i][j] << " "; cout << endl; } } void Doc(){ memset(c,sizeof(c),0); ifstream f(fn); f >> n >> m; int i,j,k,r; for (i = 1; i <= n; ++i) { f >> k; for (r = 1; r <= k; ++r) { f >> j ; c[i][j] = 1; } } f.close(); } Nhận xét Ta có thể dùng ngăn xếp hay hàng đợi trong bài này kết quả không phụ thuộc vào trật tự duyệt. Каталог: tailieu tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1 tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam tải về 2.51 Mb. Chia sẻ với bạn bè của bạn:
|