¿Qué es exactamente el camino de aumento?

Question

Cuando se habla de computing network flows, la Algorithm Design Manual dice:

algoritmos de flujo de red tradicionales se basan en la idea de trayectorias de aumento, y encontrar repetidamente una trayectoria de la capacidad positiva de s a t y agregarlo a la corriente . Se puede demostrar que el flujo a través de una red es óptimo si y solo si no contiene una ruta de aumento.

No entiendo lo que es augmenting paths. He buscado en Google y encontrado:

• Augmenting Path in Wolfram

• Flow network in Wiki

pero todos ellos referencia a la cita anterior.

¿Alguien puede explicar con claridad qué es un augmenting path?

Answer 1

Una ruta de aumento es una ruta simple, una ruta que no contiene ciclos, a través del gráfico que utiliza solo los bordes con capacidad positiva desde la fuente al sumidero.

Por lo tanto, la afirmación anterior es de alguna manera obvia: si no puede encontrar una ruta desde el origen hasta el receptor que solo usa bordes de capacidad positiva, entonces el flujo no se puede aumentar.

Por cierto, la prueba de esa afirmación no es tan fácil.

Answer 2

Aumento significa aumentar-hacer más grande. En una red de flujo dada G=(V,E) y un flujo f, una ruta de aumento p es una ruta simple desde source s hasta sink t en la red residual Gf. Por la definición de residual network, podemos aumentar el flujo en un borde (u,v) de un camino de aumento hasta una capacidad Cf(u,v) sin violar la restricción, en cualquiera de (u,v) y (v,u) en la red de flujo original G. También la cantidad máxima por la cual podemos aumentar el flujo en cada borde en una ruta aumentada p se llama residual capacity of p. La demostración se puede encontrar en la introducción a los algoritmos por thomas h. cormen, etc ...

Answer 3

¿Y cómo averiguas el camino de aumento de la fuente al sumidero? Usando la versión modificada de BFS. Hace BFS desde la fuente hasta llegar al sumidero y recorre un borde solo si tiene capacidad residual (es decir, para ese borde, su capacidad máxima - flujo de corriente> 0). Y para este camino desde el origen al sumidero, mantienes la capacidad residual mínima, que es el flujo máximo que puedes atravesar por ese camino. Alto nivel de fragmento de código para obtener la idea:

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

Un proceso de búsqueda de los flujos de la fuente al sumidero de forma iterativa. Por ejemplo, en el caso del algoritmo de Ford-Fulkerson, inicialmente todos los flujos en todos los bordes son cero. En la iteración tomamos los valores para cada ruta/borde que nos lleva a encontrar flujos llamados caminos de aumento.