Encontrar caminos cortos y gordos

Motivación: en los algoritmos de flujo máximo de ruta de aumento estándar, el bucle interno requiere encontrar rutas desde la fuente para hundirse en un gráfico ponderado dirigido. Teóricamente, es bien sabido que para que el algoritmo termine incluso cuando hay capacidades de borde irracionales, necesitamos establecer restricciones en los caminos que encontramos. El algoritmo Edmonds-Karp, por ejemplo, nos dice que busquemos caminos más cortos.

Empíricamente, se ha observado que también podríamos querer encontrar caminos gordos (¿hay un mejor término para esto?). Por ejemplo, cuando se usa el escalado de capacidad , encontramos rutas más cortas que pueden soportar al menos de flujo. No hay restricciones sobre la longitud del camino. Cuando ya no podemos encontrar ninguna ruta, disminuimos y repetimos.$\epsilon$$\epsilon$

Estoy interesado en optimizar la elección de aumentar las rutas para una aplicación muy específica de max-flow, y quiero explorar esta compensación entre las rutas cortas y gordas. (Nota: no es necesario que siempre resuelva el problema. Estoy más interesado en encontrar el límite inferior de flujo más grande en la menor cantidad de tiempo de pared).

Pregunta: ¿Existe una forma estándar de interpolar entre el enfoque de ruta más corta y el enfoque de escala de capacidad? Es decir, ¿existe un algoritmo para encontrar rutas que sean cortas y gordas, donde idealmente algún parámetro controlaría la longitud de la ruta que estamos dispuestos a cambiar por la gordura? En los extremos, me gustaría poder recuperar las rutas más cortas en un extremo y las rutas de estilo de escala de capacidad en el otro.

En el espíritu de su comentario sobre "bastante bueno pero no necesariamente óptimo", ¡presento la siguiente idea sin ninguna garantía de optimismo!

Para completar, aquí está el pseudocódigo al que se refirió (Observación: el algoritmo vinculado supone que las capacidades de borde son enteros entre 1 y C y que los valores de capacidad de flujo y residual son integrales):

Scaling-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← potencia más pequeña de 2 mayor o igual que C
   G_f ← gráfico residual

   mientras que (Δ ≥ 1) {
      G_f (Δ) ← Δ-gráfico residual
      while (existe una ruta de aumento P en G_f (Δ)) {
         f ← ​​aumento (f, C, P)
         actualizar G_f (Δ)
      }
      Δ ← Δ / 2
   }
   volver f
}

Observe que cuando = 1 ( en el psuedocode), solo está encontrando rutas en el orden más corto al más largo, y cuando es grande, está encontrando rutas en (más o menos) más gordas para orden más delgada. De hecho, dependiendo de la instancia, el algoritmo de escalamiento de capacidad encuentra rutas en el orden más corto a más largo dentro de "cubos" de "flujo suficiente".$\epsilon$$\epsilon = \Delta$$\epsilon$

Luego, agregue otro parámetro de entrada que represente cuánto le importa la "gordura" frente a la "escasez". Para asegurarnos de que no estamos afectando masivamente el tiempo de ejecución, también requerimos que sea ​​un número racional.$0 \le \rho \le 1$$\rho$

Luego, cada vez que a se le asigna un valor, también tomamos la media aritmética ponderada (espero que sea el término correcto ...) entre 1 y su valor actual. Es decir,$\epsilon$$\rho$

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

Para , terminamos con un algoritmo de ruta más corta pura; para , obtenemos un algoritmo de ruta más gordo puro; y para obtenemos algo intermedio. En particular, para un valor medio, convergerá a más rápidamente, por lo que obtendrá más rutas más cortas y menos rutas más gruesas.$\rho = 0$$\rho = 1$$0 < \rho < 1$$\epsilon$$\le 1$