Bàn luận thêm về Cặp ghép

Nguyễn Tuấn Dũng

'Ghép cặp' các đốitượng theo một quan hệ nào đó là một bài toán mang tính hết sức tự nhiên và cónhiều ý nghĩa trong ứng dụng thực tiễn. Chẳng hạn, các sinh viên ngành sư phạmdo được nhà nước đào tạo miễn phí nên khi ra trường họ được phân công về dạyhọc ở các trường miền núi. Nhưng những sinh viên đó được đưa ra danh sách nhữngtrường mà mình muốn công tác với độ ưu tiên khác nhau. Một bài toán đặt ra làphải bố trí các sinh viên này sao cho phù hợp nhất (có thể được) với sở thíchcủa mỗi người, tuy nhiên ở đây, sinh viên nào có kết quả học tập tốt hơn sẽđược ưu tiên hơn. Hay ta có thể gặp vấn đề ghép cặp trong các bài toán quenthuộc khác như: bài toán phân công công việc, bài toán hôn nhân bền vững, bàitoán xếp thời khoá biểu...

Trong số 26(11/2001), tác giả Lê Văn Chương đã giới thiệu với chúng ta thuật toánKuhn-Munkres giải bài toán tìm cặp ghép có tổng trọng số lớn nhất. ở đây, không đi vào thuật toán tìm cặpghép có tổng trọng số lớn nhất nữa vì điều đó khá rõ ràng trong số báo trước.Tuy nhiên, chúng ta sẽ xem xét thêm một chút để giúp các bạn phần nào tiếp cậngần bài toán hơn và đỡ nhầm lẫn trong lúc cài đặt chương trình. Để tiện theodõi, ta tóm tắt lại bài toán:

Cho G = (X U Y,E) là đồ thị hai phía đầy đủ, trong đó: X, Y là hai tập hữu hạn gồm n phần tử, E là tập các cạnh của đồ thịvà với mỗi cạnh được gán với một trọng số Cij. Cần tìm tập cặp ghépđầy đủ M có tổng trọng số lớn nhất.

Đối với bài toánnày có thể sử dụng bài toán luồng cực đại để giải bằng cách thêm vào G hai đỉnhgiả S và T, nối với các đỉnh xi thuộc X và nối T với các đỉnh yj thuộc Ybằng các cạnh có trọng số là 0. Tuy nhiên, bài toán cặp ghép cực đại là trườnghợp riêng của bài toán luồng nên nó có những đặc điểm riêng và do đó dẫn đếnviệc giải quyết nó thì cũng có những thuật toán đặc thù, mà tiêu biểu là thuậttoán gán nhãn, trong đó ta có thể đi theo hai hướng chính:

Hướng thứnhất, xuất phát từ một cặp ghép M đầy đủ bất kỳ của G, ta xây dựng một nhãnF tương ứng với M, nếu F chấp nhận được thì M là nghiệm cần tìm, ngược lại nhãnF là không chấp nhận được thì ta tiếp tục điều chỉnh.

Hướng thứ hai,xây dựng một nhãn F chấp nhận được, sau đó tìm M tương ứng với F bằng cách:khởi tạo M là tập rỗng, chừng nào mà M chưa đầy đủ thì ta còn tiếp tục điềuchỉnh (tăng cặp ghép).

Thuật toánKunh-Munkres trình bày trên số báo 26 là cách giải thứ hai, được trình bày khárõ ràng. Tuy nhiên có điểm cần chú ý trong bước 5 (sửa nhãn), lượng sửa nhãnkhông phải:

d:=min {F(xi)+ F (yj) - Cij, xi thuộc S, yj thuộc T} (cóthể do lỗi khi in ấn) mà là:

d:=min {F(xi)+ F(yj) - Cij, xi thuộc S, yj thuộc T } (*)

Bởi vì, trongbước 3 khi không tìm được đường tăng cặp ghép ta mới phải sửa nhãn sao cho:

- Nhãn Fmớivẫn chấp nhận được.

- Fmớivẫn tương ứng với M đang có, để cho số cạnh của G (F, M) không bị giảm đi.

- Tăng thêm sốcạnh trong đồ thị cân bằng tương ứng G (F, M)

Muốn tăng sốcạnh trong G(F, M) thì ta phải có thêm cặp xi', yj' khác,cụ thể (xi', yj') thuộc G(F, M), sao cho: F(xi')+ F(yj') = C'ij. Đồng thời để cho sau khi thêm cạnh vàoG(F, M) ta có thể tìm đường tăng cặp ghép thì cạnh cần thêm đó được chọn làcạnh nối giữa một đỉnh xi đã được đi đến trong quá trình tìm đường ởbước 3 với một đỉnh yj' chưa được đi đến trong quá trình đó.

