“La variable es el tiempo”.
Entonces depende de qué función sean en realidad. Si desea arbitrarias, no puede esperar la solución exacta independientemente de si piensa en Bellman-Ford u otros algoritmos para los caminos más cortos: si tiene un gráfico de 2 vértices y 1 borde con peso f (t), encontrar la ruta más corta significa encontrar un mínimo de la función f (t) + t, que puede no ser factible (por ejemplo, si no puede calcular la derivada) o puede tener una muy mala complejidad (si (f (t) + t) ‘tiene muchos valores 0). Entonces, si no asume nada sobre las funciones o si ni siquiera conoce su fórmula completa y solo puede en la práctica calcularlas experimentalmente, lo mejor que puede hacer es encontrar numéricamente algunos candidatos para el mínimo, pero luego todos Los errores del algoritmo residen en las técnicas numéricas, no en el propio Bellman-Ford.
Si es fácil trabajar con sus funciones para que pueda calcular rápidamente un mínimo de f (t) + t en intervalos [x, inf), o si no lo son, pero está de acuerdo con aceptar los errores al calcularlo, entonces hay no hay problema con el uso de Bellman-Ford (o Dijkstra si las funciones son positivas) para el trabajo. Lo único que es importante en la prueba de B-F es que después de la iteración i-ésima, cada nodo tiene la ruta más corta calculada correctamente si esta ruta más corta no tiene más de i bordes. No se viola si decide cambiar el peso con el tiempo: solo hace una relajación del borde (u, v), así que lo que tiene es dist (u), el momento más temprano en el que podría haber llegado a u, dist (v ): El momento más temprano en que podría haber llegado a v, y lo que desea calcular es si ir a u y luego usar (u, v) no mejorará dist (v). Por lo tanto, solo necesita encontrar cuál es el momento óptimo para usar este borde si llega a usted en el momento dist (u), es decir, necesita un mínimo de peso (t) + t en el intervalo [dist (u), inf). La prueba seguirá en pie, si el camino más corto real hacia u tiene i bordes, después de la i-ésima iteración tendrá el valor correcto, por lo que la iteración i + 1-ésima analizará correctamente el uso potencial del borde (u, v ): verificará cuál es el momento más temprano posible para llegar a v si comienza en dist (u) y asumimos que dist (u) es el momento más temprano posible que puede llegar a usted, por lo que calcula el resultado correcto para “what es el momento más temprano que puedes llegar a v si (u, v) es tu última ventaja ”.
- Si cada solución recursiva se puede transformar en una iterativa, ¿por qué usar la recursividad?
- ¿Cómo un programa de razonamiento poco preciso asigna 8 gb de memoria en 3 segundos?
- ¿Cómo hace un algoritmo para hacer objetos en movimiento a partir de fotos?
- CodeChef: ¿Está bien resolver los desafíos de programación sin el conocimiento de algoritmos?
- ¿Cómo es posible que algún algoritmo sea más rápido que cualquier otro algoritmo similar para algunos valores de la variable de entrada y más lento para otros valores?
