ford explained bellman algoritmo algorithm constraints shortest-path bellman-ford

algorithm - explained - Encontrar la ruta más corta en un gráfico sin ningún prefijo negativo



dijkstra greedy algorithm (9)

Encuentre la ruta más corta desde el origen hasta el destino en un gráfico dirigido con bordes positivos y negativos, de manera que en ningún punto de la ruta la suma de bordes que viene antes sea negativa. Si no existe tal camino, informe eso también.

Intenté usar Bellman Ford modificado, pero no pude encontrar la solución correcta.

Me gustaría aclarar algunos puntos:

  1. Sí, puede haber ciclos de peso negativo.
  2. n es el número de aristas.
  3. Suponga que existe una ruta de longitud O (n) si el problema tiene una solución.
  4. + 1 / -1 pesas de borde.

Aunque las personas han demostrado que no existe una solución rápida (a menos que P = NP) ..

Creo que para la mayoría de los gráficos (95% +) deberías poder encontrar una solución bastante rápido.

Aprovecho el hecho de que si hay ciclos, generalmente hay muchas soluciones y solo necesitamos encontrar una de ellas. Probablemente hay algunos vacíos en mis ideas, por favor hágamelo saber.

Ideas:

1. Encuentra el ciclo negativo más cercano al destino. denota la distancia más corta entre el ciclo y el destino como d (final, negC)

(Creo que esto es posible, una forma podría ser usar floyds para detectar (i, j) con un ciclo negativo, y luego realizar una primera búsqueda desde el destino hasta que llegue a algo que esté conectado a un ciclo negativo).

2. encuentre el ciclo positivo más cercano al nodo de inicio, denote la distancia desde el inicio como d (inicio, posC)

(Argumento que en el 95% de los gráficos puedes encontrar estos ciclos fácilmente)

Now we have cases: a) there is both the positive and negative cycles were found: The answer is d(end,negC). b) no cycles were found: simply use shortest path algorithm? c) Only one of the cycles was found. We note in both these cases the problem is the same due to symmetry (e.g. if we swap the weights and start/end we get the same problem). I''ll just consider the case that there was a positive cycle found. find the shortest path from start to end without going around the positive cycle. (perhaps using modified breadth first search or something). If no such path exists (without going positive).. then .. it gets a bit tricky.. we have to do laps of the positive cycle (and perhaps some percentage of a lap). If you just want an approximate answer, work out shortest path from positive cycle to end node which should usually be some negative number. Calculate number of laps required to overcome this negative answer + the distance from the entry point to the cycle to the exit point of the cycle. Now to do better perhaps there was another node in the cycle you should have exited the cycle from... To do this you would need to calculate the smallest negative distance of every node in the cycle to the end node.. and then it sort of turns into a group theory/ random number generator type problem... do as many laps of the cycle as you want till you get just above one of these numbers.

Buena suerte y espero que mis soluciones funcionen en la mayoría de los casos.

Como señala Kaganar, básicamente tenemos que hacer algunas suposiciones para obtener un algoritmo de polytime. Supongamos que las longitudes de borde están en {-1, 1}. Dado el gráfico, construya una gramática ponderada libre de contexto que reconozca las rutas válidas desde el origen hasta el destino con un peso igual al número de bordes 1 en exceso (generaliza la gramática para paréntesis equilibrados). Calcule, para cada no terminal, el costo de la producción más barata al inicializar todo hasta el infinito o 1, dependiendo de si hay una producción cuyo RHS no tenga terminal y luego se relaje n - 1 veces, donde n es el número de no terminales.

Es cierto que esta no es una respuesta constructiva, sin embargo, es demasiado largo para publicar en un comentario ...

Me parece que este problema contiene los problemas de mochila binarios y discretos, por lo que su peor tiempo de ejecución es, en el mejor de los casos, pseudo-polynomial . Considere un gráfico que está conectado y ponderado de la siguiente manera:

Entonces, el problema de la mochila binaria equivalente es tratar de elegir pesos del conjunto { a 0 , ..., n } que maximiza Σ a i donde Σ a i < X .

Como nota al margen, si introducimos bucles ponderados, es fácil construir el problema de la mochila sin límites.

