Chính xác thì đường dẫn tăng thêm là gì?

Question

Khi nói về computing network flows, các Algorithm Design Manual nói:

truyền thống thuật toán dòng chảy mạng được dựa trên ý tưởng của đường làm tăng, và lặp đi lặp lại việc tìm kiếm một con đường công suất tích cực từ s đến t và thêm nó vào dòng chảy . Có thể thấy rằng luồng thông qua mạng là tối ưu nếu và chỉ khi nó không chứa đường dẫn tăng thêm.

Tôi không hiểu augmenting paths là gì. Tôi có googled, và thấy:

• Augmenting Path in Wolfram

• Flow network in Wiki

nhưng tất cả họ đều tham chiếu đến các báo ở trên.

Có ai vui lòng giải thích rõ ràng số augmenting path là gì?

Answer 1

Đường dẫn tăng thêm là đường dẫn đơn giản - đường dẫn không chứa chu kỳ - thông qua biểu đồ chỉ sử dụng các cạnh có công suất dương từ nguồn đến bồn rửa.

Vì vậy, tuyên bố ở trên bằng cách nào đó hiển nhiên - nếu bạn không thể tìm thấy đường dẫn từ nguồn đến bồn rửa chỉ sử dụng các cạnh dung lượng tích cực thì luồng không thể tăng lên.

Bằng cách này, bằng chứng của tuyên bố đó không phải là dễ dàng.

Answer 2

Tăng tốc có nghĩa là tăng lớn hơn. Trong một mạng luồng nhất định G=(V,E) và luồng f đường dẫn tăng thêm p là một đường dẫn đơn giản từ source s đến sink t trong mạng còn lại Gf. Theo định nghĩa của residual network, chúng tôi có thể tăng lưu lượng trên một cạnh (u,v) của đường tăng thêm lên đến công suất Cf(u,v) mà không vi phạm ràng buộc, tùy theo số (u,v) và (v,u) nằm trong mạng luồng ban đầu G. Ngoài ra số tiền tối đa mà chúng tôi có thể tăng lưu lượng trên mỗi cạnh trong đường dẫn tăng cường p được gọi là residual capacity of p. Bằng chứng có thể được tìm thấy trong phần giới thiệu các thuật toán của thomas h. cormen vv ...

Answer 3

Và làm thế nào để bạn tìm ra đường dẫn tăng thêm từ nguồn đến bồn rửa? Sử dụng phiên bản BFS đã sửa đổi. Bạn làm BFS từ nguồn cho đến khi bạn đạt đến bồn rửa và bạn đi qua một cạnh chỉ khi nó có dung lượng dư (tức là đối với cạnh đó, dung lượng tối đa của nó - dòng chảy hiện tại> 0). Và đối với con đường này từ nguồn đến bồn rửa, bạn duy trì công suất dư tối thiểu, đó là lưu lượng tối đa bạn có thể đi qua con đường đó. Đoạn mã cấp cao để có ý tưởng:

bool maxFlowAchieved = false; 
int maxFlow = 0; // keeps track of what is the max flow in the network 
while(!maxFlowAchieved) 
{ 
    //BFS returns collection of Edges in the traversal order from source to sink 
    std::vector<Edge*> path = BFS(source, sink); 
    maxFlowAchieved = path.size() == 0; // all paths exhausted 
    if(maxFlowAchieved) 
     break; 
    // traverse each edge in the path and find minimum residual capacity 
    // edge->residual = edge->maxCapacity - edge->currentflow 
    int allowedFlow = GetMinResidualOnPath(path); 
    // Now add additional flow to each edge in the path. 
    // i.e. for each edge in path, edge->currentflow += allowedFlow 
    // clearly, edge->currentflow + allowedFlow <= edge->maxCapacity 
    SaturatePath(path, allowedFlow); 
    maxFlow += allowedFlow; 
} 

return maxFlow; 

Answer 4

Quy trình tìm luồng từ nguồn đến bồn rửa theo chu kỳ. Ví dụ, trong trường hợp của thuật toán Ford-Fulkerson, ban đầu tất cả các luồng trên tất cả các cạnh là Zero. Khi lặp lại, chúng tôi lấy các giá trị cho mỗi đường dẫn/cạnh dẫn chúng ta tìm các luồng được gọi là các đường dẫn tăng thêm.