Thuật toán DSA Ford-Fulkerson
Thuật toán Ford-Fulkerson giải bài toán luồng cực đại.
Việc tìm kiếm luồng tối đa có thể hữu ích trong nhiều lĩnh vực: tối ưu hóa lưu lượng mạng, sản xuất, chuỗi cung ứng và hậu cần hoặc lập lịch trình hàng không.
Thuật toán Ford-Fulkerson
Thuật toán Ford-Fulkerson giải bài toán luồng cực đại cho đồ thị có hướng.
Luồng xuất phát từ đỉnh nguồn (\(s\)) và kết thúc ở đỉnh chìm (\(t\)) và mỗi cạnh trong biểu đồ cho phép một luồng, bị giới hạn bởi dung lượng.
Lưu lượng tối đa: {{maxFlow}}
{{statusText}}Thuật toán Ford-Fulkerson hoạt động bằng cách tìm kiếm một đường dẫn có dung lượng khả dụng từ nguồn đến đích (được gọi là đường dẫn tăng cường ), sau đó gửi càng nhiều luồng càng tốt qua đường dẫn đó.
Thuật toán Ford-Fulkerson tiếp tục tìm ra những đường dẫn mới để gửi nhiều luồng hơn cho đến khi đạt được luồng tối đa.
Trong mô phỏng ở trên, thuật toán Ford-Fulkerson giải quyết vấn đề luồng tối đa: Nó tìm ra lượng luồng có thể được gửi từ đỉnh nguồn \(s\), đến đỉnh đích \(t\) và luồng tối đa đó là số 8.
Các số trong mô phỏng ở trên được viết dưới dạng phân số, trong đó số đầu tiên là luồng và số thứ hai là dung lượng (luồng tối đa có thể có ở cạnh đó). Vì vậy, ví dụ: 0/7 trên cạnh \(s \rightarrow v_2\), nghĩa là có 0 luồng, với dung lượng là 7 trên cạnh đó.
Lưu ý: Thuật toán Ford-Fulkerson thường được mô tả như một phương pháp thay vì một thuật toán , bởi vì nó không chỉ định cách tìm đường dẫn mà luồng có thể tăng lên. Điều này có nghĩa là nó có thể được thực hiện theo nhiều cách khác nhau, dẫn đến độ phức tạp về thời gian khác nhau. Nhưng đối với hướng dẫn này, chúng tôi sẽ gọi nó là một thuật toán và sử dụng Tìm kiếm theo chiều sâu để tìm đường dẫn.
Bạn có thể xem mô tả cơ bản từng bước về cách hoạt động của thuật toán Ford-Fulkerson bên dưới, nhưng sau này chúng ta cần đi sâu vào chi tiết hơn để thực sự hiểu nó.
Làm thế nào nó hoạt động:
- Bắt đầu với dòng chảy bằng 0 trên tất cả các cạnh.
- Tìm một đường dẫn tăng cường để có thể gửi nhiều luồng hơn.
- Thực hiện tính toán nút cổ chai để tìm hiểu xem có thể gửi bao nhiêu luồng thông qua đường dẫn tăng cường đó.
- Tăng luồng được tìm thấy từ tính toán nút cổ chai cho mỗi cạnh trong đường dẫn tăng cường.
- Lặp lại các bước 2-4 cho đến khi tìm thấy lưu lượng tối đa. Điều này xảy ra khi không thể tìm thấy đường dẫn tăng cường mới nữa.
Mạng lưới dư ở Ford-Fulkerson
Thuật toán Ford-Fulkerson thực sự hoạt động bằng cách tạo và sử dụng một thứ gọi là mạng dư , là biểu diễn của biểu đồ gốc.
Trong mạng dư, mọi cạnh đều có dung lượng dư , là dung lượng ban đầu của cạnh, trừ đi luồng trong cạnh đó. Dung lượng dư có thể được coi là dung lượng còn sót lại ở một cạnh có dòng chảy nào đó.
Ví dụ: nếu có luồng 2 ở cạnh \( v_3 \rightarrow v_4 \) và dung lượng là 3 thì luồng dư là 1 ở cạnh đó, vì có chỗ để gửi thêm 1 đơn vị luồng qua cạnh đó bờ rìa.
Các cạnh đảo ngược ở Ford-Fulkerson
Thuật toán Ford-Fulkerson cũng sử dụng một thứ gọi là các cạnh đảo ngược để gửi luồng ngược lại. Điều này rất hữu ích để tăng tổng lưu lượng.
Ví dụ: đường dẫn tăng cường cuối cùng \(s \rightarrow v_2 \rightarrow v_4 \rightarrow v_3 \rightarrow t\) trong hoạt ảnh ở trên và trong hướng dẫn chạy qua bên dưới cho thấy tổng luồng được tăng thêm một đơn vị như thế nào, bằng cách thực sự gửi luồng ngược lại trên cạnh \( v_4 \rightarrow v_3 \), gửi luồng theo hướng ngược lại.
Gửi luồng ngược lại trên cạnh \( v_3 \rightarrow v_4 \) trong ví dụ của chúng tôi có nghĩa là 1 đơn vị luồng này đi ra khỏi đỉnh \( v_3 \), hiện rời khỏi \( v_3 \) trên cạnh \( v_3 \ rightarrow t \) thay vì \( v_3 \rightarrow v_4 \).
Để gửi luồng ngược lại, theo hướng ngược lại của cạnh, một cạnh ngược được tạo cho mỗi cạnh ban đầu trong mạng. Thuật toán Ford-Fulkerson sau đó có thể sử dụng các cạnh ngược này để gửi luồng theo hướng ngược lại.
Cạnh đảo ngược không có dòng chảy hoặc dung lượng, chỉ có dung lượng dư. Dung lượng dư của cạnh đảo ngược luôn bằng lưu lượng ở cạnh ban đầu tương ứng. Trong ví dụ của chúng tôi, cạnh \( v_3 \rightarrow v_4 \) có luồng 2, nghĩa là có dung lượng dư là 2 trên cạnh đảo ngược tương ứng \( v_4 \rightarrow v_3 \).
Điều này chỉ có nghĩa là khi có luồng 2 trên cạnh ban đầu \( v_3 \rightarrow v_4 \), thì có khả năng gửi cùng một lượng luồng đó trở lại cạnh đó, nhưng theo hướng ngược lại. Việc sử dụng cạnh đảo ngược để đẩy lùi luồng cũng có thể được coi là hoàn tác một phần của luồng đã được tạo.
Ý tưởng về mạng dư với dung lượng dư trên các cạnh và ý tưởng về các cạnh đảo ngược là trọng tâm trong cách hoạt động của thuật toán Ford-Fulkerson và chúng tôi sẽ đi sâu vào chi tiết hơn về điều này khi chúng tôi triển khai thuật toán sâu hơn trên trang này.
Chạy qua thủ công
Không có luồng nào trong biểu đồ để bắt đầu.
Để tìm luồng tối đa, thuật toán Ford-Fulkerson phải tăng luồng, nhưng trước tiên nó cần tìm ra nơi có thể tăng luồng: nó phải tìm một đường dẫn tăng cường.
Thuật toán Ford-Fulkerson thực sự không chỉ định cách tìm thấy đường dẫn tăng cường như vậy (đó là lý do tại sao nó thường được mô tả như một phương pháp thay vì thuật toán), nhưng chúng tôi sẽ sử dụng Tìm kiếm theo chiều sâu (DFS) để tìm các đường dẫn tăng cường cho Thuật toán Ford-Fulkerson trong hướng dẫn này.
Đường dẫn mở rộng đầu tiên mà Ford-Fulkerson tìm thấy khi sử dụng DFS là \(s \rightarrow v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow t\).
Và bằng cách sử dụng phép tính thắt cổ chai, Ford-Fulkerson nhận thấy rằng 3 là luồng cao nhất có thể được gửi qua đường dẫn tăng cường, do đó luồng được tăng thêm 3 cho tất cả các cạnh trong đường dẫn này.
Lần lặp tiếp theo của thuật toán Ford-Fulkerson là thực hiện lại các bước sau:
- Tìm một con đường tăng cường mới
- Tìm xem luồng trong đường dẫn đó có thể tăng lên bao nhiêu
- Tăng luồng dọc theo các cạnh trong đường dẫn đó cho phù hợp
Đường dẫn tăng cường tiếp theo được tìm thấy là \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow v_3 \rightarrow t\), bao gồm cạnh đảo ngược \(v_4 \rightarrow v_3\) , nơi luồng được gửi trở lại.
Khái niệm Ford-Fulkerson về các cạnh đảo ngược rất hữu ích vì nó cho phép phần tìm đường đi của thuật toán tìm đường dẫn tăng cường trong đó các cạnh đảo ngược cũng có thể được đưa vào.
Trong trường hợp cụ thể này, điều đó có nghĩa là luồng 2 có thể được gửi trở lại cạnh \(v_3 \rightarrow v_4\), thay vào đó sẽ đi vào \(v_3 \rightarrow t\).
Luồng chỉ có thể tăng thêm 2 trong đường dẫn này vì đó là dung lượng ở cạnh \( v_3 \rightarrow t \).
Đường dẫn mở rộng tiếp theo được tìm thấy là \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\).
Lưu lượng có thể tăng thêm 2 trong đường dẫn này. Nút cổ chai (cạnh giới hạn) là \( v_1 \rightarrow v_4 \) vì chỉ còn chỗ để gửi thêm hai đơn vị luồng ở cạnh đó.
Đường dẫn tăng cường tiếp theo và cuối cùng là \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\).
Luồng chỉ có thể tăng thêm 1 trong đường dẫn này do cạnh \( v_4 \rightarrow t \) là nút cổ chai trong đường dẫn này chỉ có không gian cho thêm một đơn vị luồng (\(capacity-flow=1\)).
Tại thời điểm này, không thể tìm thấy đường dẫn tăng cường mới (không thể tìm thấy đường dẫn có thể gửi nhiều luồng hơn từ \(s\) đến \(t\)), có nghĩa là luồng tối đa đã được tìm thấy, và thuật toán Ford-Fulkerson đã hoàn thành.
Luồng tối đa là 8. Như bạn có thể thấy trong hình trên, luồng (8) đi ra khỏi đỉnh nguồn \(s\), giống như luồng đi vào đỉnh đích \(t\).
Ngoài ra, nếu bạn lấy bất kỳ đỉnh nào khác ngoài \(s\) hoặc \(t\), bạn có thể thấy rằng lượng dòng chảy đi vào một đỉnh cũng giống như lượng dòng chảy đi ra khỏi đỉnh đó. Đây là cái mà chúng ta gọi là bảo toàn luồng và điều này phải đúng cho tất cả các mạng luồng như vậy (đồ thị có hướng trong đó mỗi cạnh có một luồng và dung lượng).
Triển khai thuật toán Ford-Fulkerson
Để triển khai thuật toán Ford-Fulkerson, chúng tôi tạo một lớp Graph . Graph biểu thị đồ thị với các đỉnh và cạnh của nó:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, c):
self.adj_matrix[u][v] = c
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data Dòng 3: Chúng ta tạo adj_matrix để chứa tất cả các cạnh và dung lượng của cạnh. Giá trị ban đầu được đặt thành 0 .
Dòng 4: size là số đỉnh của đồ thị.
Dòng 5: vertex_data chứa tên của tất cả các đỉnh.
Dòng 7-8: Phương thức add_edge được sử dụng để thêm một cạnh từ đỉnh u đến đỉnh v , với dung lượng c .
Dòng 10-12: Phương thức add_vertex_data được sử dụng để thêm tên đỉnh vào biểu đồ. Chỉ mục của đỉnh được đưa ra cùng với đối vertex và data là tên của đỉnh.
Lớp Graph cũng chứa phương thức dfs để tìm các đường dẫn mở rộng, sử dụng Depth-First-Search:
def dfs(self, s, t, visited=None, path=None):
if visited is None:
visited = [False] * self.size
if path is None:
path = []
visited[s] = True
path.append(s)
if s == t:
return path
for ind, val in enumerate(self.adj_matrix[s]):
if not visited[ind] and val > 0:
result_path = self.dfs(ind, t, visited, path.copy())
if result_path:
return result_path
return None Dòng 15-18: Mảng visited giúp tránh việc xem lại các đỉnh giống nhau trong quá trình tìm kiếm đường dẫn tăng cường. Các đỉnh thuộc đường dẫn tăng cường được lưu trữ trong mảng path .
Dòng 20-21: Đỉnh hiện tại được đánh dấu là đã ghé thăm và sau đó được thêm vào đường dẫn.
Dòng 23-24: Nếu đỉnh hiện tại là nút đích, chúng ta đã tìm thấy một đường dẫn tăng cường từ đỉnh nguồn đến đỉnh đích, do đó đường dẫn đó có thể được trả về.
Dòng 26-30: Lặp qua tất cả các cạnh trong ma trận kề bắt đầu từ đỉnh hiện tại s , ind đại diện cho một nút liền kề và val là dung lượng còn lại trên cạnh tới đỉnh đó. Nếu đỉnh liền kề không được thăm và còn dung lượng dư trên cạnh của nó, hãy đi tới nút đó và tiếp tục tìm kiếm đường đi từ đỉnh đó.
Dòng 32: None trả về giá trị nào nếu không tìm thấy đường dẫn.
Phương thức fordFulkerson là phương thức cuối cùng chúng ta thêm vào lớp Graph :
def fordFulkerson(self, source, sink):
max_flow = 0
path = self.dfs(source, sink)
while path:
path_flow = float("Inf")
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
path_flow = min(path_flow, self.adj_matrix[u][v])
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
max_flow += path_flow
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
path = self.dfs(source, sink)
return max_flow Ban đầu, max_flow là 0 và vòng lặp while tiếp tục tăng max_flow miễn là có đường dẫn tăng cường để tăng lưu lượng vào.
Dòng 37: Đã tìm thấy đường dẫn tăng cường.
Dòng 39-42: Mỗi cạnh trong đường dẫn tăng cường được kiểm tra để tìm ra lượng luồng có thể được gửi qua đường dẫn đó.
Dòng 44-46: Dung lượng dư (dung lượng trừ lưu lượng) cho mỗi cạnh phía trước bị giảm do lưu lượng tăng lên.
Dòng 47: Dòng này thể hiện cạnh đảo ngược, được sử dụng bởi thuật toán Ford-Fulkerson để luồng có thể được gửi trở lại (hoàn tác) trên các cạnh chuyển tiếp ban đầu. Điều quan trọng là phải hiểu rằng các cạnh đảo ngược này không có trong biểu đồ gốc, chúng là các cạnh hư cấu được Ford-Fulkerson giới thiệu để làm cho thuật toán hoạt động.
Dòng 49: Mỗi khi luồng tăng lên trên một đường dẫn tăng cường, max_flow được tăng cùng một giá trị.
Dòng 51-52: Dòng này chỉ để in đường dẫn tăng cường trước khi thuật toán bắt đầu lần lặp tiếp theo.
Sau khi xác định lớp Graph , các đỉnh và cạnh phải được xác định để khởi tạo biểu đồ cụ thể và mã hoàn chỉnh cho ví dụ về thuật toán Ford-Fulkerson trông như thế này:
Ví dụ
Trăn:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, c):
self.adj_matrix[u][v] = c
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dfs(self, s, t, visited=None, path=None):
if visited is None:
visited = [False] * self.size
if path is None:
path = []
visited[s] = True
path.append(s)
if s == t:
return path
for ind, val in enumerate(self.adj_matrix[s]):
if not visited[ind] and val > 0:
result_path = self.dfs(ind, t, visited, path.copy())
if result_path:
return result_path
return None
def fordFulkerson(self, source, sink):
max_flow = 0
path = self.dfs(source, sink)
while path:
path_flow = float("Inf")
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
path_flow = min(path_flow, self.adj_matrix[u][v])
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
max_flow += path_flow
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
path = self.dfs(source, sink)
return max_flow
g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
g.add_vertex_data(i, name)
g.add_edge(0, 1, 3) # s -> v1, cap: 3
g.add_edge(0, 2, 7) # s -> v2, cap: 7
g.add_edge(1, 3, 3) # v1 -> v3, cap: 3
g.add_edge(1, 4, 4) # v1 -> v4, cap: 4
g.add_edge(2, 1, 5) # v2 -> v1, cap: 5
g.add_edge(2, 4, 3) # v2 -> v4, cap: 3
g.add_edge(3, 4, 3) # v3 -> v4, cap: 3
g.add_edge(3, 5, 2) # v3 -> t, cap: 2
g.add_edge(4, 5, 6) # v4 -> t, cap: 6
source = 0; sink = 5
print("The maximum possible flow is %d " % g.fordFulkerson(source, sink)) Chạy ví dụ »Độ phức tạp thời gian của thuật toán Ford-Fulkerson
Độ phức tạp về thời gian của Ford-Fulkerson thay đổi theo số đỉnh \(V\), số cạnh \(E\) và nó thực tế cũng thay đổi theo luồng tối đa \(f\) trong biểu đồ.
Lý do tại sao độ phức tạp thời gian thay đổi theo luồng tối đa \(f\) trong biểu đồ là vì trong biểu đồ có thông lượng cao, sẽ có nhiều đường dẫn tăng cường hơn làm tăng lưu lượng và điều đó có nghĩa là phương pháp DFS tìm thấy những đường dẫn tăng cường này path sẽ phải chạy nhiều lần hơn.
Tìm kiếm theo chiều sâu (DFS) có độ phức tạp về thời gian \(O(V+E)\).
DFS chạy một lần cho mỗi đường dẫn tăng cường mới. Nếu chúng tôi giả định rằng mỗi biểu đồ tăng cường tăng luồng thêm 1 đơn vị thì DFS phải chạy \(f\) lần, gấp nhiều lần giá trị của luồng tối đa.
Điều này có nghĩa là độ phức tạp về thời gian đối với thuật toán Ford-Fulkerson, sử dụng DFS, là
\[ O( (V+E) \cdot f ) \]
Đối với các đồ thị dày đặc , trong đó \( E > V \), độ phức tạp về thời gian cho DFS có thể được đơn giản hóa thành \(O(E)\), điều đó có nghĩa là độ phức tạp về thời gian của thuật toán Ford-Fulkerson cũng có thể được đơn giản hóa thành
\[ O( E \cdot f ) \]
Đồ thị dày đặc không có định nghĩa chính xác nhưng nó là đồ thị có nhiều cạnh.
Thuật toán tiếp theo mà chúng tôi sẽ mô tả để tìm luồng cực đại là thuật toán Edmonds-Karp .
Thuật toán Edmonds-Karp rất giống với Ford-Fulkerson, nhưng nó sử dụng BFS thay vì DFS để tìm các đường dẫn tăng cường, dẫn đến ít lần lặp hơn để tìm luồng tối đa.
