Me encanta la orientación sobre este problema:
G es un gráfico acíclico dirigido. Desea pasar del vértice c al vértice z. Algunos bordes reducen sus ganancias y otros aumentan sus ganancias. ¿Cómo se pasa de c a z mientras se maximiza su beneficio? ¿Cuál es la complejidad del tiempo?
¡Gracias!
Respuestas
1 para la respuesta № 1El problema tiene una subestructura óptima. Para encontrar el camino más largo desde el vértice c vértice z, primero necesitamos encontrar el camino más largo desde c a todos los predecesores de z. Cada problema de estos es otro subproblema más pequeño (el camino más largo desde c a un predecesor específico).
Vamos a denotar los predecesores de z como u1,u2,...,uk y dist[z] ser el camino más largo desde c a z entonces dist[z]=max(dist[ui]+w(ui,z))..
Aquí hay una ilustración con 3 predecesores que omiten los pesos del conjunto de bordes:
Para encontrar el camino más largo hacia z primero necesitamos encontrar el camino más largo hacia sus predecesores y tomar el máximo (sus valores más sus pesos de aristas para z)
Esto requiere cada vez que visitamos un vértice utodo uLos predecesores deben haber sido analizados y calculados.
Entonces la pregunta es: para cualquier vértice u, cómo asegurarnos de que una vez que establecemos dist[u], dist[u] nunca se cambiará más adelante? Dicho de otra manera: cómo asegurarnos de que hemos considerado todos los caminos desde c a u antes de considerar cualquier borde que se origine en u?
Como el gráfico es acíclico, podemos garantizar estocondición encontrando un tipo topológico sobre el gráfico. La ordenación topológica es como una cadena de vértices donde todos los bordes apuntan de izquierda a derecha. Entonces si estamos en vértice vi entonces hemos considerado todos los caminos que conducen a vi y tener el valor final de dist[vi].
La complejidad del tiempo: el tipo topológico toma O(V+E). En el peor de los casos donde z es una hoja y todos los demás vértices apuntan a ella, visitaremos todos los bordes del gráfico que da O(V+E).
0 para la respuesta № 2
Dejar f (u) ser el beneficio máximo que puedes obtener do a tu en tu DAG Entonces quieres calcular f (z). Esto se puede calcular fácilmente en tiempo lineal utilizando programación dinámica / clasificación topológica.
Inicializar f (u) = -infinito por cada tu otro que doy f (c) = 0. Luego, proceda a calcular los valores de F en algún orden topológico de su DAG. Por lo tanto, como el orden es topológico, para cada borde entrante del nodo que se está calculando, se calculan los otros puntos finales, por lo que solo debe elegir el valor máximo posible para este nodo, es decir, f (u) = max (f (v) + costo (v, u)) para cada borde entrante (v, u).
0 para la respuesta № 3
Es mejor usar Clasificación topológica en lugar de Bellman Ford desde su DAG.
Fuente:- http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf
EDITAR:-
G es un DAG con bordes negativos.
Algunos bordes reducen sus ganancias y otros aumentan sus ganancias
- Bordes - aumento de ganancias - valor positivo
- Bordes - disminuir ganancias - valor negativo
Después de TS, para cada vértice U en orden de TS: relaje cada borde saliente.
dist[] = {-INF, -INF, ….}
dist[c] = 0 // source
for every vertex u in topological order
if (u == z) break; // dest vertex
for every adjacent vertex v of u
if (dist[v] < (dist[u] + weight(u, v))) // < for longest path = max profit
dist[v] = dist[u] + weight(u, v)
ans = dist[z];