Nếu lượng sửanhãn là d:=min{F(xi)+ F (yj) - Cij, xi thuộc S, yj thuộc T} thìsẽ dẫn đến những sai sót khiến chương trình không cho ra kết quả. Thật vậy, tacho ra công thức sửa nhãn:

F(xi) := F(xi)- d với xi thuộcS

F(yj) := F(yj)+ d với yj thuộcT

Xét một ví dụđơn giản, sau khi sửa nhãn với lượng sửa nhãn d như trên, đối với những đỉnh xithuộc S vàyj thuộc T,ta có:

F(xi) mới :=F(xi) cũ - d

F(yj)mới :=F(yj)cũ

Suy ra:

A = F(xi)mới +F(yj)mới - Cij = F(xi)cũ+ F(yj)cũ - Cij - d

Nhận thấy A cóthể dương, bằng không, hay âm tuỳ thuộc vào các xi, yjgán nhãn Fcũ vì d chỉ là min {F(xi)cũ +F(yj)cũ - Cij } đối với những đỉnh xithuộc S, yjthuộc T.Do đó có thể xảy ra F(xi)mới + F(yj)mới< Cij với một vài cặp cạnh (xi,yj) nào đómà xi thuộc S,yj thuộc T.Nói cách khác, nhãn Fmới sẽ là không chấp nhận được, ít nhất là đốivới những đỉnh yj thuộc T.

Trong khi đó,theo như dưới đây ta sẽ thấy việc gán nhãn công thức (*) là hoàn toàn đúng đắn.Thật vậy:

Ta có công thứcsửa nhãn:

F(xi) := F(xi)- d với xi thuộc S

F(yj) := F(yj)+ d với yj thuộc T

Nhận thấy, dotính chất đặc biệt của G(F, M), chỉ có thể đi từ yj sang xikhi và chỉ khi (xi, yj) thuộc M nên tập S (tập các đỉnh đếnđược trong bước 3 tìm đường tăng cặp ghép) sẽ là tập các đỉnh của X đã đượcghép cặp (trừ x0). Đồng thời, khi không có đường tăng cặp ghép nghĩalà trong khi tìm đường đi, ta chỉ đến được các yj đã bị ghép cặp. Dođó tập T cũng là tập các đỉnh của Y đã ghép cặp (với các đỉnh thuộc S)

Bây giờ ta sẽxem xét các trường hợp:

1. Đối vớinhững xi thuộcS: F(xi)mới := F(xi)cũ - D

- Xét các đỉnh yjthuộc T: F(yj)mới := F(yj)cũ

Suy ra: F(xi)mới + F(yj)mới- Cij = F(xi)cũ + F(yj)cũ- Cij - D >= 0

(vì D = min {F(xi)cũ+ F (yj)cũ - Cij } với xi thuộc S, yjthuộc T)

do đó: F(xi)mới + F(yj)mới>= Cij , xi thuộc S, yj thuộc T (1)

Vậy nhãn F vẫnchấp nhận được đối với những xi thuộc S và yj thuộc T.

Ngoài ra ta còncó thêm đẳng thức F(xi) + F(yj) = Cij trong đóxithuộc S,yj thuộc Ttương ứng với việc xảy ra dấu '=' trong bất đẳng thức lượng sửa nhãn (luôn luônxảy ra). Do đó dẫn tới việc làm tăng thêm số cạnh của G(F, M).

- Xét yjthuộc T:F(yj)mới := F(yj)cũ + D

Do đó: F(xi)mới+ F(yj)mới = F(xi)cũ - D + F(yj)cũ+ D = F(xi)cũ +F(yj)cũ = Cij (2)

bởi vì với xithuộc S vàyj thuộcT trong bước 3 thì (xi, yj) là một cạnh của đồ thị cânbằng tương ứng G(F, Mcũ)

Như vậy, nhãn Fmớivẫn tương ứng tập cặp ghép Mcũ ngay cả với những đỉnh bị sửa nhãn.Đối với những đỉnh còn lại của Mcũ không bị sửa nhãn thì cũng vẫntương ứng với Fmới vì Fmới là giữ nguyên giá trị của Fcũđối với những đỉnh này.

2. Đối với xithuộc S:F(xi)mới = F(xi)cũ

mà: F(yj)mới= F(yj)cũ với yj thuộc T

F(yj)mới = F(yj)cũ+ D với yj thuộc T

thì: F(xi)mới+ F(yj)mới >= F(xi)cũ + F(yj)cũ>= Cij (3)

(vì nhãn Fcũlà chấp nhận được)

Tóm lại, từ (1)(2) (3) ta kết luận sau khi sửa nhãn, nhãn Fmới vẫn chấp nhận đượcvà tương ứng với Mcũ đang có, đồng thời thêm được cạnh trong G(F,M). Do đó, quay lại bước 3 ta vẫn có thể tìm được đường tăng cặp ghép và tiếptục các bước tiếp theo của thuật toán.

