Thuật toán Ford-Fulkerson

Bách khoa toàn thư mở Wikipedia

Thuật toán Ford- Fulkerson (đặt theo L. R. Ford và D. R. Fulkerson) tính toán luồng cực đại trong một mạng vận tải. Tên Ford-Fulkerson cũng thường được sử dụng cho thuật toán Edmonds-Karp, một trường hợp đặc biệt của thuật toán Ford-Fulkerson.

Ý tưởng đằng sau thuật toán rất đơn giản: miễn là tồn tại một đường đi từ nguồn (nút bắt đầu) đến điểm xả (nút cuối), với điều kiện tất cả các cung trên đường đi đó vẫn còn khả năng thông qua, thì ta sẽ gửi đi một luồng dọc theo đường đi đó. Sau đó chúng ta tìm một đường đi khác, và tiếp tục như vậy. Một đường đi còn khả năng thông qua là một đường đi có khả năng mở rộng thêm hay một đường đi mà luồng qua đó còn khả năng tăng thêm - gọi tắt là đường tăng.

[sửa] Thuật toán

Cho một đồ thị $G (V, E)$ , với các khả năng thông qua $c (u, v)$ và luồng $f (u, v) = 0$ trên các cung từ $u$ đến $v$ , ta muốn tìm luồng cực đại từ đầu nguồn $s$ đến điểm thoát $t$ . Sau mỗi bước, các điều kiện sau đây được duy trì:

$\ f(u,v) \leq c(u,v)$ . Luồng từ $u$ tới $v$ không vượt quá khả năng thông qua.
$\ f(u,v) = - f(v,u)$ . Ta duy trì cân bằng luồng.
$\ \sum_v f(u,v) = 0$ cho tất cả các nút ngoại trừ $s$ và $t$ . Lượng dòng chảy vào một nút bằng lượng chảy ra khỏi một nút.

Điều này có nghĩa là một luồng đi qua một mạng là một luồng hợp lệ sau mỗi vòng của thuật toán. Chúng ta định nghĩa mạng còn dư $G f (V, E f)$ là mạng với sức chứa $c f (u, v) = c (u, v) - f (u, v)$ và luồng bằng không. Chú ý rằng không chắc chắn là $E = E f$ , bởi vì việc gửi luồng theo cung $u, v$ có thể làm ngắt $u, v$ (làm nó bão hòa), nhưng lại mở một cung mới $v, u$ trong mạng còn dư.

Đầu vào: Đồ thị G với khả năng thông qua c, một nút nguồn s, và một nút thoát t

Kết quả: Luồng f sao cho f là cực đại từ s đến t

$f(u,v) \leftarrow 0$ trên tất cả các cung $u, v$
Trong khi còn có một đường đi từ s đến t trong G_f:
1. Tìm một đường đi $u_1, u_2, \dots, u_k$ với $u 1 = s$ và $u k = t$ , sao cho $c f (u i, u i + 1) > 0$
2. Tìm $m = min(c f (u i, u i + 1))$
3. $f(u_i,u_{i+1}) \leftarrow f(u_i,u_{i+1}) + m$ (gửi luồng dọc theo đường đi)
4. $f(u_{i+1},u_i) \leftarrow f(u_{i+1},u_i) - m$ (luồng có thể "quay lại" sau)

Có thể tìm đường đi trong $G f (V, E f)$ bằng các phương pháp chẳng hạn như tìm kiếm theo chiều rộng (breadth-first-search) hoặc tìm kiếm theo chiều sâu (depth-first-search). Nếu sử dụng cách thứ nhất, thuật toán sẽ được gọi là Edmonds-Karp.

[sửa] Độ phức tạp

Bằng cách thêm luồng trên đường tăng vào luồng đã được thiết lập trên đồ thị, ta sẽ đạt đến luồng cực đại khi trên đồ thị không còn tìm được thêm đường tăng luồng nào nữa. Tuy nhiên, không chắc chắn là tình huống này sẽ đạt được, do vậy điều tốt nhất có thể được đảm bảo là: nếu thuật toán kết thúc thì kết quả sẽ là lời giải đúng. Trong trong trường hợp thuật toán chạy vô hạn, luồng có thể không hội tụ về phía luồng cực đại. Tuy nhiên, tình huống này chỉ xảy ra với luồng có giá trị vô tỷ. Khi khả năng thông qua là các số tự nhiên, thời gian chạy của thuật toán Ford-Fulkerson bị chặn bởi O(E*f), trong đó E là số cung của đồ thị và f là luồng cực đại trên đồ thị. Điều này là bởi vì mỗi đường tăng được tìm ra trong trong thời gian O(E) và nó làm tăng luồng với một lượng có giá trị nguyên không nhỏ hơn 1.

Một biến thể của thuật toán Ford-Fulkerson bảo đảm sự kết thúc và thời gian chạy không phụ thuộc vào giá trị luồng cực đại là thuật toán Edmonds-Karp, chạy trong thời gian O(VE²).

[sửa] Ví dụ

Ví dụ sau đây cho thấy những bước ban đầu của thuật toán Ford-Fulkerson trong một mạng vận tải gồm 4 nút, nguồn A và thoát D. Các đường đi tăng được tìm bằng phương pháp tìm kiếm theo chiều sâu, trong đó các đỉnh lân cận được duyệt theo thứ tự bảng chữ cái. Ví dụ này cho thấy biểu hiện của trường hợp xấu nhất của thuật toán. Mỗi bước chỉ gửi thêm được một luồng giá trị 1 qua mạng. Nếu sử dụng phép tìm theo chiều rộng thay vì theo chiều sâu, ta sẽ chỉ cần hai bước.

Đường đi	Khả năng thông qua	Mạng đạt được
	Mạng vận tải ban đầu
$A, B, C, D$	$min(c f (A, B), c f (B, C), c f (C, D)) =$ $min(c (A, B) - f (A, B), c (B, C) - f (B, C), c (C, D) - f (C, D)) =$ $min(1000 - 0,1 - 0,1000 - 0) = 1$
$A, C, B, D$	$min(c f (A, C), c f (C, B), c f (B, D)) =$ $min(c (A, C) - f (A, C), c (C, B) - f (C, B), c (B, D) - f (B, D)) =$ $min(1000 - 0,0 - ( - 1),1000 - 0) = 1$
	$\dots$
	Mạng vận tải cuối cùng

Chú ý khi luồng bị "đẩy ngược" từ C đến B khi tìm được đường đi A,C,B,D.

[sửa] Tham khảo

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 26.2: The Ford-Fulkerson method, pp.651–664.