49

について話すときcomputing network flowsアルゴリズム設計マニュアルは次のように述べています。

従来のネットワークフローアルゴリズムは、パスを拡張し、sからtまでの正の容量のパスを繰り返し見つけて、それをフローに追加するという考え方に基づいています。ネットワークを通るフローは、拡張パスが含まれていない場合にのみ最適であることを示すことができます。

何なのかわかりませんaugmenting paths。私はグーグルで検索しました:

しかし、それらはすべて上記の引用を参照しています。

誰かが本当に明確に何であるかを説明できますaugmenting pathか?

4

4 に答える 4

53

増補パスは、ソースからシンクまでの正の容量を持つエッジのみを使用して、グラフを通過する単純なパス (サイクルを含まないパス) です。

したがって、上記のステートメントはなんとなく明らかです。正の容量エッジのみを使用するソースからシンクへのパスを見つけることができない場合、フローを増やすことはできません。

ところで、その命題の証明はそれほど簡単ではありません。

于 2012-05-01T11:41:23.710 に答える
7

Augmenting とは、増加 - 大きくすることを意味します。与えられたフロー ネットワークG=(V,E)とフローfでは、拡張パスは残差ネットワーク内のからへpの単純なパスです。の定義により、元のフロー ネットワークのとのいずれかで、制約に違反することなく容量まで増補パスのエッジでフローを増やすことができます。また、拡張パス p の各エッジでフローを増やすことができる最大量は と呼ばれます。証明は、トーマス h によるアルゴリズムの紹介で見つけることができます。コーメンなど...source ssink tGfresidual network(u,v)Cf(u,v)(u,v)(v,u)Gresidual capacity of p

于 2013-04-18T10:57:44.987 に答える
4

また、ソースからシンクへの拡張パスをどのように見つけますか? BFS の修正版を使用します。シンクに到達するまでソースから BFS を実行し、残りの容量がある場合にのみエッジをトラバースします (つまり、そのエッジの最大容量 - 電流フロー > 0)。ソースからシンクへのこのパスでは、そのパスを通過できる最大フローである最小残存容量を維持します。アイデアを得るための高レベルのコード スニペット:

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;
于 2013-12-29T03:12:42.703 に答える
0

ソースからシンクへのフローを繰り返し見つけるプロセス。たとえば、Ford-Fulkerson アルゴリズムの場合、最初はすべてのエッジのすべてのフローがゼロです。反復では、すべてのパス/エッジの値を取得して、拡張パスと呼ばれるフローを見つけます。

于 2015-12-10T04:48:22.293 に答える