Trên đây đã bànluận một số chi tiết trong các bước thực hiện thuật toán Kuhn-Munkres. Tiếptheo, vấn đề đặt ra là đối với bài toán tìm cặp ghép đầy đủ có tổng trọng sốnhỏ nhất thì sao?

Cặp ghép đầy đủ cótổng trọng số nhỏ nhất

Nếu bạn xem xétkỹ lưỡng một chút về thuật toán Kuhn-Munkres thì có thể thấy ngay bài toán nàyhoàn toàn tương tự với bài toán tìm cặp ghép có tổng trọng số lớn nhất. Chỉ cầnsửa lại một chút như sau:

+ Thứ nhất,nhãn F được gọi là chấp nhận được nếu F(xi) + F(yj) <=Cij

Như vậy, có thểkhởi tạo: F(xi) := 0

F(yj):= min {Cij, xi thuộcX }, yj thuộcY

+ Thứ hai,lượng sửa nhãn: d:= max{F(xi)+ F(yj) - Cij , xi thuộc S, yj thuộc T}

với nhận xét: d<= 0

Hoặc: d:=min {Cij - F(xi)- F(yj), xi thuộcS, yj thuộc T}

thì d >= 0 vàkhi đó, công thức sửa nhãn sẽ là: F(xi):= F(xi) + d

F(yj):= F(yj) - d

Cách khác, đơngiản hơn, chúng ta có thể thấy để tìm M có tổng trọng số nhỏ nhất, chỉ cần đổidấu các phần tử của ma trận trọng số rồi tìm cặp ghép có tổng trọng số lớn nhấtvới ma trận trọng số mới này. Cặp ghép đó sẽ chính là cặp ghép có tổng trọng sốnhỏ nhất cần tìm đối với ma trận trọng số ban đầu.

Như chúng ta đãbiết bài toán cặp ghép được xem xét theo hai khía cạnh. Trường hợp thứ nhất,người ta quan tâm đến việc ghép cặp đầy đủ và thoả mãn tính tối ưu như bài toánKuhn-Munkres ở trên. Nhưng trong trường hợp khác, người ta lại không quan tâmđến việc ghép cặp đầy đủ với tổng trọng số lớn nhất mà cần tìm một tập cặp ghépcó số lượng cặp ghép là cực đại (không quan tâm đến trọng số trên các cạnh củacặp ghép). Khi đó chúng ta sẽ có một bài toán khác dưới đây:

Cặp ghép cực đại

Để minh hoạ, taxét một bài toán cụ thể, bài toán Phân công thợ-việc: Có N người thợvà M công việc, mỗi công việc, mỗi một người thợ chỉ biết làm một số công việcnhất định. Cần phân công mỗi thợ chỉ làm một việc và mỗi việc chỉ được làm bởimột thợ sao cho có nhiều công việc được làm nhất. Khả năng làm việc của các thợđược cho trong ma trận Cij với Cij = 1 thì thợ i biết làmviệc j, Cij =0 thì thợ i không biết làm việc j.

Ta nhận thấyhoàn toàn có thể giải bài toán này bằng thuật toán Kunh-Munkres. Tuy nhiên, vấnđề ở đây là bài toán của chúng ta đơn giản hơn nhiều và tất nhiên, có thể giảiquyết nó bằng một cách riêng khá dễ dàng.

Bàn luận thêm về cặp ghép

Nguyễn Tuấn Dũng

(Tiếp theo số trước)

Nhắc lại bài toán phân công Thợ - Việc: Có N người thợ và M công việc, mỗi côngviệc, mỗi một người thợ chỉ biết làm một số công việc nhất định. Cần phân côngmỗi thợ chỉ làm một việc và mỗi việc chỉ được làm bởi một thợ sao cho có nhiềucông việc được làm nhất. Khả năng làm việc của các thợ được cho trong ma trận Cijvới Cij = 1 thì thợ i biết làm việc j, Cij =0 thì thợ ikhông biết làm việc j.

Ta nhận thấy hoàn toàn có thể giải bài toán nàybằng thuật toán Kunh-Munkres. Tuy nhiên, vấn đề ở đây là bài toán của chúng tađơn giản hơn nhiều và tất nhiên, có thể giải quyết nó bằng một cách riêng khádễ dàng.

Với các khái niệm và định nghĩa như trong bàitoán Kunh-Munkres (tuy nhiên, đồ thị hai phía G ở đây không nhất thiết đầy đủ),ta sử dụng định lý sau để có được thuật toán:

