dijkstra - investigacion - camino mas corto grafos java
El algoritmo de Dijkstra con pesos negativos (7)
¿Podemos usar el algoritmo de Dijkstra con pesos negativos?
¡DETENER! Antes de que pienses "lol nub puedes saltar sin parar entre dos puntos y obtener un camino infinitamente barato", estoy pensando más en caminos de una sola dirección.
Una aplicación para esto sería un terreno montañoso con puntos en él. Obviamente, pasar de mayor a menor no consume energía; de hecho, genera energía (¡y por lo tanto un peso de ruta negativo)! Pero regresar de nuevo no funcionaría de esa manera, a menos que seas Chuck Norris.
Estaba pensando en aumentar el peso de todos los puntos hasta que no sean negativos, pero no estoy seguro de si eso funcionará.
En realidad, creo que funcionará para modificar los pesos de los bordes. No con un desplazamiento, pero con un factor. Suponga que en lugar de medir la distancia está midiendo el tiempo requerido desde el punto A hasta el B.
peso = tiempo = distancia / velocidad
Incluso puedes adaptar la velocidad dependiendo de la pendiente para usar la física si tu tarea es para montañas reales y auto / bicicleta.
En realidad, hay un algoritmo que usa el algoritmo de Dijkstra en un entorno de ruta negativa; lo hace eliminando todos los bordes negativos y reequilibrando primero el gráfico. Este algoritmo se llama ''Algoritmo de Johnson''.
La forma en que funciona es agregando un nuevo nodo (digamos Q) que tiene un costo de 0 para atravesar a cada otro nodo en el gráfico. Luego ejecuta Bellman-Ford en el gráfico desde el punto Q, obteniendo un costo para cada nodo con respecto a Q que llamaremos q [x], que será 0 o un número negativo (ya que usó uno de los caminos negativos )
Por ejemplo, a -> -3 -> b, por lo tanto, si agregamos un nodo Q que tiene 0 costo para todos estos nodos, entonces q [a] = 0, q [b] = -3.
Luego reequilibramos los bordes usando la fórmula: peso + q [fuente] - q [destino], por lo que el nuevo peso de a-> b es -3 + 0 - (-3) = 0. Hacemos esto para todos los demás bordes en el gráfico, luego eliminar Q y sus bordes salientes y ¡voila! ¡Ahora tenemos un gráfico reequilibrado sin bordes negativos en el que podemos ejecutar dijkstra!
El tiempo de ejecución es O (nm) [bellman-ford] + nx O (m log n) [n Dijkstra''s] + O (n ^ 2) [cálculo de peso] = O (nm log n) time
Más información: http://joonki-jeong.blogspot.co.uk/2013/01/johnsons-algorithm.html
Puede usar Dijkstra en un gráfico con ponderación negativa, pero primero debe encontrar la compensación adecuada para cada Vertex. Eso es esencialmente lo que hace el algoritmo de Johnson. Pero eso sería excesivo ya que Johnson usa Bellman-Ford para encontrar la (s) compensación (es) de peso. Johnson''s está diseñado para todos los caminos más cortos entre pares de vértices.
Sí, podrías hacer eso agregando un paso al final, es decir,
If v ∈ Q, Then Decrease-Key(Q, v, v.d)
Else Insert(Q, v) and S = S / {v}.
Si lees la prueba de optimalidad, una de las suposiciones es que todos los pesos no son negativos. Entonces, no . Como Bart recomienda, use Bellman-Ford si no hay ciclos negativos en su gráfico.
Debe comprender que una ventaja negativa no es solo un número negativo, sino que implica una reducción en el costo de la ruta. Si agrega un borde negativo a su ruta, ha reducido el costo de la ruta --- si incrementa los pesos de modo que este borde ahora no sea negativo, ya no tiene esa propiedad de reducción y por lo tanto este es un diferente grafico.
Te animo a que leas la prueba de optimalidad: allí verás que la suposición de que agregar una ventaja a una ruta existente solo puede aumentar (o no afectar) el costo de la ruta es fundamental.
Siempre que el gráfico no contenga un ciclo negativo (un ciclo dirigido cuyos pesos de borde tengan una suma negativa), tendrá una ruta más corta entre dos puntos, pero el algoritmo de Dijkstra no está diseñado para encontrarlos. El algoritmo más conocido para encontrar rutas de acceso más cortas de fuente única en un gráfico dirigido con ponderaciones negativas es el en.wikipedia.org/wiki/Bellman-Ford_algorithm . Esto tiene un costo, sin embargo: Bellman-Ford requiere O (| V | · | E |) tiempo, mientras que Dijkstra''s requiere O (| E | + | V | log | V |) tiempo, que es asintóticamente más rápido para ambos escasos gráficos (donde E es O (| V |)) y gráficos densos (donde E es O (| V | ^ 2)).
En su ejemplo de un terreno montañoso (necesariamente un gráfico dirigido , dado que subir y bajar una pendiente tienen diferentes pesos) no hay posibilidad de un ciclo negativo, ya que esto implicaría dejar un punto y luego volver a él con un aumento neto de energía - que podría usarse para crear una máquina de movimiento perpetuo .
Aumentar todos los pesos en un valor constante para que no sean negativos no funcionará. Para ver esto, considere el gráfico donde hay dos caminos de A a B, uno que atraviesa un único borde de longitud 2 y uno que atraviesa los bordes de longitud 1, 1 y -2. La segunda ruta es más corta, pero si aumenta todos los pesos de los bordes en 2, la primera ruta ahora tiene la longitud 4, y la segunda ruta tiene la longitud 6, invirtiendo las rutas más cortas. Esta táctica solo funcionará si todos los caminos posibles entre los dos puntos usan la misma cantidad de aristas.
Un árbol de expresiones es un árbol binario en el que todas las hojas son operandos (constantes o variables), y los nodos de hojas son operadores binarios ( + , - , / , * , ^ ). Implemente este árbol para modelar polinomios con los métodos básicos del árbol, incluidos los siguientes:
- Una función que calcula la primera derivada de un polinomio.
- Evalúa un polinomio para un valor dado de x.
[20] Use las siguientes reglas para la derivada: Derivada (constante) = 0 Derivada (x) = 1 Derivada (P (x) + Q (y)) = Derivada (P (x)) + Derivada (Q (y) ) Derivado (P (x) - Q (y)) = Derivado (P (x)) - Derivado (Q (y)) Derivado (P (x) * Q (y)) = P (x) * Derivado (Q) (y)) + Q (x) * Derivado (P (x)) Derivado (P (x) / Q (y)) = P (x) * Derivado (Q (y)) - Q (x) * Derivado ( P (x)) Derivada (P (x) ^ Q (y)) = Q (y) * (P (x) ^ (Q (y) - 1)) * Derivada (Q (y))