Chuyên đề Bài toán liệt kê

 v khỏi Queue và lại đẩy Queue những nối từ v chưa được
thăm. Như vậy nếu thăm tới một Y_đỉnh chưa ghép thì tức là ta tìm đường mở kết thúc ở Y_đỉnh
chưa ghép đó, quá trình tìm kiếm dừng ngay. Còn nếu ta thăm tới một đỉnh y ∈ Y đã ghép, dựa vào
sự kiện: từ y chỉ có thể tới được matchY[y] theo duy nhất một 0_cạnh định hướng, nên ta có thể
đánh dấu thăm y, thăm luôn cả matchY[y], và đẩy vào Queue phần tử matchY[y] ∈ X.
3. Nhập dữ liệu từ file văn bản ASSIGN.INP
• Dòng 1: Ghi hai số m, n theo thứ tự là số thợ và số việc cách nhau 1 dấu cách (m, n ≤ 100)
• Các dòng tiếp theo, mỗi dòng ghi ba số i, j, c[i, j] cách nhau 1 dấu cách thể hiện thợ i làm được
việc j và chi phí để làm là c[i, j] (1 ≤ i ≤ m; 1 ≤ j ≤ n; 0 ≤ c[i, j] ≤ 100).
]Lê Minh Hoàng^ Tập bài giảng chuyên đề Lý thuyết đồ thị ]95^
1 1
2 2
3 3
4 4
5 5
6
12
9
19
ASSIGN.INP
5 6
1 1 0
1 2 0
2 1 0
2 4 2
3 2 1
3 3 0
4 3 0
4 4 9
5 4 19
OUTPUT
Optimal assignment:
 1) X[1] - Y[1] 0
 2) X[2] - Y[4] 2
 3) X[3] - Y[2] 1
 4) X[4] - Y[3] 0
Cost: 4
X Y
PROG12_1.PAS * Thuật toán Hungari
program AssignmentProblemSolve; {Giải bài toán phân công}
const
 max = 100;
 maxC = 10001;
var
 c: array[1..max, 1..max] of Integer;
 Fx, Fy, matchX, matchY, Trace: array[1..max] of Integer;
 VisitedX, VisitedY: array[1..max] of Boolean;
 m, n, k: Integer;
procedure Enter;
var
 f: Text;
 i, j: Integer;
begin
 Assign(f, 'ASSIGN.INP'); Reset(f);
 Readln(f, m, n);
 if m > n then k := m else k := n; {k := max(m, n), coi như có k thợ, k việc}
 for i := 1 to k do
 for j := 1 to k do c[i, j] := maxC; {(i, j) nào không có trong file thì c[i, j] := maxC}
 while not SeekEof(f) do Readln(f, i, j, c[i, j]);
 Close(f);
end;
procedure Init;
var
 i, j: Integer;
begin
 FillChar(matchX, SizeOf(matchX), 0);
 FillChar(matchY, SizeOf(matchY), 0); {Khởi tạo bộ ghép ∅}
{Ta hoàn toàn có thể đặt các Fx cũng như Fy bằng 0, nhưng để hiệu quả hơn thì nên: }
 for i := 1 to k do {Trừ tất cả trọng số những cạnh liên thuộc với X[i] đi trọng số cạnh nhỏ nhất}
 begin {⇔ Đặt Fx[i] := Trọng số cạnh nhỏ nhất liên thuộc với X[i]}
 Fx[i] := maxC;
 for j := 1 to k do
 if c[i, j] < Fx[i] then Fx[i] := c[i, j];
 end;
 for j := 1 to k do {Rồi trừ tất cả trọng số những cạnh liên thuộc với Y[j] cho trọng số cạnh nhỏ nhất}
 begin {Lưu ý là trọng số cạnh (X[i], Y[j]) bây giờ là c[i, j] - Fx[i] chứ không còn là c[i, j] nữa}
 Fy[j] := maxC;
 for i := 1 to k do
 if c[i, j] - Fx[i] < Fy[j] then Fy[j] := c[i, j] - Fx[i];
 end;
end;
{Tìm đường mở xuất phát từ StartX ∈ X, nếu tìm thấy trả về Y_đỉnh kết thúc đường mở, nếu không thấy trả về 0}
]Lê Minh Hoàng^ Tập bài giảng chuyên đề Lý thuyết đồ thị ]96^
function FindAugmentingPath(StartX: Integer): Integer;
var
 Queue: array[1..max] of Integer;
 x, y, first, last: Integer;
