algorithm - una - Enrutar el problema en un gráfico: minimizar el costo marginal promedio en lugar del costo total

costo variable promedio

Question

Tengo un gráfico ponderado, sin ponderaciones negativas, y me gustaría encontrar la ruta de un nodo a otro, tratando de minimizar el costo del único paso. No es necesario que minimice el costo total del viaje (como, por ejemplo, Dijkstra), sino el costo promedio de un paso. Sin embargo, tengo una restricción: K, la cantidad máxima de nodos en la ruta.

Entonces, por ejemplo, para ir de A a J, tal vez Dijkstra encuentre esta ruta (entre paréntesis, el peso)

A (4) D (6) J -> total cost: 10

y el algoritmo que necesito, estableciendo K = 10, encontraría algo así como

A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15

¿Hay algún algoritmo bien conocido para este problema?

Gracias por adelantado.

Eugenio

Edite como respuesta a templatetypedef. Algunas preguntas:

1) El hecho de que pueda pasar un ciclo varias veces para reducir el promedio no es bueno para mi problema: tal vez debería haberlo mencionado, pero no quiero visitar el mismo nodo más de una vez

2) ¿Es posible explotar el hecho de que no tengo pesos negativos?

3) ¿Cuando dijiste O (kE) te referías al algoritmo completo o solo a la parte adicional?

Tomemos esta implementación simple en C donde n = número de nodos e = número de bordes, d es un vector con las distancias, vector pa con el predecesor y una estructura bordes (u, v, w) memoriza los bordes en los gráficos

for (i = 0; i < n; ++i)
    d[i] = INFINITY;

    d[s] = 0;

    for (i = 0; i < n - 1; ++i)
        for (j = 0; j < e; ++j)
            if (d[edges[j].u] + edges[j].w < d[edges[j].v]){
                d[edges[j].v] = d[edges[j].u] + edges[j].w;
                p[edges[j].v] = u;
                }

No estoy seguro de cómo debería modificar el código de acuerdo con su respuesta; tomar en consideración el promedio en vez del costo total si esto fuera suficiente?

for (i = 0; i < n; ++i)
        d[i] = INFINITY;

    d[s] = 0;

    for (i = 0; i < n - 1; ++i)
        steps = 0;
        for (j = 0; j < e; ++j)
            if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
                d[edges[j].v] = d[edges[j].u] + edges[j].w;
                p[edges[j].v] = u;
                steps++;
            }

Pero de todos modos no sé cómo tomar en consideración el límite K al mismo tiempo ... Gracias de antemano por su ayuda.

Editar Como puedo permitirme algunos errores, estoy pensando en esta solución naif:

• precomputar todos los caminos más cortos y memorizar en A
• precomputar todos los caminos más cortos en un gráfico modificado, donde corté los bordes sobre un cierto peso y los memoricé en B

Cuando necesito un camino, miro en A, por ejemplo, de xa y, esta es la ruta x-> z-> y, luego, para cada paso que miro en B, entonces para x> z veo si hay una conexión en B , si no, mantengo x> z, de lo contrario, llené el camino x> z con el subtrayecto proporcionado por B, que podría ser algo como x-> j-> h-> z; luego hago lo mismo por z-> y. Cada vez también verifico si estoy agregando una ruta cíclica.

Quizás consiga algunos caminos raros pero podría funcionar en la mayoría de los casos. Si extiendo la solución probando con diferentes "umbrales de corte", quizás también pueda estar cerca de respetar la restricción de K.

Answer 1

Creo que puedes resolver esto usando una versión modificada del algoritmo Bellman-Ford.

Bellman-Ford se basa en la siguiente recurrencia de programación dinámica que intenta encontrar la ruta más corta desde algunos nodos de inicio a cada uno de los nodos cuya longitud no sea superior a m para algunos m. Como caso base, cuando considera rutas de longitud cero, el único nodo alcanzable es s y los valores iniciales son

BF(s, t, 0) = infinity
BF(s, s, 0) = 0

Entonces, si conocemos los valores para una ruta de longitud m, podemos encontrarla para rutas de longitud m + 1 al notar que la ruta anterior puede seguir siendo válida, o queremos extender alguna ruta por longitud uno:

BF(s, t, m + 1) = min {
                     BF(s, t, m),
                     BF(s, u, m) + d(u, t) for any node u connected to t
                   }

El algoritmo como un todo funciona al señalar que cualquier camino más corto debe tener una longitud no mayor que n y luego usar la recurrencia anterior y la programación dinámica para calcular el valor de BF (s, t, n) para todo t. Su tiempo de ejecución general es O (EV), ya que hay bordes E a considerar en cada paso y V vértices totales.