Por lo tanto, cualquier algoritmo práctico que pueda elegir tiene un tiempo de ejecución que depende de lo que considere el caso "promedio". ¿Hay alguna restricción al problema que no haya considerado o que no haya tenido a mi disposición? Parece bastante seguro de que es un problema O ( n 3 ). (Aunque ¿qué es n en este caso?)

Los supuestos actuales son:

  1. Sí, puede haber ciclos de peso negativo.
  2. n es el número de aristas.
  3. Suponga que existe una ruta de longitud O (n) si el problema tiene una solución.
  4. + 1 / -1 pesas de borde.

Podemos suponer sin pérdida de generalidad que el número de vértices es a lo sumo n. Recursivamente recorra el gráfico y recuerde los valores de costo para cada vértice. Deténgase si el costo ya fue recordado para el vértice, o si el costo sería negativo.

Después de los pasos O (n), el destino no se ha alcanzado y no hay solución. De lo contrario, para cada uno de los vértices O (n) hemos recordado a lo sumo O (n) valores de costo diferentes, y para cada una de estas combinaciones O (n ^ 2) podría haber habido hasta n intentos fallidos de caminar a otros vértices . Con todo, es O (n ^ 3). qed

Actualización: Por supuesto, hay algo sospechoso otra vez. ¿Qué significa la suposición 3: existe una ruta de longitud O (n) si el problema tiene una solución? Cualquier solución tiene que detectar eso, porque también tiene que informar si no hay una solución. Pero es imposible detectar eso, porque eso no es una propiedad del gráfico individual en el que trabaja el algoritmo (es un comportamiento asintótico).

(También está claro que no todos los gráficos para los que se puede alcanzar el destino tienen una ruta de solución de longitud O (n): tome una cadena de m bordes de peso -1, y antes de eso un ciclo simple de m bordes y peso total +1).

[Ahora me doy cuenta de que la mayoría del código Python de mi otra respuesta (intento de la primera versión del problema) se puede reutilizar.]

Me gustaría aclarar algunos puntos:

  1. Sí, puede haber ciclos de peso negativo.
  2. n es el número de aristas.
  3. los pesos son arbitrarios no solo + 1 / -1.
  4. Suponga que existe una ruta de longitud O (n) si el problema tiene una solución. (n es el número de bordes)

Paso 1: Tenga en cuenta que su respuesta será como máximo 2 * n (si existe).
Paso 2: Cree un nuevo gráfico con vértices que sean pares de [vértice] [costo]. (2 * n ^ 2 vértices)
Paso 3: Tenga en cuenta que la nueva gráfica tendrá todos los bordes iguales a uno, y como máximo 2 * n para cada par [vértice] [costo].
Paso 4: haga un dfs sobre este gráfico, comenzando desde [inicio] [0]
Paso 5: Encuentra el mínimo de k, de manera que [acabado] [k] sea accesible.

La complejidad total es a lo sumo O (n ^ 2) * O (n) = O (n ^ 3)

EDIT: aclaración en el paso 1.
Si hay un ciclo positivo, accesible desde el inicio, puede ir hasta n. Ahora puede caminar a cualquier vértice accesible, sobre no más de n bordes, cada uno es +1 o -1, lo que le deja con el rango [0; 2n]. De lo contrario, recorrerá ciclos negativos, o no más de n +1, que no están en ciclo negativo, dejándole con el rango [0; n].

Yo usaría la fuerza bruta de recursión aquí: algo como (pseudo código para asegurarse de que no sea específico del idioma)

necesitará:

  • La matriz 2D de bools que muestra dónde PUEDE y adónde NO puede ir, NO debe incluir "valores prohibidos", como antes del borde negativo, puede elegir agregar una ''traducción'' vertical y horizontal para asegurarse de que comienza en [0 ] [0]
  • un entero (estático) que contiene la ruta más corta
  • Una matriz 1D de 2 ranuras, que muestra el objetivo. [0] = x, [1] = y

harás:

function(int xPosition, int yPosition, int steps) { if(You are at target AND steps < Shortest Path) Shortest Path = steps if(This Position is NOT legal) /*exit function*/ else /*try to move in every legal DIRECTION, not caring whether the result is legal or not but always adding 1 to steps, like using:*/ function(xPosition+1, yPosition, steps+1); function(xPosition-1, yPosition, steps+1); function(xPosition, yPosition+1, steps+1); function(xPosition, yPosition-1, steps+1); }

luego simplemente ejecútelo con la función (StartingX, StartingY, 0);

