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

9

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?

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
2
Creo que deberías sacar a Bellman-Ford del fregadero, ¿no? Si encuentra un flujo máximo,f, luego debajo del gráfico residual Gf no habrá un camino desde s a t. Por lo tanto, Bellman-Ford debe ejecutarse enGf con t.
Nicholas Mancuso

Respuestas:

2

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

Ahora ejecutando Bellman-Ford de t en Gf podemos rastrear hacia atrás en bordes que tienen flujo no negativo (por definición de Gf) 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 tdebe tener flujo cero. De lo contrario tendríamos una contradicción enf 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 desdeT.
Patrick Schmidt el
0

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
1
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(En la red residual). En este momento no puedo encontrar un contraejemplo
Patrick Schmidt, el
Puede ver un flujo como originario de S y yendo a T, o invertir cada borde y verlo como originario de T y yendo a S. Si elimina todos los ciclos a los que se puede acceder desde la fuenteS no funciona, eliminando cada ciclo al que se puede acceder desde el fregadero Tno 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
0

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