Tập cặp ghép M (có thể không đầy đủ) là cực đạikhi và chỉ khi không tìm được đường đi bắt đầu từ một đỉnh tự do thuộc X và kếtthúc tại một đỉnh tự do thuộc Y trên đồ thị G' = (X U Y, E'). Đường đi đó gọilà đường tăng cặp ghép, và G' nhận được từ G bằng cách định hướng lại các cạnhcủa G theo quy tắc:

- Những cạnh (x, y) thuộc Mtrong đồ thị G được định hướng ngược lại trở thành cung (y, x) trong đồ thị G'.

- Những cạnh (x, y) không thuộc M trong đồ thị Gđược định hướng trở thành cung (x, y) trong đồ thị G'.

Như vậy, ta có nhận xét sau: giả sử đã xây dựngđược một tập cặp ghép M nhưng vẫn có đường tăng cặp ghép từ đỉnh tự do x0thuộc X đến đỉnh tự do y0 thuộc Y:

x0--> y1--> x1--> y2-->... --> xt--> y0

trongđó các cạnh đậm là các cạnh thuộc tập cặp ghép đã có. Dễ thấy vì đường tăng cặpghép xuất phát từ đỉnh tự do x0 thuộc X đến đỉnh tự do y0thuộc Y nên số cạnh nhạt trên đường đi sẽ lớn hơn số cạnh đậm. Khi đó nếu đổichỗ các cạnh nhạt thành cạnh đậm, các cạnh đậm thành cạnh nhạt thì ta được tậpcặp ghép mới M' có lực lượng lớn hơn M.

Tómlại, sơ đồ thuật toán như sau:

Bước 1 : Khởi tạo tập cặpghép M là rỗng.

Bước 2 : Tìm đường cặpghép từ một đỉnh x0 tự do thuộc X đến một đỉnh y0 tự dothuộc Y:

+Nếu có thì chuyển sang bước 3.

+Nếu không có thì tập cặp ghép hiện thời là cực đại và kết thúc thuật toán.

Bước 3 : tăng cặp ghép:

Thựchiện việc đổi cạnh nhạt thành đậm và cạnh đậm thành nhạt. Tuy nhiên trong khicài đặt không phải xây dựng cụ thể đồ thị G' và đổi màu cạnh.

Quayvề bước 2.

Chươngtrình bài Phân công Thợ việc:

ProgramCapghepcucdai;

Uses Crt;

Const

Inf = 'Matching.inp';

Outf = 'Matching.out';

MaxN = 200;

MaxM = 200;

Var

A :array[0..MaxN,0..MaxM]of 0..1;

Tho:array[1..MaxN]of byte;

Viec :array[1..MaxM]of byte;

Pred :array[1..MaxN]of byte;

N,M :byte;

X0, Y0 : byte;

PathFound:boolean;

Procedure ReadInp;

var f:text;i,x:byte;

begin

fillchar(A, sizeof (A),0);

assign(f,inf); reset(f);

readln(f,N,M);

for i:=1 to n do

begin

while not(seekeoln(f)) do

begin

read(f,x);

A[i,x]:=1;

end;

readln(f);

end;

close(f);

end;

Procedure WriteOut;

var f:text; i,socv:byte;

begin

socv:=0;

for i:=1 to n do

if viec[i]>0 theninc(socv);

assign(f,outf); rewrite(f);

writeln(f,socv);

for i:=1 to n do