begin
 FillChar(VisitedX, SizeOf(VisitedX), False);
 FillChar(VisitedY, SizeOf(VisitedY), False);
 Queue[1] := StartX;
 first := 1; last := 1;
 VisitedX[StartX] := True; {Duy nhất StartX đã thăm được đẩy vào Queue}
 repeat
 x := Queue[first]; Inc(first); {Lấy một đỉnh x∈X ra khỏi Queue}
 for y := 1 to k do {Xét các Y_đỉnh chưa thăm, kề với x qua một 0_cạnh chưa ghép (if viết hơi thừa cho dễ hiểu)}
 if not VisitedY[y] and (matchX[x] y) and (c[x, y] = Fx[x] + Fy[y]) then
 begin
 Trace[y] := x; {Lưu vết đường đi: đỉnh liền trước y trên đường đi StartX tới y là x}
 if matchY[y] = 0 then {nếu y chưa ghép thì tức là tìm thấy đường mở từ StartX tới y}
 begin
 FindAugmentingPath := y;
 Exit; {Ghi nhận và thoát ngay}
 end;
 VisitedY[y] := True; {Nếu y đã ghép thì đánh dấu thăm y}
 VisitedX[matchY[y]] := True; {Thăm luôn cả matchY[y]}
 Inc(last); Queue[last] := matchY[y]; {Đẩy matchY[y] vào hàng đợi}
 end;
 until first > last; {Cho tới khi hàng đợi rỗng, quá trình BFS xong}
 FindAugmentingPath := 0; {ở trên không Exit được tức là không có đường mở từ StartX}
end;
procedure SubX_AddY; {Xoay đồ thị G}
var
 x, y, Delta: Integer;
begin
 Delta := maxC; {Trước hết tính Delta := trọng số nhỏ nhất trong các cạnh nối VisitedX với Y\VisitedY}
 for x := 1 to k do
 if VisitedX[x] then
 for y := 1 to k do
 if not VisitedY[y] and (c[x, y] - Fx[x] - Fy[y] < Delta) then
 Delta := c[x, y] - Fx[x] - Fy[y];
 for x := 1 to k do {Trừ tất cả trọng số những cạnh liên thuộc với VisitedX đi Delta}
 if VisitedX[x] then Fx[x] := Fx[x] + Delta;
 for y := 1 to k do {Cộng tất cả trọng số những cạnh liên thuộc với VisitedY lên Delta}
 if VisitedY[y] then Fy[y] := Fy[y] - Delta;
end;
{Tăng cặp dựa trên đường mở kết thúc ở f∈Y}
procedure Enlarge(f: Integer);
var
 x, next: Integer;
begin
 repeat
 x := Trace[f];
 next := matchX[x];
 matchX[x] := f;
 matchY[f] := x;
 f := Next;
 until f = 0;
end;
procedure Solve; {Thuật toán Hungari}
var
 x, y: Integer;
begin
next
... ...
fx
next
... ...
fx
]Lê Minh Hoàng^ Tập bài giảng chuyên đề Lý thuyết đồ thị ]97^
 for x := 1 to k do {Xét ∀x∈X}
 begin
 repeat
 y := FindAugmentingPath(x); {Tìm đường mở xuất phát tại x}
 if y = 0 then SubX_AddY; {Nếu không tìm thấy thì xoay đồ thị}
 until y 0; {Cho tới khi tìm thấy đường mở}
 Enlarge(y); {Nới rộng bộ ghép bằng đường mở tìm được, x và y trở thành đã ghép}
 end;
end;
procedure Result;
var
 x, y, Count, W: Integer;
begin
 Writeln('Optimal assignment:');
 W := 0; Count := 0;
 for x := 1 to k do
 begin
 y := matchX[x];
{Những cạnh có trọng số maxC tương ứng với một thợ không được giao việc và một việc không được phân công}
 if c[x, y] < maxC then {Nên chỉ cần quan tâm tới những phép phân công thật sự}
 begin
 Inc(Count);
 Writeln(Count:5, ') X[', x, '] - Y[', y, '] ', c[x, y]);
 W := W + c[x, y];
 end;
 end;
 Writeln('Cost: ', W);
end;
begin
 Enter;
 Init;
 Solve;
 Result;
