Bài giảng Giải thuật và lập trình

Trường hợp 4: v đã thăm, là đỉnh đậm và b[u] ≠ b[v] 
1 2x
T:1
3
S:2
4
6
8
T:3 S:4
S:6T:3
5
7
1 2x
T:1
3
S:2
4
6
8
T:3
S:5
T:7
S:4
T:5
S:6
T:3
S:7
5
7
a
⇒ Phát hiện Blossom, tìm đỉnh cơ sở a = 3, gán lại nhãn S và T dọc chu trình pha. Đẩy hai đỉnh 
đậm mới 4, 6 vào hàng đợi, Tại những bước sau, khi duyệt tới đỉnh 6, sẽ tìm thấy đường mở kết 
thúc ở 8, truy vết theo nhãn S và T tìm được đường (1, 2, 3, 4, 5, 7, 6, 8) 
Tư tưởng chính của phương pháp Lawler là dùng các nhãn b[v] thay cho thao tác chập trực tiếp 
Blossom, dùng các nhãn S và T để truy vết tìm đường mở, tránh thao tác nở Blossom. Phương pháp 
này dựa trên một nhận xét: Mỗi khi tìm ra đường mở, nếu đường mở đó xuyên qua một Blossom 
ngoài nhất thì chắc chắn nó phải đi vào Blossom này từ nút cơ sở và thoát ra khỏi Blossom bằng 
một cạnh nhạt. 
13.4. CÀI ĐẶT 
Ta sẽ cài đặt phương pháp Lawler với khuôn dạng Input/Output như sau: 
Chuyên đề 
Đại học Sư phạm Hà Nội, 1999-2002 
] 296 ^
Input: file văn bản GMATCH.INP 
• Dòng 1: Chứa hai số n, m lần lượt là số cạnh và số đỉnh của đồ thị cách nhau ít nhất một dấu 
cách (n ≤ 100) 
• m dòng tiếp theo, mỗi dòng chứa hai số u, v tượng trưng cho một cạnh (u, v) của đồ thị 
Output: file văn bản GMATCH.OUT, ghi bộ ghép cực đại tìm được 
1 2
5
4
6
3
9
7 8
10 
GMATCH.INP 
10 11 
1 2 
1 6 
2 4 
2 8 
3 4 
3 6 
5 6 
5 9 
5 10 
7 8 
7 9 
GMATCH.OUT 
1) 1 6 
2) 2 8 
3) 3 4 
4) 5 10 
5) 7 9 
Chương trình này sửa đổi một chút mô hình cài đặt trên dựa vào nhận xét: 
v là một đỉnh đậm ⇔ v = x hoặc match[v] là một đỉnh nhạt 
Nếu v là đỉnh đậm thì S[v] = match[v] 
Vậy thì ta không cần phải sử dụng riêng một mảng nhãn S[v], tại mỗi bước sửa vết, ta chỉ cần sửa 
nhãn vết T[v] mà thôi. Để kiểm tra một đỉnh v ≠ x có phải đỉnh đậm hay không, ta có thể kiểm tra 
bằng điều kiện: match[v] có là đỉnh nhạt hay không, hay T[match[v]] có khác 0 hay không. 
Chương trình sử dụng các biến với vai trò như sau: 
match[v] là đỉnh ghép với đỉnh v 
b[v] là đỉnh cơ sở của Blossom chứa v 
T[v] là đỉnh liền trước v trên đường pha từ đỉnh xuất phát tới v kết thúc bằng cạnh nhạt, T[v] = 0 
nếu quá trình BFS chưa xét tới đỉnh nhạt v. 
InQueue[v] là biến Boolean, InQueue[v] = True ⇔ v là đỉnh đậm đã được đẩy vào Queue để chờ 
duyệt. 
start và finish: Nơi bắt đầu và kết thúc đường mở. 
P_4_13_1.PAS * Phương pháp Lawler áp dụng cho thuật toán Edmonds 
program MatchingInGeneralGraph; 
const 
 InputFile = 'GMATCH.INP'; 
 OutputFile = 'GMATCH.OUT'; 
 max = 100; 
var 
 a: array[1..max, 1..max] of Boolean; 
 match, Queue, b, T: array[1..max] of Integer; 
 InQueue: array[1..max] of Boolean; 
 n, first, last, start, finish: Integer; 
procedure Enter; 
var 
Các thuật toán trên đồ thị 
Lê Minh Hoàng 
] 297 ^
 i, m, u, v: Integer; 
 f: Text; 
begin 
 Assign(f, InputFile); Reset(f); 
 FillChar(a, SizeOf(a), False); 
 ReadLn(f, n, m); 
 for i := 1 to m do 
 begin 
 ReadLn(f, u, v); 
 a[u, v] := True; 
 a[v, u] := True; 
 end; 
 Close(f); 
end; 
procedure Init; {Khởi tạo bộ ghép rỗng} 
begin 
 FillChar(match, SizeOf(match), 0); 