if viec[i]>0 thenwriteln(f,{'Thó,}i:3,{' - viec',}viec[i]:3);

close(f);

end;

ProcedureFindPath(x:byte);

var y:byte;

begin

for y:=1 to m do

begin

if(Pred[y]=0)and (A[x,y]=1) then

begin

Pred[y]:=x;

ifTho[y]=0 then

begin

Y0:=y;

PathFound:=true;

Exit;

end

else

begin

FindPath(Tho[y]);

end;

end;

ifPathFound then Exit;

end;

end;

Procedure IncM;

var x,y,y1:byte;

begin

y:=y0;

while pred[y]<>x0 do

begin

x:=pred[y];

tho[y]:=x;

y1:=viec[x];

viec[x]:=y;

y:=y1;

end;

viec[X0]:=y; tho[y]:=X0;

end;

Procedure Matching;

var Stop: boolean;x:byte;

begin

fillchar(Tho, sizeof(Tho),0);

fillchar(Viec, sizeof(Viec),0);

Stop:=false;

While not(Stop) do

begin

PathFound:=false;

fillchar(pred,sizeof(pred),0);

for x:=1 ton do

ifviec[x]=0 then

begin

X0:=x;

FindPath(x);

ifPathFound then Break;

end;

if PathFoundthen IncM {TangCG} else Stop:=true;

end;

end;

BEGIN

clrscr;

ReadInp;

Matching;

WriteOut;

END.

Córất nhiều bài toán được giải quyết bằng việc ghép cặp sao cho số cặp ghép làcực đại. Chẳng hạn như bài Xếp các con xe trên bàn cờ quốc tế: Trênbàn cờ quốc tế kích thước N x N (N < 251), ngu+o+'i ta dda'nh da^'u mo^.t o^ ba('ng ca'ch ghi tre^n ddo' so^' 1, ca'c o co'n la.i ghi so^' 0. Ha~y ti'm ca'ch dda(.t nhie^'u nha^'t ca'c con xe va'o ca'c o^ ddu+o+.c dda'nh da^'u sao cho kho^ng co' hai con xe na'o a(n ddu+o+.c nhau (tu+'c la' kho^ng co' hai con na'o xe^'p tre^n cu'ng mo^.t ha'ng hay cu'ng mo^.t co^.t).

Tuynhiên, có một dạng bài toán khác khá hay và thực tế mà cũng được giải bằngthuật toán ghép cặp cực đại. Đó là bài toán ta sẽ trình bày dưới đây:

Hệđại diện phân biệt

Định nghĩa : Cho một họtập con S1, S2,..., Sm thuộc X.

Mộtbộ sắp thứ tự gồm m phần tử (a1, a2,..., am)với a1 thuộc S1, a2 thuộc S2,...,am thuộc Sm, trong đó: ai khác ajvới i khác j (i, j = 1, 2,..., m) đượcgọi là một hệ đại diện phân biệt của họ S1, S2,..., Sm.

Bàitoán đặt ra là cần phải xây dựng một hệ đại diện phân biệt của một họ chotrước.

Vídụ, nhà trường tổ chức một buổi họp cán bộ của trường, đề nghị mỗi tổ chức cửmột người đi họp và mỗi người chỉ được đại diện cho một tổ chức. Tuy nhiên, mộtngười có thể giữ nhiều chức vụ trong các tổ chức khác nhau. Chẳng hạn, một bíthư liên chi có thể vừa là một lớp trưởng, một phó bí thư của lớp cũng có thểlà hội trưởng hội sinh viên của khoa... Cần lập chương trình sắp xếp mọi ngườiđi họp sao cho thích hợp.

Quaylại bài toán, trước hết, gọi tập Y = S1 U S2 U S3U... U Sm là hợp của tất cả các Si (chính là tập các phầntử khác nhau của họ S). Chúng ta có nhận xét sau về điều kiện để tồn tại một hệđại diện phân biệt là:

+Nếu lực lượng (số phần tử) của Y là n thì n tối thiểu phải bằng m. Nghĩa là n>= m.

Đểgiải bài toán hệ đại diện phân biệt, ta xây dựng đồ thị hai phía biểu diễn mốiquan hệ giữa các tập Si thuộc X và các phần tử yj thuộc Ycủa họ (j = 1, 2,..., n) bằng ma trận Cij được định nghĩa như sau:

Cij= 1 tương đương với phần tử yj thuộc tập Si

Cij= 0 tương đương với phần tử yj không thuộc Si

Từđây ta thấy bài toán đã được đưa về việc tìm một tập cặp ghép cực đại M (có lựclượng lớn nhất) của đồ thị G. Nếu lực lượng của M tìm được bằng đúng m thì tađã tìm được một hệ đại diện phân biệt. Còn nếu không thì kết luận là không tồntại một hệ đại diện phân biệt nào của họ S.

Trênđây chỉ là vài vấn đề bổ sung thêm cho bài toán cặp ghép mà tôi xin được giớithiệu để các bạn tham khảo và xem xét. Còn vô số bài toán khác liên quan đếnviệc 'ghép cặp' trong lý thuyết đồ thị cũng như trong thực tế phứctạp. Mong được bạn đọc góp ý thêm.

Bàn thêm về cặp ghép

Lưu Tuấn Anh

Bài toán cặp ghép là 1 bài toán rất cơ bản và cũng có rất nhiều ứng dụng trong thực tế. Trên ISM đã có rất nhiều bài viết viết về những vấn đề liên quan đến bài toán này. Bài viết của tôi chỉ xin nói thêm về 1 khía cạnh ít được đề cập đến. Đó là đếm số lượng cặp ghép.

Bài toán phát biểu như sau:

Cho N sinh viên( N<=12 ) và N vấn đề cần nghiên cứu. Mỗi sinh viên sẽ hứng thú với 1 số vấn đề, và khi sinh viên được giao vấn đề họ thích thì họ sẽ làm việc hiệu quả hơn rất nhiều. Ngài giáo sư đáng kính của chúng ta muốn biết có bao nhiêu cách ghép sao cho mỗi sinh viên sẽ giải quyết 1 vấn đề mà họ thích.

Giáo sư sẽ cung cấp cho chúng ta 1 ma trận A kích thước NxN trong file PROBLEM.TXT với
+ A[i,j]=1 khi sinh viên i thích vấn đề j.
+ A[i,j]=0 khi sinh viên i không thích vấn đề j.
Yêu cầu: Bạn hãy viết 1 chương trình tính số ghép thoả mãn yêu cầu của giáo sư và gửi file kết quả SOLVE.TXT cho giáo sư.

Ví dụ:

PROBLEM.TXT
3
1 1 1
1 1 1
1 1 0
SOLVE.TXT
4
Giải thích : 4 cặp ghép là
((1,2),(2,3),(3,1))
((1,1),(2,3),(3,2))
((1,3),(2,1),(3,2))
((1,3),(2,2),(3,1))

Bài toán trên ta có thể giải theo cách tầm thường là tìm toàn bộ cách khả năng có thể ghép bằng cách vét cạn, độ phức tạp là N!. Trong trường hợp ma trận A gồm toàn số 1, số cách chọn sẽ là N!.Dù N<=12 nhưng N! vẫn là 1 giá trị “khủng khiếp”.

Sau đây tôi xin đề xuất cách giải với thuật toán QHĐ trạng thái. Xin nói qua về QHĐ trạng thái.QHĐ trạng thái là QHĐ trên các trạng thái, các trang thái thường được biều diễn bằng 1 dãy bít hoặc tính trước.

Ví dụ 1: Bài 1 thi QG năm 2006 bảng B ( tôi không nói lại đề ) : Ta dùng QHĐ trạng thái với 8 trạng thái cho mỗi dòng : (0,0),(0,1),(0,2),(0,3),(0,4),(1,3),(1,4),(2,4) với ý nghĩa (i,j) là chọn ô i và ô j, giá trị 0 là không chọn ô nào.Ví dụ 2: Bài viết “chia sẻ 1 thuật toán hay” của bạn Nguyễn Hiển. Bạn đã dùng 1 dãy bít với ý nghĩa là bít thứ i bằng 1 nếu công việc đó được chọn, bằng 0 nếu công việc đó không được chọn.

Trở lại bài toán của chúng ta. Ta biết: 1 cách ghép cặp là cách ghép 1 sinh viên và 1 vấn đề. Giả sử ta có 1 cách ghép cặp (x1,y1),(x2,y2),…,(xn,yn). Bây giờ ta bỏ đi 1 cặp (x1,y1). Cặp ghép còn lại là (x2,y2),(x3,y3),…,(xn,yn) vẫn là 1 cặp ghép, ta có bài toán với kích thước nhỏ hơn. Như vậy các bạn đã thấy rõ bản chất QHĐ của bài toán này. Để tìm số cách ghép của N sinh viên, ta phải tìm số cách ghép của N-1 sinh viên.

Ta định nghĩa 1 dãy bít X thay cho các trạng thái của các vấn đề. X[i]=1 nếu vấn đề i được chọn. X[i]=0 nếu vấn đề i không được chọn. Độ dài dãy bít tối đa là 12 nên ta thay 1 dãy bít X bằng 1 giá trị TX.

Vì cặp ghép là đầy đủ nên số sinh viên ghép với 1 trạng thái X là số giá trị 1 trong X. Ta cố định các sinh viên này và duỵêt qua tất cả các trạng thái X. Gọi D[TX] là số cách ghép cặp 1 trạng thái X với sl sinh viên đầu tiên, sl là số bít 1 của trạng thái X. Ta có công thức QHĐ:D[TX] := D[TX]+D[TX xor (1 shl i)] với i thoả mãn X[i]=1 và có sinh viên sl thích vấn đề i.TX xor (1 shl i) có ý nghĩa là thay giá trị bít thứ i thành 0, ta đã giảm số vấn đề được chọn đi 1. Sau đây là chương trình:

{ Sử dụng Free Pascal }

Const max = 1 shl 12;
fi = 'PROBLEM.TXT';
fo = 'SOLVE.TXT';
Var n : Integer;
f ,g : text;
A : array[0..20,0..20] of Boolean;
D : array[0..max] of longInt; {Mảng D có ý nghĩa như trên }
T : array[0..20] of Integer; { T lưu lại vị trí các bít 1 để dễ dàng QHĐ hơn }

Procedure Tinh( TX : LongInt );
Var gt , j , i , sl : LongInt;
{sl là số lượng bít 1}
Begin
gt := TX;
i := -1;
sl := -1;
While gt> 0 do {vong while de tim cac bit 1 trong phan tich nhi phan so TX}
Begin
Inc( i );
If gt and 1 = 1 then {neu bít i là 1 }
Begin
Inc(sl);
T[pt]:=i; {luu lai vi tri cac bit 1}
End;
gt:= gt shr 1;
End;
D[TX]:=0;
For j :=0 to sl do
If A[ sl , T[j] ] then {Sinh viên sl thích vấn đề T[j]}
Inc( D[TX] , D[ TX xor (1 shl T[j])] );
{TX xor (1 shl T[j] là tắt bit thứ T[j]}
End;

Procedure Xuli;
Var TX:LongInt;
Begin
D[0]:=1;
For TX:=1 to (1 shl n)-1 do
Tinh(TX); {QHD voi so TX
Writeln(g, D[1 shl n-1] );
End;

Procedure Nhap;
Var i ,j,t:Integer;
Begin
Read(f,n);
For i:=0 to n-1 do
For j:=0 to n-1 do
Begin
Read(f,t);
A[i,j]:= t =1;
End;
End;

Begin

assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
fillchar(d,sizeof(d),0);
Nhap;
Xuli;
close(f);close(g);
End.

Thuật toán trên có độ phức tạp khoảng 2^N, hiệu quả hơn rất nhiều so với cách duyệt bình thường.

Bài toán trên đã giải quyết xong. Bây giờ, ta sẽ thay đổi bài toán trên 1 chút:

Vị giáo sư đáng kính muốn biết có bao nhiêu cách ghép cặp mà trong đó có chứa cặp sinh viên x và vấn đề y.,/p>

Khi ta đã giải quyết được bài toán trên thì bài toán mở rộng trở nên quá dễ.

Cặp Ghép

Lê Văn Chương

Định nghĩa cặp ghép

Xét hai tập hữu hạn X, Y gồm n phần tử:

X= {x1, x2,...,xn}

Y= {y1, y2,...,yn}

Cặp phần tử (x,y) với x thuộc X, y thuộc Y được gọi là một cặpghép. Hai cặp ghép (x,y) và (x', ý) được gọi là rời nhau nếu x # x' và 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ánxây dựng các cặp ghép được tiếp cận theo 2 hướng hoặc thỏa mãn một điều kiệnghép cặp nào đấy, khi đó người ta quan tâm đến khả năng ghép cặp tối đa, hoặclượng hoá việc ghép cặp, khi đó người ta quan tâm đến phương án ghép cặp tối ưutheo các giá trị đã lượng hoá. }

Vì số tập cặp ghép là hữu hạn, nên một phương pháp xây dựngđơn giản 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.Vì thế, phải tìm kiếm những thuật giải thật hữu hiệu, dễ cài đặt chương trìnhvà có tính khả thi cao.

Bài toán tìm cặp ghép đầy đủtối ưu

a. Giới thiệu bài toán: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 hoá việc ghép mỗi phần tử x thuộc X với một phần tử y thuộc Y,người ta đưa vào ma trận số Cij (i,j = 1, 2,..., n) với ý nghĩa Cijmô tả hiệu quả của việc ghép xi với yj. Bài toán được đặtra 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ìnhthực tế là bài toán phân công:

Bài toán phân công: Cón người và n công việc. Biết Cij là số tiền làm ra nếu giao côngviệ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ổngsố tiền làm ra là lớn nhất.

b. Định lý về cặp ghép: Việcxâ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 sosá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 thuộc X, yj thuộc 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 thoảmãn bất đẳng thức F(xi)+F(yj)>=Cij với mọixi thuộc X,yj thuộc 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 đẳngthức F(xi)+F(yj)=Cij với mọi xi thuộc X, yj thuộc Y.Nói riêng, 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ồntại nhãn F chấp nhận được là tương thích với nó.

c. 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épnào đó chưa đầy đủ (có thể là 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 thoả 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ônngữ đồ thị kèm với việc dùng thuật toán tìm đường đi.

Giả sử F là một nhãn chấp nhận được và M là tập cặp ghép tươngthí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ướnghai phía. Các cạnh của đồ thị này được xác định tuỳ thuộc nội dung của nhãn Fvà tập cặp ghép M như sau:

- Mỗi cặp phầntử xi thuộc X,yj thuộc Ythoả mãn đẳng thức F(xi)+F(yj) = Cij 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 và ngượclại.

Đồ 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 đượcnhư sau:

F(xi):=Max{Cij, yj thuộc Y} xithuộc X

F(yj):=0 yj thuộc Y

M là tập cặp ghép rỗng.

Bước 2. Tìm đỉnh tự do thuộc X:

Tìm đỉnh u thuộc Xchư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ệctì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 đượcmột đỉnh z thuộcY chưa ghép cặp thì ghi nhận đường đi từ u đến z và chuyển sang bước tăng cặpghép trên đường đi này.

- Nếu không tồntại một đường đi như vậy thì chuyển sang bước sửa nhãn F.

Bước4. Tăng cặp ghép: điều chỉnh M như sau:

- Giữ nguyênnhững cặp ghép của M nằm ngoài đường tăng cặp ghép.

- Trên đườngtăng cặp ghép, bỏ đi những cặp ghép của M là cạnh ngược và thêm vào M những cặpghép là cạnh thuận.

Sau bước này,số cặp ghép thuộc M được tăng thêm 1 và đỉnh u được bảo toàn. Sau đó quay vềbước 2 để lặp lại vởi đỉnh tự do khác.

Bước5. Sửa nhãn:

Gọi S là tậpcác đỉnh thuộc X và T là tập các đỉnh thuộc Y đã được đi đến trong quá trìnhtì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ửanhãn:

d:= min{F(xi) + F(yj)- Cij, xi thuộcS, yj thuộcT}

- Gán lại nhãn:

F(xi):=F(xi) -d với xi thuộcS

F(yj):=f(yj) +d với yj thuộcT

Sau đó, quay vềbước 3 để lặp lại việc tìm đường tăng cặp ghép.

Chú ý 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àira có thêm ít nhất một cặp (xi, yj) thoả mãn F(xi)+F(yj) = C ij, vì thế, sau một số lần sửa nhãn chắc chắnsẽ tăng được cặp ghép.

Dưới đây là sơ đồ khối mô tả các bướcthực hiện trên:

Các bạn có thể tham khảo thuật toán này quachương trình.

Chươngtrình:

Program Capghep;

Const Fi='capghep.Inp';

MaxN=100;

Var f:Text;

Total,n,i,j,u,Path:Integer;

A,B,Cg:Array[1..MaxN]Of 0..MaxInt;

Tr,Q:Array[1..2*MaxN]Of 0..2*MaxN;

S,T: Array[1..MaxN] Of 0..1;

Yetx,Yety:Array[1..MaxN]Of Boolean;

C:Array[1..MaxN,1..MaxN]Of 0..MaxInt;

Procedure ReadF;

Begin

Assign(f,Fi);

Reset(f);

Readln(f,n);

For i:=1 to n do

For j:=1 to n do Read(f,C[i,j]);

Close(f);

End;

ProcedureFindPath(u:Integer);

Var dq,cq,v:Integer;

Begin

Path:=0;

dq:=1;cq:=1;Q[1]:=u;S[u]:=1;

Tr[1]:=0;

While cq>=dq Do

Begin

v:=Q[dq];Inc(dq);

If v<=n Then

For i:=1 to n do

If (A[v]+B[i]=C[v,i])And(T[i]=0) Then

Begin

T[i]:=1;

Inc(cq);Q[cq]:=i+n;

Tr[i+n]:=v;

If Yety[i] Then Begin Path:=i+n;Exit;End;

End;

If v>n Then

Begin

v:=v-n;

For i:=1 to n do

If (B[v]+A[i]=C[i,v])And(S[i]=0) Then

Begin

S[i]:=1;

Inc(Cq);Q[Cq]:=i;

Tr[i]:=v+n;

End;

End;

End;

End;

Procedure IncCg;

Var Way,m,i,j:Integer;

Begin

m:=Path;Way:=0;

Repeat

If m>n Then j:=m-n Else i:=m;

If Way=0 Then Way:=1

Else If Way=1 Then

Begin

Way:=-1;Cg[i]:=j;

Yety[Cg[i]]:=True;

Yetx[i]:=False;Yety[j]:=False;

End Else

Begin

Way:=1;Yety[j]:=True;

End;

m:=Tr[m];

Until m=0;

End;

Procedure Change;

Var d,i,j:Integer;

Begin

d:=MaxInt;

For i:=1 to n do

If S[i]=1 Then

For j:=1 to n do

If T[j]=0 Then

If (d>A[i]+B[j]-C[i,j]) Then d:=A[i]+B[j]-C[i,j];

For i:=1 to n do

If S[i]=1 Then Dec(A[i],d);

For i:=1 to n do

If T[i]=1 Then Inc(B[i],d);

End;

Procedure Main;

Begin

ReadF;

{Enter...}

For i:=1 to n do

Begin

A[i]:=0;B[i]:=0;

For j:=1 to n do

If C[i,j]>A[i] Then A[i]:=C[i,j];

End;

FillChar(Yetx,SizeOf(Yetx),True);

FillChar(Yety,SizeOf(Yety),True);

FillChar(Cg,SizeOf(Cg),0);

Repeat

u:=0;

For i:=1 to n do

If Yetx[i] Then Begin u:=i;Break;End;

If u=0 Then Break;

FillChar(S,SizeOf(S),0);

FillChar(T,SizeOf(T),0);

FillChar(Tr,SizeOf(Tr),0);

FindPath(u);

If Path=0 Then Change Else IncCg;

Until False;

Writeln('Cap ghep :');

Total:=0;

For i:=1 to n do

Begin

Writeln('(',i,',',Cg[i],')');

Inc(Total,C[i,Cg[i]]);

End;

End;

BEGIN

Main;

END.