Говоря о computing network flows, Руководство по разработке алгоритмов говорит:
Традиционные алгоритмы сетевого потока основаны на идее расширений путей и многократно находят путь положительной емкости от s до t и добавляют его к потоку. Можно показать, что поток через сеть является оптимальным тогда и только тогда, когда он не содержит пути увеличения.
Я не понимаю, что такое augmenting paths. Я googled, и нашел:
но все они ссылаются на приведенную выше цитату.
Кто-нибудь может действительно объяснить, что такое augmenting path?
Путь расширения - это простой путь - путь, который не содержит циклов, - через граф, используя только ребра с положительной мощностью от источника до приемника.
Таким образом, приведенное выше высказывание является каким-то очевидным - если вы не можете найти путь от источника к приемнику, который использует только положительные границы мощности, то поток не может быть увеличен.
Кстати, доказательство этого утверждения не так просто.
Увеличение означает увеличение - сделать больше. В данной сети потока G=(V,E) и потоке f путь расширения p представляет собой простой путь от source s до sink t в остаточной сети Gf. По определению residual network мы можем увеличить поток на ребре (u,v) пути расширения до емкости Cf(u,v) без нарушения ограничения, в зависимости от того, что (u,v) и (v,u) находится в исходном потоке сеть G.
Также максимальное количество, на которое мы можем увеличить поток на каждом ребре в расширенном пути p, называется residual capacity of p.
Доказательство можно найти во введении к алгоритмам thomas h. cormen и т.д.
И как вы узнаете путь увеличения из источника, чтобы потопить? Использование модифицированной версии 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;
Процесс поиска потоков из источника для итерации. Например, в случае алгоритма Форда-Фулкерсона сначала все потоки на всех ребрах равны нулю. На итерации мы берем значения для каждого пути/ребра, ведущего к тому, чтобы находить потоки, называемые дополнительными путями.