end.
Nhận xét:
1. Nếu cài đặt như trên thì cho dù đồ thị có cạnh mang trọng số âm, chương trình vẫn tìm được
bộ ghép cực đại với trọng số cực tiểu. Lý do: Ban đầu, ta trừ tất cả các phần tử trên mỗi hàng
của ma trận C đi giá trị nhỏ nhất trên hàng đó, rồi lại trừ tất cả các phần tử trên mỗi cột của
ma trận C đi giá trị nhỏ nhất trên cột đó (Phép trừ ở đây làm gián tiếp qua các Fx, Fy chứ
không phải trừ trực tiếp trên ma trận C). Nên sau bước này, tất cả các cạnh của đồ thị sẽ có
trọng số không âm bởi phần tử nhỏ nhất trên mỗi cột của C chắc chắn là 0.
2. Sau khi kết thúc thuật toán, tổng tất cả các phần tử ở hai dãy Fx, Fy bằng trọng số cực tiểu của
bộ ghép đầy đủ tìm được trên đồ thị ban đầu.
3. Lại tương tự như bài toán đường đi ngắn nhất, ta thêm vào đồ thị một số đỉnh giả và một số
cạnh để được đồ thị hai phía đầy đủ và giải bài toán trên đồ thị đó. Những cạnh giả thêm vào
được gán trọng số đủ lớn. Giá trị đủ lớn đó phải chọn như thế nào?, nó phải lớn hơn trọng số
của tất cả những bộ ghép có thể tạo thành từ những cạnh thật. Khi giá trị đó quá lớn thì sẽ dẫn
đến nhiều phiền toái khi tổ chức dữ liệu. Vậy ta nên có một giải pháp tốt hơn cho vấn đề này,
chẳng hạn do giả thiết cho các trọng số không âm nên ta có thể lấy một giá trị đặc biệt -1 gán
cho các cạnh giả, tại các bước phải xét cạnh, ta thêm vào phép kiểm tra để chỉ xét các cạnh
trọng số khác -1. Khi tìm đường mở xuất phát từ x, nếu không tìm thấy thì ta phải tìm giá trị
xoay ∆ là trọng số nhỏ nhất của cạnh nối một X_đỉnh trong cây pha với một Y_đỉnh ngoài cây
pha, nếu không có cạnh nối như vậy (hay nói đúng hơn là tất cả các cạnh nối X_đỉnh trong
]Lê Minh Hoàng^ Tập bài giảng chuyên đề Lý thuyết đồ thị ]98^
cây pha với một Y_đỉnh ngoài cây pha đều là cạnh trọng số -1) thì ta có thể khẳng định đỉnh x
là không thể ghép được và bỏ qua ngay để tìm cách ghép một X_đỉnh khác.
4. Một vấn đề nữa phải hết sức cẩn thận trong việc ước lượng độ lớn của các phần tử Fx và Fy.
Nếu như giả thiết cho các trọng số không quá 500 thì ta không thể dựa vào bất đẳng thức
Fx(x) + Fy(y) ≤ c(x, y) mà khẳng định các phần tử trong Fx và Fy cũng ≤ 500. Hãy tự tìm ví
dụ để hiểu rõ hơn bản chất thuật toán.
V. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TRỌNG SỐ CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA
Bài toán tìm bộ ghép cực đại với trọng số cực đại cũng có thể giải nhờ phương pháp Hungari bằng
cách đổi dấu tất cả các phần tử ma trận chi phí (Nhờ nhận xét 1).
Khi cài đặt, ta có thể sửa lại đôi chút trong chương trình trên để giải bài toán tìm bộ ghép cực đại
với trọng số cực đại mà không cần đổi dấu trọng số. Cụ thể như sau:
Bước 1: Khởi tạo:
• M := ∅;
• Khởi tạo hai dãy Fx và Fy thoả mãn: ∀i, j: Fx[i] + Fy[j] ≥ c[i, j]; Chẳng hạn ta có thể đặt
Fx[i] := Phần tử lớn nhất trên dòng i của ma trận C và đặt các Fy[j] := 0.
Bước 2: Với mọi đỉnh x*∈X, ta tìm cách ghép x* như sau:
Với cách hiểu 0_cạnh là cạnh thoả mãn c[i, j] = Fx[i] + Fy[j]. Bắt đầu từ đỉnh x*, thử tìm đường mở
bắt đầu ở x*. Có hai khả năng xảy ra:
• Hoặc tìm được đường mở thì dọc theo đường mở, ta loại bỏ những cạnh đã ghép khỏi M và
thêm vào M những cạnh chưa ghép.
• Hoặc không tìm được đường mở thì xác định được hai tập:
™ VisitedX = {Tập những X_đỉnh có thể đến được từ x* bằng một đường pha}
™ VisitedY = {Tập những Y_đỉnh có thể đến được từ x* bằng một đường pha}
™ Đặt ∆ := min{Fx[i] + Fy[j] - c[i, j]  ∀X[i] ∈ VisitedX; ∀Y[j] ∉ VisitedY}
™ Với ∀X[i] ∈ VisitedX: Fx[i] := Fx[i] - ∆;
™ Với ∀Y[j] ∈ VisitedY: Fy[j] := Fy[j] + ∆;
™ Lặp lại thủ tục tìm đường mở xuất phát tại x* cho tới khi tìm ra đường mở.
Bước 3: Sau bước 2 thì mọi X_đỉnh đều đã ghép, ta được một bộ ghép đầy đủ k cạnh với trọng số
lớn nhất.
Dễ dàng chứng minh được tính đúng đắn của phương pháp, bởi nếu ta đặt:
c'[i, j] = - c[i, j]; F'x[i] := - Fx[i]; F'y[j] = - Fy[j].
Thì bài toán trở thành tìm cặp ghép đầy đủ trọng số cực tiểu trên đồ thị hai phía với ma trận trọng số
c'[1..k, 1..k]. Bài toán này được giải quyết bằng cách tính hai dãy đối ngẫu F'x và F'y. Từ đó bằng
những biến đổi đại số cơ bản, ta có thể kiểm chứng được tính tương đương giữa các bước của
phương pháp nêu trên với các bước của phương pháp Kuhn-Munkres ở mục trước.