El camino más corto estará contenido en el int externo estático.

ACTUALIZACIÓN: El OP ahora ha tenido varias rondas de aclaraciones, y ahora es un problema diferente. Dejaré esto aquí para documentar mis ideas para la primera versión del problema (o más bien mi comprensión de ello). Intentaré una nueva respuesta para la versión actual del problema. Fin de actualización

Es una pena que el OP no haya aclarado algunas de las preguntas abiertas. Asumiré lo siguiente:

  1. Los pesos son +/- 1.
  2. n es el número de vértices

El primer supuesto es que no hay pérdida de generalidad, obviamente, pero tiene un gran impacto en el valor de n (a través del segundo supuesto). Sin el primer supuesto, incluso un pequeño gráfico (fijo) puede tener soluciones largas arbitrarias variando las ponderaciones sin límites.

El algoritmo que propongo es bastante simple y similar a los algoritmos de gráficos conocidos. Sin embargo, no soy experto en gráficos, por lo que puedo usar las palabras equivocadas en algunos lugares. Sientase libre de corregirme.

  1. Para el vértice de origen, recuerde el costo 0. Agregue (origen, 0) a la lista de tareas.
  2. Pop un elemento de la lista de tareas pendientes. Siga todos los bordes salientes del vértice, calculando el nuevo costo c para alcanzar el nuevo vértice v. Si el nuevo costo es válido (c> = 0 y c <= n ^ 2 , consulte a continuación) y no se recuerda para v, agréguelo a los valores de costo recordados de v, y agregue (v, c) a su lista de tareas pendientes.
  3. Si la lista de tareas no está vacía, continúe con el paso 2. (O salga temprano si se puede llegar al destino con el costo 0).

Está claro que cada "paso" que no es un callejón sin salida inmediato crea una nueva combinación (vértice, costo). Se almacenarán a lo sumo n * n ^ 2 = n ^ 3 de estas combinaciones, y por lo tanto, en cierto sentido, este algoritmo es O (n ^ 3).

Ahora, ¿por qué encuentra esto el camino óptimo? No tengo una prueba real, pero creo que las siguientes ideas justifican por qué creo que esto es suficiente, y es posible que se puedan convertir en una prueba real.

Creo que está claro que lo único que tenemos que mostrar es que la condición c <= n ^ 2 es suficiente.

Primero, notemos que cualquier vértice (alcanzable) se puede alcanzar con un costo menor que n.

Sea (v, c) parte de una ruta óptima y c> n ^ 2. Como c> n, debe haber algún ciclo en la ruta antes de llegar a (v, c), donde el costo del ciclo es 0 <m1 <n, y debe haber algún ciclo en el camino después de alcanzar (v, c), donde el costo del ciclo es 0> m2> -n.

Además, sea v accesible desde la fuente con un costo 0 <= c1 <n, mediante una ruta que toque el primer ciclo mencionado anteriormente, y permita que el destino sea accesible desde v con un costo 0 <= c2 <n, mediante una ruta que Toca el otro ciclo mencionado anteriormente.

Luego podemos construir rutas de origen a v con costos c1, c1 + m1, c1 + 2 * m1, ..., y rutas de v a destino con costos c2, c2 + m2, c2 + 2 * m2, ... . Elija 0 <= a <= m2 y 0 <= b <= m1, de manera que c1 + c2 + a * m1 + b * m2 sea mínimo y, por lo tanto, el costo de una ruta óptima. En esta ruta óptima, v tendría el costo c1 + a * m1 <n ^ 2.

Si el gcd de m1 y m2 es 1, entonces el costo será 0. Si el gcd es> 1, entonces podría ser posible elegir otros ciclos para que el gcd se convierta en 1. Si eso no es posible, tampoco es posible para la solución óptima, y ​​habrá un costo positivo para la solución óptima.

(Sí, puedo ver varios problemas con este intento de una prueba. Podría ser necesario tomar el gcd de varios costos de ciclo positivos o negativos, etc. Sin embargo, estaría muy interesado en un contraejemplo).

Aquí hay algo de código (Python):