Veamos cómo podemos cambiar este algoritmo para resolver su problema. En primer lugar, para limitar esto a las rutas de longitud k, podemos simplemente cortar la iteración de Bellman-Ford después de encontrar todas las rutas de longitud más cortas hasta k. Encontrar el camino con el costo promedio más bajo es un poco más complicado. En cada punto, rastrearemos dos cantidades: la longitud de la ruta más corta que llega a un nodo t y la longitud promedio de esa ruta. Cuando consideramos nuevas rutas que pueden alcanzar t, nuestras opciones son mantener la ruta anterior que encontramos (cuyo costo está dado por la ruta más corta dividida hasta el momento por la cantidad de nodos en ella) o extender alguna otra ruta en un paso. El nuevo costo de ese camino viene dado por el costo total desde antes más la longitud del borde dividido por el número de aristas en el camino anterior más uno. Si tomamos el más barato de estos y luego registramos tanto su costo como el número de bordes, al final habremos calculado la ruta con el menor costo promedio de longitud no mayor que k en el tiempo O (kE). Como inicialización, diremos que la ruta desde el nodo de inicio a sí misma tiene una longitud 0 y un costo promedio de 0 (el costo promedio no importa, ya que cada vez que lo multiplicamos por el número de bordes obtenemos 0). También diremos que cada otro nodo está a una distancia infinita al decir que el costo promedio de un borde es infinito y que el número de bordes es uno. De esta forma, si alguna vez tratamos de calcular el costo de un camino formado al extender el camino, parecerá que tiene un costo promedio infinito y no será elegido.

Matemáticamente, la solución se ve así. En cada punto, almacenamos el costo marginal promedio y el número total de bordes en cada nodo:

BF(s, t, 0).edges = 1
BF(s, t, 0).cost  = infinity

BF(s, s, 0).edges = 0
BF(s, s, 0).cost  = 0

BF(s, t, m + 1).cost = min {
    BF(s, t, m).cost,
    (BF(s, u, m).cost * BF(s, u, m).edges + d(u, t)) / (BF(s, u, m).edges + 1)
}

BF(s, t, m + 1).edges = {
    BF(s, t, m).edges         if you chose the first option above. 
    BF(s, u, m).edges + 1     else, where u is as above
}

Tenga en cuenta que esto puede no encontrar una ruta simple de longitud k, ya que la minimización del costo promedio puede requerir que tome un ciclo con un costo bajo (positivo o negativo) varias veces para reducir la media. Por ejemplo, si un gráfico tiene un ciclo de costo cero, debe seguir tomándolo tantas veces como sea posible.

EDITAR : en respuesta a sus nuevas preguntas, este enfoque no funcionará si no desea duplicar nodos en una ruta. Como @comestibles ha señalado, esta versión del problema es NP-hard, por lo que, a menos que P = NP, no se debe esperar encontrar ningún buen algoritmo de tiempo polinomial para este problema.

En cuanto al tiempo de ejecución, el algoritmo que he descrito arriba se ejecuta en tiempo total O (kE). Esto se debe a que cada iteración de calcular la recurrencia toma tiempo O (E) y hay un total de k iteraciones.

Finalmente, veamos tu código propuesto. Lo he reimpreso aquí:

for (i = 0; i < n - 1; ++i) {
    steps = 0;
    for (j = 0; j < e; ++j) {
        if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
            d[edges[j].v] = d[edges[j].u] + edges[j].w;
            p[edges[j].v] = u;
            steps++;
        }
    }
}

Su primera pregunta fue cómo tomar k en cuenta. Esto se puede hacer fácilmente reescribiendo el ciclo externo para contar hasta k, no n - 1. Eso nos da este código:

for (i = 0; i < k; ++i) {
    steps = 0;
    for (j = 0; j < e; ++j) {
        if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
            d[edges[j].v] = d[edges[j].u] + edges[j].w;
            p[edges[j].v] = u;
            steps++;
        }
    }
}

Un problema que estoy notando es que el algoritmo Bellman-Ford modificado necesita tener cada candidato mejor ruta almacenar su número de bordes de forma independiente, ya que la ruta óptima de cada nodo se puede alcanzar por un número diferente de bordes. Para solucionar esto, sugeriría que la matriz d almacenara dos valores: el número de aristas necesarias para llegar al nodo y el costo promedio de un nodo a lo largo de esa ruta. Luego, actualizaría su código reemplazando la variable de steps en estas ecuaciones con las longitudes de las rutas en caché.

¡Espero que esto ayude!

Answer 2

Para la nueva versión de su problema, hay una reducción de la ruta de acceso de Hamilton (lo que hace que su problema no se pueda resolver). Tomemos un ejemplo del camino de Hamilton (es decir, un gráfico cuyos bordes se supone que tienen un peso unitario), agreguemos vértices fuente y sumidero y bordes de peso 2 de la fuente a todos los demás y del fregadero a todos los demás. Establecer K = | V | + 2 y solicita una ruta desde el origen al receptor. Existe un camino de Hamilton si y solo si la longitud media óptima del borde es (| V | + 3) / (| V | + 2).

¿Cuéntanos por qué quieres estas rutas para que podamos aconsejarte acerca de una estrategia de aproximación razonable?

Answer 3

Puede modificar ligeramente el algoritmo Bellman-Ford para encontrar la ruta mínima usando como máximo K bordes / nodos. Si la cantidad de bordes es fija, debe minimizar el costo total, ya que el costo promedio sería TotalCost / NumberOfEdges.

Una de las soluciones sería iterar NumberOfEdges de 1 a K, encontrar un costo total mínimo y elegir un TotalCost / NumberOfEdges mínimo.