Encontrar ciclos negativos para el algoritmo de cancelación de ciclo

Estoy implementando el algoritmo de cancelación de ciclo para encontrar una solución óptima para el problema de flujo de costo mínimo. Al encontrar y eliminar los ciclos de costos negativos en la red residual, el costo total se reduce en cada ronda. Para encontrar un ciclo negativo, estoy usando el algoritmo de Bellman-Ford.

Mi problema es: Bellman-ford solo encuentra ciclos accesibles desde la fuente, pero también necesito encontrar ciclos que no sean accesibles.

Ejemplo: en la siguiente red, ya aplicamos un flujo máximo. El borde hace muy costoso. En la red residual, tenemos un ciclo de costo negativo con capacidad . Retirarlo, nos daría una solución más barata utilizando bordes y , pero no puede llegar a ella desde la fuente . $(A, B)$ $1$ $(A, C)$ $(C, T)$ $S$

Etiquetas: flujo / capacidad, costo

ingrese la descripción de la imagen aquí

Por supuesto, podría ejecutar Bellman-Ford varias veces con cada nodo como fuente, pero eso no parece una buena solución. Estoy un poco confundido porque todos los documentos que leo parecen saltear este paso.

¿Me puede decir cómo usar bellman-ford para encontrar cada ciclo negativo (accesible o no)? Y si no es posible, ¿qué otro algoritmo propones?

algorithms graph-theory shortest-path network-flow Patrick Schmidt
fuente

Si no se puede alcanzar un ciclo a través de la fuente, ¿cómo puede afectar el flujo total?

Nicholas Mancuso

No afectará el valor del flujo sino el costo total. Ver el nuevo ejemplo.

Patrick Schmidt el

Creo que deberías sacar a Bellman-Ford del fregadero, ¿no? Si encuentra un flujo máximo,

f

$f$ , luego debajo del gráfico residual

G_{f}

$G_f$ no habrá un camino desde

s

$s$ a

t

$t$ . Por lo tanto, Bellman-Ford debe ejecutarse en

G_{f}

$G_f$ con

t

$t$ .

Nicholas Mancuso

Respuestas:

Para ampliar mi comentario, recuerde, este algoritmo para encontrar Flujo de Costo Mínimo se basa en el hecho de que $f$ es máximo Al ejecutar primero Ford-Fulkerson para encontrar $f$ y la red residual resultante $G_f$ , el costo $f$ luego se reduce al encontrar ciclos negativos en $G_f$ . Es decir, al encontrar ciclos negativos en $G_f$ no cambiamos la cantidad de flujo, $f$ , pero simplemente el costo.

Ahora ejecutando Bellman-Ford de $t$ en $G_f$ podemos rastrear hacia atrás en bordes que tienen flujo no negativo (por definición de $G_f$ ) Si los ciclos son adyacentes a cualquier borde en estos caminos, entonces podemos "transferir" cierta cantidad de flujo a otros bordes en el ciclo. En otras palabras, mantenemos el flujo neto durante algún ciclo igual, pero podemos cambiar el costo.

Observe un ciclo inalcanzable desde $t$ debe tener flujo cero. De lo contrario tendríamos una contradicción en $f$ siendo máximo

^{Pido disculpas por la "ondulación manual" de esta explicación. Intentaré ser más formal cuando tenga tiempo esta noche.}

Nicholas Mancuso
fuente

Gracias, tu última oración lo deja claro. Por lo tanto, es suficiente con los ciclos a los que se puede acceder desde

T

$T$ .

Patrick Schmidt el

Mi sugerencia: debe iniciar el algoritmo desde T para encontrar un ciclo negativo en su red residual. El resultado debe ser el mismo, pero luego puedes alcanzar el círculo

Sven Jung
fuente

Esto funciona para este gráfico, pero puede tener ciclos negativos que no están conectados a S o T. Sospecho que el OP quiere una solución que funcione en general.

Peter Shor

sí, en general no puede encontrar cada ciclo negativo, pero el OP quiere mejorar su red residual al verificar los costos. Entonces los círculos negativos inalcanzables no importan

Sven Jung

Quiero usar esto para obtener un flujo mínimo de costos. Entonces, la nueva pregunta sería: ¿Es suficiente eliminar cada ciclo al que se puede acceder desde el fregadero?

T

$T$ (En la red residual). En este momento no puedo encontrar un contraejemplo

Patrick Schmidt, el

Puede ver un flujo como originario de

S

$S$ y yendo a

T

$T$ , o invertir cada borde y verlo como originario de

T

$T$ y yendo a

S

$S$ . Si elimina todos los ciclos a los que se puede acceder desde la fuente

S

$S$ no funciona, eliminando cada ciclo al que se puede acceder desde el fregadero

T

$T$ no funciona La fuente y el sumidero se comportan simétricamente.

Peter Shor

por supuesto, es lo mismo si invierte cada borde y comienza desde T, porque nada cambió. Pero, ¿por qué no comenzar en T sin invertir los bordes? Entonces debería encontrar un ciclo negativo alcanzable, si existe. La pregunta es, si los ciclos negativos inalcanzables realmente no importan

Sven Jung

Creo que no es suficiente ejecutar Bellman-Ford desde T o S. Considere un ejemplo en el que hay una ventaja de S a T y un ciclo de costo negativo que no se puede lograr ni de S ni de T.

Una solución es agregar una S 'auxiliar y agregar una arista desde S' a cualquier otro vértice con costo 0. Luego ejecuta Bellman-Ford desde S '. De esta manera, todos los ciclos negativos son accesibles desde S '.

Además, realmente no necesita agregar ese vértice auxiliar S 'en su implementación. Simplemente inicialice d (v) = 0 para cualquier vértice v.

Vea cómo Boost Graph Library lo implementa.

Hongjie Chen
fuente