end; 
procedure InitBFS; {Thủ tục này được gọi để khởi tạo trước khi tìm đường mở xuất phát từ start} 
var 
 i: Integer; 
begin 
 {Hàng đợi chỉ gồm một đỉnh đậm start} 
 first := 1; last := 1; 
 Queue[1] := start; 
 FillChar(InQueue, SizeOf(InQueue), False); 
 InQueue[start] := True; 
 {Các nhãn T được khởi gán = 0} 
 FillChar(T, SizeOF(T), 0); 
 {Nút cơ sở của outermost blossom chứa i chính là i} 
 for i := 1 to n do b[i] := i; 
 finish := 0; {finish = 0 nghĩa là chưa tìm thấy đường mở} 
end; 
procedure Push(v: Integer); {Đẩy một đỉnh đậm v vào hàng đơi} 
begin 
 Inc(last); 
 Queue[last] := v; 
 InQueue[v] := True; 
end; 
function Pop: Integer; {Lấy một đỉnh đậm khỏi hàng đợi, trả về trong kết quả hàm} 
begin 
 Pop := Queue[first]; 
 Inc(first); 
end; 
{Khó nhất của phương pháp Lawler là thủ tục này: Thủ tục xử lý khi gặp cạnh nhạt nối hai đỉnh đậm p, q} 
procedure BlossomShrink(p, q: Integer); 
var 
 i, NewBase: Integer; 
 Mark: array[1..max] of Boolean; 
 {Thủ tục tìm nút cơ sở bằng cách truy vết ngược theo đường pha từ p và q} 
 function FindCommonAncestor(p, q: Integer): Integer; 
 var 
 InPath: array[1..max] of Boolean; 
 begin 
 FillChar(InPath, SizeOf(Inpath), False); 
 repeat {Truy vết từ p} 
 p := b[p]; {Nhảy tới nút cơ sở của Blossom chứa p, phép nhảy này để tăng tốc độ truy vết} 
 Inpath[p] := True; {Đánh dấu nút đó} 
Chuyên đề 
Đại học Sư phạm Hà Nội, 1999-2002 
] 298 ^
 if p = start then Break; {Nếu đã truy về đến nơi xuất phát thì dừng} 
 p := T[match[p]]; {Nếu chưa về đến start thì truy lùi tiếp hai bước, theo cạnh đậm rồi theo cạnh nhạt} 
 until False; 
 repeat {Truy vết từ q, tương tự như đối với p} 
 q := b[q]; 
 if InPath[q] then Break; {Tuy nhiên nếu chạm vào đường pha của p thì dừng ngay} 
 q := T[match[q]]; 
 until False; 
 FindCommonAncestor := q; {Ghi nhận đỉnh cơ sở mới} 
 end; 
 procedure ResetTrace(x: Integer); {Gán lại nhãn vết dọc trên đường pha từ start tới x} 
 var 
 u, v: Integer; 
 begin 
 v := x; 
 while b[v] NewBase do {Truy vết đường pha từ start tới đỉnh đậm x} 
 begin 
 u := match[v]; 
 Mark[b[v]] := True; {Đánh dấu nhãn blossom của các đỉnh trên đường đi} 
 Mark[b[u]] := True; 
 v := T[u]; 
 if b[v] NewBase then T[v] := u; {Chỉ đặt lại vết T[v] nếu b[v] không phải nút cơ sở mới} 
 end; 
 end; 
begin {BlossomShrink} 
 FillChar(Mark, SizeOf(Mark), False); {Tất cả các nhãn b[v] đều chưa bị đánh dấu} 
 NewBase := FindCommonAncestor(p, q); {xác định nút cơ sở} 
 {Gán lại nhãn} 
 ResetTrace(p); ResetTrace(q); 
 if b[p] NewBase then T[p] := q; 
 if b[q] NewBase then T[q] := p; 
 {Chập blossom ⇔ gán lại các nhãn b[i] nếu blossom b[i] bị đánh dấu} 
 for i := 1 to n do 
 if Mark[b[i]] then b[i] := NewBase; 
 {Xét những đỉnh đậm i chưa được đưa vào Queue nằm trong Blossom mới, đẩy i và Queue để chờ duyệt tiếp tại các bước sau} 
 for i := 1 to n do 
 if not InQueue[i] and (b[i] = NewBase) then 
 Push(i); 
end; 
{Thủ tục tìm đường mở} 
procedure FindAugmentingPath; 
var 
 u, v: Integer; 
