Luồng cực đại trong mạng và một số bài toán ứng dụng

Chia sẻ: Hoang Viet Anh | Ngày: | Loại File: DOC | Số trang:25

Thêm vào BST

Báo xấu

700
lượt xem 89
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ị 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. Bài toán được đề xuất vào đầu những năm 1950, và gắn liền với tên tuổi của hai nhà toán học Mỹ là Ford và Fulkerson. Trong nội dung bài viết này chúng tôi muốn trình bày thuật toán của hai ông và cài đặt nó cũng như đưa ra một số bài toán ứng dụng của thuật toán. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luồng cực đại trong mạng và một số bài toán ứng dụng

Luồng cực đại trong mạng và một số bài toán ứng dụng Nguyễn Văn Trường 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ị 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. Bài toán được đề xuất vào đầu những năm 1950, và gắn liền vơi tên tuổi của hai nhà toán học Mỹ là Ford và Fulkerson. Trong nội dung bài viết này chúng tôi muốn trình bày thuật toán của hai ông và cài đặt nó cũng như đưa ra một số bài toán ứng dụng của thuật toán. 1. Một số khái niệm Định nghĩa 1. Mạng là một đồ thị có hướng G = (V,E), trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát và có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung e = (v,w) thuộc E được gán với một số không âm c(e) = c(v,w) gọi là khả năng thông qua của cung e (nếu không có cung (v,w) thì khả năng thông qua c(v,w) được gán bằng 0). Định nghĩa 2. Một luồng f trong mạng G = (V,E) là ánh xạ f : E → R+ gán cho mỗi cung e = (v,w) thuộc E một số thực không âm f(e) = f(v,w), gọi là luồng trên cung e, thoả mãn các điều kiện sau: 1) Luồng trên mỗi cung e thuộc E không vượt quá khả năng thông qua của nó: 0 ≤ f(e) ≤ c(e). 2) Điều kiện cân bằng luồng trên mỗi đỉnh của mạng là tổng luồng trên mỗi cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v, nếu v ≠ s và v ≠ t thì: Divf(v) = Σf(w,v) - Σ f(v,w) = 0 w thuộc G - (v) w thuộc G + (v) trong đó G - (v) là tập các đỉnh của mạng mà từ đó có cung đến v, và G + (v) là tập các đỉnh của mạng mà từ v có cung đến nó. G - (v) = { w thuộc V : (w,v) thuộc E}; G + (v) = { w thuộc V : (v,w) thuộc E}; 3) Giá trị của luồng f là số: val( f ) = Σ f(s,w) = Σ f(w,t) w thuộc G + (v) w thuộc G - (v) Bài toán luồng cực đại trong mạng: Cho mạng G = (V,E). Hãy tìm luồng f*trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng như vậy sẽ được gọi là luồng cực đại trong mạng. Bài toán như vậy có thể xuất hiện rất nhiều trong ứng dụng thực tế mà chúng ta sẽ nghiên cứu trong phần 3 tiếp theo dưới đây. Định nghĩa 3. Lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X* = VX, trong đó s thuộc X và t thuộc X*. Khả năng thông qua của lát cắt (X,X*) là số: c(X,X*) = Σ c(v,w). v thuộc X w thuộc X* Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất. Bổ đề 1. Giá trị của mọi luồng f trong mạng luôn nhỏ hơn hoặc bằng khả năng thông qua của lát cắt bất kỳ của nó: val(f) ≤ c(X,X*).
(do phạm vi có hạn của bài báo nên các phần chứng minh xin xem thêm trong [1] ) Hệ quả 1. Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng. Ford và Fulkerson đã chứng minh được rằng: giá trị luồng cực đại trong mạng đúng bằng khả năng thông qua của lát cắt hẹp nhất. Ta đưa thêm vào một số khái niệm sau: Giả sử f là một luồng trong mạng G = (V,E). Từ mạng G = (V,E) ta xây dựng đồ thị có trọng số trên mạng Gf = (V,Ef), với tập các cung Ef và trọng số trên các cung được xác định như sau: 1) Nếu e = (v,w) thuộc E với f(v,w) = 0, thì (v,w) thuộc Ef với trọng số c(v,w). 2) Nếu e = (v,w) thuộc E với f(v,w) = c(v,w), thì (v,w) thuộc Ef với trọng số f(v,w). 3) Nếu e = (v,w) thuộc E với 0 < f(v,w) < c(v,w) thì (v,w) thuộc Ef với trọng số c(v,w) - f(v,w) và (w,v) thuộc Ef với trọng số f(v,w). Các cung của Gf đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại được gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng. Ví dụ: các số viết cạnh các cung của G ở hình vẽ dưới theo thứ tự là khả năng thông qua và luồng f trên cung. Giả sử P = (s = v1,v2,v3,.. ,vk = t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P. Xây dựng luồng f′ trên mạng G theo qu y tắc sau: f′(u,v) nhận một trong các giá trị sau: 1) f(u,v) + d nếu (u,v) thuộc P là cung thuận. 2) f(u,v) - d nếu (u,v) thuộc P là cung nghịch. 3) f(u,v) nếu (u,v) không thuộc P. Dễ dàng kiểm tra được rằng f′ xây dựng như trên là một luồng trên mạng và val(f′) = val(f) + d. Thủ tục biến đổi vừa nêu gọi là tăng luồng dọc theo đường P. Địng nghĩa 4. Đường tăng luồng f là mọi đường đi từ s đến t trên đồ thị tăng luồng G(f). Định lý 1. Các mệnh đề sau là tương đương: 1) f là luồng cực đại trong mạng 2) không tìm được đường tăng luồng f 3) val(f′) = c(X,X*) với một lát cắt (X,X*) nào đó. 2.Thuật toán tìm luồng cực đại trong mạng Định lý 1 là cơ sở để xây dựng thuật toán lặp sau đây để tìm luồng cực đại trong mạng: Bắt đầu từ luồng với tất cả các cung bằng 0 (luồng đó được gọi là luồng không), và thực hiện hai thao tác: a) Tìm đường tăng P đối với luồng hiện có; b) Tăng luồng dọc theo đường P, lặp đi lặp lại cho đến khi thu được luồng mà đối với nó không còn đường tăng (bước lặp trên được gọi là bước lặp tăng luồng Ford- Fulkerson). Sơ đồ thuật toán Ford-Fulkerson được mô tả trong thủ tục sau đây: Procedure Max_Flow; (*Thuật toán Ford-Fulkerson *) Begin (* khởi tạo bắt đầu từ luồng với giá trị 0 *) for u thuộc V do for v thuộc V do f(u,v):=0; Stop:= false;
While not Stop do If {tìm được đường tăng luông P}then {tăng luồng dọc theo P} else stop:=true; End; Để tìm được đường tăng luồng trong Gf có thể sử dụng thuật toán tìm kiếm theo chiều rộng hay tìm kiếm theo chiều sâu bắt đầu từ đỉnh s, nhưng sử dụng thuật toán gán nhãn của Ford-Fulkerson sẽ tối ưu hơn. Thuật toán bắt đầu từ luồng chấp nhận nào đó trong mạng (có thể bắt đầu từ luồng không), sau đó tăng luồng bằng cách tìm các đường tăng luồng bằng phương pháp gán nhãn cho các đỉnh. Mỗi đỉnh trong quá trình gán nhãn sẽ ở một trong ba trạng thái: chưa có nhãn, có nhãn chưa xét và có nhãn đã xét. Nhãn của đỉnh v có hai phần và ở một trong hai dạng sau:[+p(v), e (v)] hoặc[-p(v), e (v)]. Phần thứ nhất +p(v) (-p(v)) chỉ ra là cần tăng (giảm) luồng theo cung (p(v),v) (cung (v,p(v))), còn phần thứ hai e (v) chỉ ra lượng lớn nhất có thể tăng hoặc giảm luồng theo cung này. Thuật toán được thực hiện bắt đầu với duy nhất đỉnh s được khởi tạo nhãn và nhãn của nó là chưa xét, còn tất cả các đỉnh còn lại đều chưa có nhãn. Từ s ta gán nhãn tất cả các đỉnh kề với nó và nhãn của đỉnh s trở thành đã xét. Tiếp theo, từ mỗi đỉnh v có nhãn chưa xét ta lại gán nhãn cho tất cả đỉnh chưa có nhãn kề với nó và nhãn của đỉnh v trở thành đã xét. Quá trình cứ lặp lại cho tới khi: hoặc là đỉnh t trở thành có nhãn hoặc là nhãn của tất cả các đỉnh có nhãn đều trở thành đã xét nhưng đỉnh t vẫn không có nhãn. Trong trường hợp thứ nhất ta tìm được đường tăng luồng, còn trường hợp thứ hai đối với luồng đang xét không tồn tại đường tăng luồng (tức là luồng đã là cực đại). Mỗi khi tìm được đường tăng luồng, ta lại tăng luồng theo đường tìm được, sau đó xoá tất cả các nhãn đối với luồng mới thu được rồi lại sử dụng phép gán nhãn các đỉnh để tìm đường tăng luồng. Thuật toán kết thúc khi gặp trường hợp thứ hai ở trên. Các thủ tục Tìm đường tăng luồng và Tăng luồng được mô tả như sau: Procedure Find_Path; (* Thủ tục gán nhãn tìm đường tăng luồng p[v], e [v] là các nhãn của đỉnh v; VT là danh sách các đỉnh có nhãn nhưng chưa xét; c[u,v] là khả năng thông qua của cung (u,v),u, v thuộc V; f[u,v] là luồng trên cung u,v (u,v thuộc V) *) Begin p[s]:=s; e [s]:=+ ∞ ; VT :={s}; PathFound:=true; While VT ≠ Φ do Begin u ← VT ;(*lấy u từ VT*) for v thuộc VVT do Begin if (c[u,v] > 0) and (f[u,v] < c[u,v]) then Begin p[v]:=u; e [v]:=min{ e [u],c[u,v]-f[u,v]};
VT:=VT hợp {v};(*nạp v vào danh sách đỉnh có nhãn*) If v=t then exit; End; If (c[u,v] > 0) and (f[u,v] > 0) then Begin p[v]:= - u;(* đánh dấu cung nghịch *) e [v]:=min{ e [u],f[v,u]}; VT:=VT hợp {v};(*nạp v vào danh sách đỉnh có nhãn*) If v=t then exit; End; End; PathFound:=false; End; Procedure Inc_Flow; (*tăng luồng theo đường tăng *) Begin v:=p[t];u:=t;tang:= e [t]; While u ≠ s do Begin if v > 0 then f[u,v]:=f[u,v] + tang else begin v:= - v; f[u,v]:=f[u,v] - tang; end; u:=v;v:=p[u]; End; End; Thuật toán Ford-Fulkerson được thực hiện nhờ thủ tục: Procedure Max_Flow; (* thụât toán Ford-Fulkerson*) Begin (*khởi tạo bắt đầu từ luồng với giá trị 0 *) for u thuộc V do for v thuộc V do f[u,v]:=0; stop:=false; while not stop do Begin Find_Path; If PathFound then Inc_Flow Else Stop:=true; End; {luồng cực đại trong mạng là f[u,v],u,v thuộc V} {lát cát hẹp nhất là (VT,VVT)} End;
Rõ ràng nếu khả năng thông qua của tất cả các cung của đồ thị là những số nguyên, thì giá trị của luồng sẽ tăng lên ít nhất là 1 sau mỗi lần tăng luồng. Từ đó suy ra thuật toán trên luông dừng sau không quá val(f*) lần tăng luồng và cho ta luồng cực đại trong mạng. Ta có các kết quả sau: Định lý 2. (Định lý về luồng cực đại trong mạng và lát cắt hẹp nhất). Luồng cực đại trong mạng bằng khả năng thông qua của lát cắt hẹp nhất. Định lý 3. (Định lý về tính nguyên). Nếu tất cả các khả năng thông qua là các số nguyên thì luôn tìm được luồng cực đại với luồng trên các cung là các số nguyên. Tuy nhiên, nếu khả năng thông qua là các số rất lớn thì giá trị của luồng cực đại cũng có thể rất lớn và thuật toán ở trên đòi hỏi phải thực hiện nhiều bước tăng luồng. Gần đây người ta đã đưa ra các thuật toán với độ phức tạp tính toán tốt hơn, tuy nhiên thuật toán Ford-Fulkerson cũng được đánh giá là một trong những thuật toán kinh điển để giải các bài toán ứng dụng về luồng cực đại trong mạng. Tiếp theo là phần cài đặt cụ thể của thuật toán bằng ngôn ngữ Pascal. Chương trình dưới đây có sử dụng dữ liệu vào được cho trong file Luong.inp có dạng như sau: Dòng đầu tiên gồm ba số nguyên là số đỉnh của mạng n, đỉnh phát s, đỉnh thu t. Tiếp theo là một ma trận kích thước n x n thể hiện ma trận trọng số của đồ thị có hướng minh hoạ cho mạng cần tìm luồng cực đại. Dữ liệu ra được cho trong file Luong.out có dạng như sau: Phần đầu tiên là một ma trận kích thước n x n thể hiện luồng cực đại tìm được (phần tử (i,j) của ma trận là luồng trên cung (i,j)). Dòng tiếp theo là một số nguyên cho biết giá trị luồng cực đại trong mạng. Chẳng hạn với mạng được cho trong hình vẽ ở trên thì các file tương ứng là: luong.inp 616 034000 000320 010030 000004 000003 000000 luong.out 033000 000300 000030 000003 000003 000000 6 Nội dung chương trình như sau: var vt,e,p:array [1..50] of integer; c, f:array [1..50,1..50]of byte; u,v,l,s,t,n,Tang:integer; Path_Found,stop:boolean; procedure init; var ff:text;i,j:byte;
begin assign(ff,'Luong.inp'); reset(ff); readln(ff,n,s,t); for i:=1 to n do for j:=1 to n do begin read(ff,c[i,j]);f[i,j]:=0; end; close(ff); stop:=false; end; procedure Find_Path; var vt1: set of byte; begin p[s]:=s;e[s]:=maxint; l:=1;vt[l]:=s;vt1:=[s]; Path_Found:=true; while l>0 do begin u:=vt[l];l:=l-1; for v:=1 to n do if not ( v in vt1)then begin if (c[u,v]>0)and(f[u,v] begin p[v]:=u;e[v]:=e[u]; if e[v]>c[u,v]-f[u,v] then e[v]:=c[u,v]-f[u,v]; l:=l+1;vt[l]:=v;vt1:=vt1+[v]; if v=t then exit; end; if (c[v,u]>0)and(f[v,u]>0)then begin p[v]:=-u;e[v]:=e[u]; if e[u]>f[v,u]then e[v]:=f[v,u]; l:=l+1;vt[l]:=v;vt1:=vt1+[v]; if v=t then exit; end; end; end; Path_Found:=false; end; procedure Inc_Flow; begin v:=p[t];u:=t;Tang:=e[t];
while us do begin if v>0 then f[v,u]:=f[v,u]+Tang else begin v:=-v; f[u,v]:=f[u,v]-Tang; end; u:=v;v:=p[u]; end; end; procedure Result; var value:integer;ff:text; begin assign(ff,'Luong.out'); rewrite(ff); value:=0; for u:=1 to n do begin if f[s,u]>0 then inc(value,f[s,u]); for v:=1 to n do write(ff,f[u,v]:3); writeln(ff); end; writeln(ff,value:3); close(ff) end; procedure Max_Flow; begin while not stop do begin Find_Path; if Path_Found then Inc_Flow else stop:=true; end; end; begin init; Max_Flow; result; end. 3. Một số bài toán ứng dụng Bài 1. (mạng với nhiều điểm phát và nhiều điểm thu) Cho n kho cần chuyển hàng s1,s2,.. sn và m kho nhận hàng t1,t2,.. ,tm. Hãy tìm một phương án chuyển hàng sao cho lượng hàng được chuyển là lớn nhất, cho biết trước
số lượng hàng cần chuyển cũng như khả năng chứa hàng ở mỗi kho và số hàng có thể chuyển từ si đến tj là c(i,j). Bài toán này có thể đưa về bài toán mạng với nhiều điểm phát và điểm thu. Ta coi các kho si là các điểm phát, các kho nhận tj là các điểm thu. Đồng thời đưa vào một điểm phát giả s nối với tất cả các điểm phát và một điểm thu giả t được nối với các điểm thu. Giá trị c(s,si) bằng số hàng cần chuyển ở kho si , và c(tj,t) bằng khả năng chứa hàng trong kho tj . Bài 2. (bài toán với khả năng thông qua ở các cung và các đỉnh) Hãy tìm một phương án vận chuyển dầu từ một bể chứa s tới bể nhận t thông qua hệ thống đường ống dẫn dầu, sao cho lượng dầu chuyển được là nhiều nhất. Cho biết trước lượng dầu lớn nhất có thể bơm qua mỗi đường ống và qua mỗi điểm nối giữa các ống. Phương án giải bài toán như sau: xây dựng đồ thị G = (V,E), với V là tập các đỉnh của đồ thị gồm s, t và tập các điểm nối, còn E là tập các cung của đồ thị gồm các đường ống dẫn dầu. Trong G, với mỗi đỉnh v thuộc V thì tổng luồng đi vào đỉnh v không được vượt quá khả năng thông qua d(v) của nó: Σf(w,v) ≤ d(v) w thuộc V để tìm luồng cực đại giữa s và t trong mạng như vậy ta xây dựng một mạng G′ sao cho: mỗi đỉnh v của G tương ứng với hai đỉnh v+ và v - trong G′, mỗi cung (u,v) trong G tương ứng với cung (u-,v+) trong G′, và mỗi cung (u-,u+) trong G′ có khả năng thông qua là d(v) tức là bằng khả năng thông qua của đỉnh v trong G. Dễ thấy luồng cực đại trong G′ bằng luồng cực đại trong G với khả năng thông qua của các cung và các đỉnh. Bài 3. (đề thi sinh viên giỏi toàn quốc 1994-1995). Cho một bảng chữ nhật kích thước MxN (M, N < 100) các ô vuông. Trong đó có một số ô trằng, còn lại là đen. Hãy chọn 2M ô đên trong bảng sao cho thoả mãn các điêu kiện: 1) mỗi dòng chọn đúng 2 ô đen 2) số ô đen được chọn trong cột chọn nhiều ô nhất là nhỏ nhất. Ta phát biểu bài toán dưới một dạng khác: xét mạng gồm N + M + 2 đỉnh, gồm hai đỉnh thu và phát s, t ; M đỉnh tương ứng với M dòng còn N đỉnh còn lại tương ứng với N cột của bảng. Đỉnh s nối với tất cả các đỉnh tương ứng với dòng, các đỉnh tương ứng với cột nối với đỉnh thu t, nếu ô (i,j ) là ô đen thì ta nối đỉnh thứ i của dòng với đỉnh thứ j của cột. Khả năng thông qua của các cung được xác định như sau: - Mọi cung xuất phát từ đỉnh s có khả năng thông qua bằng 2. - Mọi cung nối cặp đỉnh dòng và cột có khả năng thông qua bằng 1. - Mọi cung nối với đỉnh thu t thì khả năng thông qua sẽ thay đổi trong quá trình thay đổi bài toán luồng để thoả điều kiện thứ hai của bài toán, song chúng luôn bằng nhau, ban đầu khả năng thông qua của các cung này đều bằng 1. Sau mỗi bước tìm được luồng cực đại ta có thể tăng khả năng thông qua của các cung này thêm 1 đơn vị phụ thuộc vào luồng vừa tìm được đã thoả mãn điều kiện thứ nhất của bài toán hay chưa. Bài toán phát biểu lại như sau: Tìm một mạng có khả năng thông qua của các cung tại đỉnh thu là bé nhất sao cho giá trị của luồng tại các cung chứa đỉnh phát đều bằng 2. Với cách phát biểu trên ta có thuật toán giải như sau: 1. Ban đầu xét mạng có khả năng thông qua tại các cung chứa đỉnh thu đều bằng 1.
2. Mỗi bước tìm một luồng cực đại. Nếu luồng tìm được thoả mãn điều kiện 1, nghĩa là giá trị luồng tại mỗi cung chứa đỉnh phát đều bằng 2 thì ta dừng thuật toán, ngược lại ta tăng khả năng thông qua của các cung thêm một đơn vị và quay lại bước 2. Bài toán không tồn tại lời giải khi khả năng thông qua của các cung chứa đỉnh thu đều bằng N mà không tồn tại luồng cực đại sao cho giá trị của luồng tại các cung chứa đỉnh phát đều bằng 2. Bài 4. Có n sinh viên cần đi thực tập ở m trường. Mỗi sinh viên i có quyền đăng ký nguyện vọng thực tập vào các trường với số lượng trường đăng ký là c(i): 0 ≤ c(i) ≤ m. Hãy tìm một phương án bố trí các sinh viên vào các trường sao cho thoả mãn được nhiều nguyện vọng nhất và nếu có thể thì số lượng trường có sinh viên được bố trí vào thực tập càng ít càng tốt. Dữ liệu vào cho trong tệp THUCTAP.INP có cấu trúc như sau: dòng đầu gồm hai số nguyên n, m; tiếp theo là một ma trận gồm n hàng, m cột: ô (i,j) bằng 1 nếu sinh viên i có nguyện vọng đăng ký thực tập ở trường j và bằng 0 trong trường hợp ngược lại. Dữ liệu ra ghi vào tệp THUCTAP.OUT gồm một ma trận gồm n hàng, m cột: ô (i,j) bằng 1 nếu sinh viên i được bố trí thực tập ở trường j và bằng 0 trong trường hợp ngược lại. Bài toán này khá dễ giải nếu ta phát hiện ra rằng: để thỏa mãn yêu cầu thứ hai của đầu bài thì chỉ cần bỏ đi một số lượng các trường nhiều nhất trong tập m trường đã cho sao cho số nguyện vọng được thoả mãn vẫn giữ nguyên như khi chưa bỏ đi trường nào. Các bài toán có thể giải được thông qua thuật toán đã trình bày rất phong phú và đa dạng. Nó còn được sử dụng nhiều trong các bài toán tổ hợp như bài toán đám cưới vùng quê, các bài tối ưu rời rạc (bài toán lập lịch, phân nhóm).. Trong các bài toán dạng này, có một số bài có thể đưa về bài toán tìm cặp ghép đầy đủ tối ưu ( bạn đọc có thể tham khảo thêm trong bài Cặp ghép của tác giả Lê Văn Chương, trong số báo 11/2001 ). Tài liệu tham khảo: [1] Nguyễn Đức Nghĩa, Nguyễn Tô Thành-Toán học rời rạc. Nhà xuất bản giáo dục- 1997. [2] Robert Sedgewick.' Algorithm ' Princeton University ( USA ) Ađison - Wesley Publishing Co. [3] Một số sách báo và tài liệu tham khảo khác. Nguyễn văn Trường Một số ứng dụng của bài toán luồng cực đại Lê Thanh Hà Ta xét bài toán sau: - Có m chàng trai, mỗi chàng biết những cô gái mà anh ta vừa ý trong n cô gái trong làng, liệu có thể xếp cặp cho cả m chàng trai đó không.
- Có m thợ, mỗi thợ có khả năng làm được một số công việc nào đó. Và bạn hãy xắp xếp việc làm cho m thợ sao cho mội thợ chỉ làm một việc và mỗi việc chỉ do một người thợ đảm nhiệm. Để giải quyết hai bài toán trên ta xây dựng đồ thị với các đỉnh biểu thị cho các chàng trai Ti(hay người thợ) và các cô gái (hay công việc) còn các cạnh biểu thị sự vừa ý của các chàng trai đối với các cô gái Gi (hay khả năng của các người thợ đối với các công việc). Khi đó đồ thị mà ta nhận được là đồ thị hai phía. Giả sử ta đã thu được đồ thị sau: Ta gán cho trọng số của mỗi cạnh là 1. Và tìm luồng cực đại từ S sang T. Nhưng nếu áp dụng thuật toán lát cắt hẹp nhất để tìm luồng cực đại trong một đồ thị tương đối đơn giản này thì quả thật là "đem dao mổ trâu để giết ruồi". Bạn hãy đọc kĩ đoạn chương trình sau, thuật toán đã cắt lược đi rất nhiều bước của thuật toán tìm luồn cực đại để giải bài toán trên. Trong đó hoàn toàn không còn các đỉnh S và T nữa và thời gian của thuật toán này so với thuật toán tìm luồng chuật thì thật tuyệt vời. Và thực tế nó đã hoàn toàn chuyển sang dạng thuật toán tìm cặp ghép cực đại trong đồ thị hai phía. uses crt; const fi = 'input.txt'; fo = 'output.txt'; var m:array[1..200,1..200] of byte; a,b,c,dt:array[1..200] of byte; s:string; n:byte; f:text; time:longint; tich:longint absolute 0:$46c; procedure input; var i,j:byte;
begin assign(f,fi); reset(f); readln(f,n); fillchar(m,sizeof(m),0); while not eof(f) do begin readln(f,i,j); m[i,j]:=1; end; close(f); end; procedure tim; label done; var i,j,k:byte; begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); for i:=1 to n do if a[i]=0 then begin s:=chr(i); fillchar(c,sizeof(c),0);
repeat k:=ord(s[length(s)]); delete(s,length(s),1); for j:=1 to n do if (c[j]=0) and (m[k,j]=1) then begin c[j]:=1; dt[j]:=k; if b[j]>0 then s:=s+chr(b[j]) else begin repeat b[j]:=dt[j]; k:=a[dt[j]]; a[dt[j]]:=j; j:=k; until j=0; goto done; end; end; until s=''; done: end; writeln(tich-time); assign(f,fo);
rewrite(f); k:=0; for i:=1 to n do if a[i]0 then inc(k); writeln(f,k); for i:=1 to n do if a[i]0 then writeln(f,i,' ',a[i]); close(f); end; begin input; time:=tich; tim; end. Tuy nhiên bài toán sẽ thực sự khó hơn nếu như mỗi chàng trai sẽ có một mức độ tình cảm nào đó đối với mỗi cô gái hay mỗi nguời thợ sẽ có một năng xuất nào đó đỗi với mỗi công việc. Và công việc của ta phải làm là ghép cặp cho các chàng trai với các cô gái và người thợ với mỗi công việc để không những thoả mãn điều kiện như cũ mà tổng số mức độ tình cảm hay năng xuất phải là lớn nhất. Để giải quyết vấn đề trên ta tiếp tục cải tiến thuật toán trên: Trước tiên ta xây dựng một đồ thị hai phía mới với các đỉnh vẫn như cũ. Ta lần lượt thêm vào đồ thị từng cạnh của đồ thị cũ theo thứ tự từ cao xuống thấp của giá trị trọng số. Sau mỗi lần thêm, ta lại tìm một cặp ghép cực đại trong đồ thị đó cho tới khi tìm được giá trị cực đại đó bằng m thì dừng. Bạn tham khảo chương trình sau: uses crt; const fi = 'input.txt'; fo = 'output.txt'; var m,dx:array[1..150,1..150] of byte; a,b,c,dtr:array[1..150] of byte;
n:byte; dem:word; f:text; time:longint absolute 0:$46c; tich:longint; procedure input; var i,j:Byte; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do begin for j:=1 to n do read(f,m[i,j]); readln(f); end; close(f); end; procedure work; label 1; var i,j,k,x,y,max,max1:byte; s:string; ok:boolean;
begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(dx,sizeof(dx),0); max:=0; for i:=1 to n do for j:=1 to n do if m[i,j]>max then max:=m[i,j]; repeat max1:=0; for i:=1 to n do for j:=1 to n do if (dx[i,j]=0) and (m[i,j]>max1) then begin max1:=m[i,j]; x:=i; y:=j; end; dx[x,y]:=1; for i:=1 to n do if a[i]=0 then begin s:=chr(i); fillchar(c,sizeof(c),0);
repeat k:=ord(s[1]); delete(s,1,1); for j:=1 to n do if (dx[k,j]=1) and (c[j]=0) then begin dtr[j]:=k; c[j]:=1; if b[j]0 then s:=s+chr(b[j]) else begin repeat b[j]:=dtr[j]; k:=a[b[j]]; a[b[j]]:=j; j:=k; until j = 0; goto 1; end; end; until s = ''; 1: end; ok := false;
for i:=1 to n do if a[i]=0 then begin ok := true; writeln(time-tich); break; end; until ok =false; assign(f,fo); rewrite(f); dem:=0; for i:=1 to n do dem:=dem+m[i,a[i]]; writeln(f,dem); for i:=1 to n do writeln(f,i,' ',a[i],' ',m[i,a[i]]); close(f); end; begin input; tich:=time; work; write(time-tich); end. Bạn hoàn toàn có thể tiếp tục cải tiến để nâng cao tốc độ của bài toán trên, chúc bạn thành công. Lê Thanh Hà
Superdo Home Học tập Ứng dụng luồng cực đại trong bài toán tối ưu rời rạc Main Menu • Home • Học tập • Game • Web hay Ứng dụng luồng cực đại trong bài toán tối ưu rời rạc • • 1 • 2 • 3 • 4 • 5 ( 0 Votes ) Written by Administrator Thursday, 31 December 2009 04:38 Ứng dụng luồng cực đại trong bài toán tối ưu rời rạc Đức Trọng I. Bài toán Xétbài toán: Trongđó aij thuộc {0,1} pi nguyên dương i = 1,2,…,m; j = 1,2,…,n
Bài toán trên là mô hình toán học của nhiều bàitoán tối ưu tổ hợp trong thực tế. Ví dụ: II. Vídụ 1. Bài toán phânnhóm sinh hoạt: Cóm sinh viên và n nhóm sinh hoạt chuyên đề.Với mỗi sinh viên i biết: - aij =1, nếu sinh viêni có nguyện vọng tham gia vào nhóm j - aij =0, nếu ngượclại - pi là số lượngnhóm chuyên đề mà sinh viên i phải tham dự i=1,2,…,m; j=1,2,…,n Trong số các cách phân các sinh viên vào nhóm chuyênđề mà họ có nguyện vọng tham gia và đảm bảo mỗi sinh viên i phảitham gia đúng pi nhóm, hãy tìm cách phân phối với số người trong nhómcó nhiều sinh viên tham gia nhất là nhỏ nhất có thể được. Đưa vào các biến số: xij =1, nếu sinh viên i tham gia vào nhóm j xij = 0, nếu ngược lại i=1,2,...,m ; j=1, 2,...,n, khi đó dễ thấy mô hình toán học cho bài toánđặt ra chính là bài toán (1)-(2). 2. Bài toán lậplịch cho hội nghị: Mộthội nghị có m tiểu ban, mỗi tiểu ban cần sinh hoạt trong một ngày tạiphòng họp phù hợp với nó. Có n phòng họp dành cho việc sinh hoạt củacác tiểu ban. Biết: - aij =1, nếu phòng họpi là thích hợp với tiểu ban j - aij =0, nếu ngượclại i=1,2,...,m, j=1, 2,...,n. Hãy bố trí các phòng họp cho các tiểu bansao cho hội nghị kết thúc sau ít ngày làm việc nhất. Đưa vào các biến số : xij = 1, nếu bố trí tiểu ban i làm việc ở phòng j xij = 0, nếu ngược lại i=1, 2,...,m ; j=1, 2,...,n, khi đó dễ thấy mô hình toán học cho bài toánđặt ra chính là bài toán (1)-(2), trong đó pi =1, i=1, 2,...,m. III. Cơ sở thuật toán Bổ đề 1: Bài toán (1)-(2) có nghiệm tối ưu khi và chỉ khi: Chứng minh: Điều kiện cần là hiển nhiên vì sự tồn tại phương án của bàitoán suy ra bất đẳng thức trong (3) được thực hiện ít nhất dưới dạng dấu đẳngthức. Điều kiện đủ: Chỉ cần chỉ ra rằng nếu có (3) thì luôn có phươngán. Giả sử (3) đúng, gọi:
Do(3) là điều kiện để (1)-(2) có nghiệm nên trong phần tiếp theo ta luôngiả thiết rằng điều kiệnđược thực hiên. Bâygiờ ta chỉ ra rằng bài toán (1)-(2) có thể chuyển về giải một số hữuhạn bài toán luồng cực đại trong mạng. Trước hết với mỗi k nguyêndương ta xây dựng mạng G(k) = (V,E) với e thuộc E:khả năng thông qua c(e) c(s,ui) = pi c(ui,vj) = aij c(vj,t) = k Bổđề 2: Giả sử vớik nào đó luồng cực đại trong mạng G(k) có giá trị Δ thì x* với x*ij = Φ (ui,vj)là phương án của bài toán (1)-(2) trong đó Φ (ui,vj)là luồng qua (ui,vj) Chứngminh: Thật vậy, do luồng cực đại trong mạng có giá trị Δ và là nguyên nên Φ (s,ui) = pivà Φ (ui,vj) thuộc {0,1}với i=1,2,…,m;j=1,2,…,n Vậy x* là phương án của bài toán (1)-(2) (đpcm). Bổđề 3: Giả sử x*là phương án tối ưu và k* là giá trị tối ưu của bài toán(1)-(2) thì luồng cực đại trong G(k*) có giá trị Δ Chứng minh: Do giá trị của luồng cực đại trong mạng G(k*)không vượt qu Δ, nên để chứng minh bổ đề ta chỉ cần chỉ ra luồngvới giá trị Δ trong mạng G(k*). Ta xây dựng luồng Φ như sau: Dễ dàng chứng minh Φ là luồng trong mạng G(m) có giá trị Δ.(đpcm) Bổđề 4: Nếu k=m thìluồng cực đại trong mạng G(m) có giá trị Δ.