def f(vertices, edges, source, dest): # vertices: unique hashable objects # edges: mapping (u, v) -> cost; u, v in vertices, cost in {-1, 1} #vertex_costs stores the possible costs for each vertex vertex_costs = dict((v, set()) for v in vertices) vertex_costs[source].add(0) # source can be reached with cost 0 #vertex_costs_from stores for each the possible costs for each vertex the previous vertex vertex_costs_from = dict() # vertex_gotos is a convenience structure mapping a vertex to all ends of outgoing edges and their cost vertex_gotos = dict((v, []) for v in vertices) for (u, v), c in edges.items(): vertex_gotos[u].append((v, c)) max_c = len(vertices) ** 2 # the crucial number: maximal cost that''s possible for an optimal path todo = [(source, 0)] # which vertices to look at while todo: u, c0 = todo.pop(0) for v, c1 in vertex_gotos[u]: c = c0 + c1 if 0 <= c <= max_c and c not in vertex_costs[v]: vertex_costs[v].add(c) vertex_costs_from[v, c] = u todo.append((v, c)) if not vertex_costs[dest]: # destination not reachable return None # or raise some Exception cost = min(vertex_costs[dest]) path = [(dest, cost)] # build in reverse order v, c = dest, cost while (v, c) != (source, 0): u = vertex_costs_from[v, c] c -= edges[u, v] v = u path.append((v, c)) return path[::-1] # return the reversed path

Y la salida de algunos gráficos (bordes y su peso / ruta / costo en cada punto de la ruta; lo siento, no hay buenas imágenes):

AB+ BC+ CD+ DA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH- A B C D A X Y H I J K L M H 0 1 2 3 4 5 6 7 6 5 4 3 2 1 AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH- A B C D E F G A B C D E F G A B C D E F G A X Y H I J K L M H I J K L M H I J K L M H I J K L M H 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH- A X Y H 0 1 2 3 AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH- A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G A X Y H I J K L M N O P H I J K L M N O P H I J K L M N O P H I J K L M N O P H I J K L M N O P H 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

Aquí está el código para producir esa salida:

def find_path(edges, source, path): from itertools import chain print(edges) edges = dict(((u, v), 1 if c == "+" else -1) for u, v, c in edges.split()) vertices = set(chain(*edges)) path = f(vertices, edges, source, dest) path_v, path_c = zip(*path) print(" ".join("%2s" % v for v in path_v)) print(" ".join("%2d" % c for c in path_c)) source, dest = "AH" edges = "AB+ BC+ CD+ DA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-" # uv+ means edge from u to v exists and has cost 1, uv- = cost -1 find_path(edges, source, path) edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-" find_path(edges, source, path) edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-" find_path(edges, source, path) edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-" find_path(edges, source, path)

Peter de Rivaz señaló en un comentario que este problema incluye a HAMILTONIAN PATH como un caso especial. Su explicación fue un poco breve, y me tomó un tiempo averiguar los detalles, así que dibujé algunos diagramas para beneficio de otros que podrían estar luchando. He hecho esta wiki de post comunidad.

Usaré el siguiente gráfico con seis vértices como ejemplo. Uno de sus caminos hamiltonianos se muestra en negrita.

Dado un gráfico no dirigido con n vértices para el que queremos encontrar una ruta hamiltoniana, construimos un nuevo gráfico dirigido ponderado con n 2 vértices, más los vértices de INICIO y FINAL. Etiqueta los vértices originales v i y los nuevos vértices w ik para 0 ≤ i , k < n . Si hay un borde entre v i y v j en el gráfico original, entonces para 0 ≤ k < n −1 hay bordes en el nuevo gráfico de w ik a w j ( k +1) con peso −2 j y de w jk a w i ( k +1) con peso −2 i . Hay bordes desde START hasta w i0 con peso 2 n - 2 i - 1 y desde w i ( n −1) hasta END con peso 0.

Es más fácil pensar que esta construcción es equivalente a comenzar con una puntuación de 2 n - 1 y luego restar 2 i cada vez que visitas w ij . (Así es como he dibujado el gráfico de abajo).

Cada ruta desde START hasta END debe visitar exactamente n + 2 vértices (uno de cada fila, más START y END), por lo que la única forma de que la suma a lo largo de la ruta sea cero es que visite cada columna exactamente una vez.

Así que aquí está el gráfico original con seis vértices convertidos en un nuevo gráfico con 38 vértices. El camino hamiltoniano original corresponde al camino trazado en negrita. Puedes verificar que la suma a lo largo del camino es cero.