begin 
 InitBFS; {Khởi tạo} 
 repeat {BFS} 
 u := Pop; 
 {Xét những đỉnh v chưa duyệt, kề với u, không nằm cùng Blossom với u, dĩ nhiên T[v] = 0 thì (u, v) là cạnh nhạt rồi} 
 for v := 1 to n do 
 if (T[v] = 0) and (a[u, v]) and (b[u] b[v]) then 
 begin 
 if match[v] = 0 then {Nếu v chưa ghép thì ghi nhận đỉnh kết thúc đường mở và thoát ngay} 
 begin 
 T[v] := u; 
 finish := v; 
 Exit; 
 end; 
 {Nếu v là đỉnh đậm thì gán lại vết, chập Blossom …} 
 if (v = start) or (T[match[v]] 0) then 
 BlossomShrink(u, v) 
 else {Nếu không thì ghi vết đường đi, thăm v, thăm luôn cả match[v] và đẩy tiếp match[v] vào Queue} 
Các thuật toán trên đồ thị 
Lê Minh Hoàng 
] 299 ^
 begin 
 T[v] := u; 
 Push(match[v]); 
 end; 
 end; 
 until first > last; 
end; 
procedure Enlarge; {Nới rộng bộ ghép bởi đường mở bắt đầu từ start, kết thúc ở finish} 
var 
 v, next: Integer; 
begin 
 repeat 
 v := T[finish]; 
 next := match[v]; 
 match[v] := finish; 
 match[finish] := v; 
 finish := next; 
 until finish = 0; 
end; 
procedure Solve; {Thuật toán Edmonds} 
var 
 u: Integer; 
begin 
 for u := 1 to n do 
 if match[u] = 0 then 
 begin 
 start := u; {Với mỗi đỉnh chưa ghép start} 
 FindAugmentingPath; {Tìm đường mở bắt đầu từ start} 
 if finish 0 then Enlarge; {Nếu thấy thì nới rộng bộ ghép theo đường mở này} 
 end; 
end; 
procedure Result; {In bộ ghép tìm được} 
var 
 u, count: Integer; 
 f: Text; 
begin 
 Assign(f, OutputFile); Rewrite(f); 
 count := 0; 
 for u := 1 to n do 
 if match[u] > u then {Vừa tránh sự trùng lặp (u, v) và (v, u), vừa loại những đỉnh không ghép được (match=0)} 
 begin 
 Inc(count); 
 WriteLn(f, count, ') ', u, ' ', match[u]); 
 end; 
 Close(f); 
end; 
begin 
 Enter; 
 Init; 
 Solve; 
 Result; 
end. 
13.5. ĐỘ PHỨC TẠP TÍNH TOÁN 
Thủ tục BlossomShrink có độ phức tạp O(n). Thủ tục FindAugmentingPath cần không quá n lần gọi 
thủ tục BlossomShrink, cộng thêm chi phí của thuật toán tìm kiếm theo chiều rộng, có độ phức tạp 
Chuyên đề 
Đại học Sư phạm Hà Nội, 1999-2002 
] 300 ^
O(n2). Phương pháp Lawler cần không quá n lần gọi thủ tục FindAugmentingPath nên có độ phức 
tạp tính toán là O(n3). 
Cho đến nay, phương pháp tốt nhất để giải bài toán tìm bộ ghép tổng quát trên đồ thị được biết đến 
là của Micali và Varizani (1980), nó có độ phức tạp tính toán là )m.n(O . Bạn có thể tham khảo 
trong các tài liệu khác. 
TÀI LIỆU ĐỌC THÊM 
[1] Christian Charras, Thierry Lecroq. Handbook of Exact String-Matching Algorithms. 
Gần 20 thuật toán tìm kiếm chuỗi, có diễn giải đầy đủ. 
[2] Reinhard Diestel. Graph Theory. Một cuốn sách chuyên về Lý thuyết đồ thị. 
[3] Johan Håstad. Advanced Algorithms. 
[4] Andrew J. Manson. Speaker Matching. Bài báo nói về các thuật toán tìm bộ ghép trên 
đồ thị tổng quát, cả trong trường hợp đồ thị có trọng số 
[5] Eva Milková. Graph Theory and Information Technology. Một số thuật toán về bài 
toán cây bao trùm tối tiểu. 
[6] Dave Mount. Design and Analysis of Computer Algorithms. 
[7] Nguyễn Xuân My, Trần Đỗ Hùng, Lê Sĩ Quang. Một số vấn đề chọn lọc trong tin học. 
Cuốn sách rất phù hợp cho học sinh phổ thông trung học yêu thích việc giải các bài toán 
tin học 
[8] Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán rời rạc. Một cuốn sách rất căn bản dành 
cho sinh viên ngành tin học. 
[9] Kenneth H. Rosen. Discrete Mathematics and its Applications (Bản dịch tiếng Việt: 
Toán học rời rạc ứng dụng trong tin học). Cuốn sách viết dưới dạng giáo trình rất dễ 
hiểu, có hệ thống bài tập được sắp xếp rất khoa học. 
[10] Robert Sedgewick. Algorithms (Bản dịch tiếng Việt: Cẩm Nang Thuật Toán). Một 
cuốn sách rất tiện lợi cho tra cứu, đầy đủ các thuật toán kinh điển 
In memory of committed teachers and excellent students. 
Le Minh Hoang.