Liebe einige Hinweise zu diesem Problem:
G ist ein gerichteter azyklischer Graph. Sie möchten von Vertex c zu Vertex z wechseln. Einige Kanten reduzieren Ihren Profit und einige erhöhen Ihren Profit. Wie kommst du von c zu z, während du deinen Profit maximierst? Was ist die zeitliche Komplexität?
Vielen Dank!
Antworten:
1 für die Antwort № 1Das Problem hat eine optimale Unterstruktur. Um den längsten Pfad vom Scheitelpunkt zu finden c zum Scheitelpunkt zmüssen wir zuerst den längsten Weg finden c zu allen Vorgängern von z. Jedes Problem von diesen ist ein anderes kleineres Teilproblem (längster Weg von c zu einem bestimmten Vorgänger).
Lässt die Vorgänger von bezeichnen z wie u1,u2,...,uk und dist[z] der längste Weg von sein c zu z dann dist[z]=max(dist[ui]+w(ui,z))..
Hier ist eine Illustration mit 3 Vorgängern, die die Kantensatzgewichte weglassen:
Also um den längsten Weg zu finden z wir müssen zuerst den längsten Pfad zu seinen Vorgängern finden und das Maximum übernehmen (ihre Werte plus ihre Kantengewichte zu z).
Dies erfordert jedes Mal, wenn wir einen Eckpunkt besuchen u, alle uDie Vorgänger müssen analysiert und berechnet worden sein.
Die Frage ist also: für jeden Eckpunkt u, wie man sicherstellt, dass wir es einmal einstellen dist[u], dist[u] wird später nie geändert werden? Anders ausgedrückt: Wie kann man sicherstellen, dass wir alle Pfade von berücksichtigt haben? c zu u bevor man eine Kante berücksichtigt, die von u?
Da die Grafik azyklisch ist, können wir dies garantierenBedingung, indem eine topologische Sortierung über den Graphen gefunden wird. Die topologische Sortierung ist wie eine Kette von Knoten, bei der alle Kanten von links nach rechts zeigen. Also wenn wir uns in der Ecke befinden vi dann haben wir alle Wege berücksichtigt, die zu vi und haben den Endwert von dist[vi].
Die zeitliche Komplexität: topologische Sortierung braucht O(V+E). Im schlimmsten Fall wo z ist ein Blatt und alle anderen Ecken weisen darauf hin, wir werden alle Graphenränder besuchen, die geben O(V+E).
0 für die Antwort № 2
Lassen f (u) sei der maximale Profit, von dem du ausgehen kannst c zu u in deiner DAG. Dann willst du rechnen f (z). Dies kann leicht in linearer Zeit mittels dynamischer Programmierung / topologischer Sortierung berechnet werden.
Initialisieren f (u) = -Unendlichkeit für jeden u außer c, und f (c) = 0. Fahren Sie dann mit der Berechnung der Werte von f in einer topologischen Reihenfolge Ihrer DAG. Da die Reihenfolge topologisch ist, werden somit für jede ankommende Kante des Knotens, der berechnet wird, die anderen Endpunkte berechnet, also wählen Sie einfach den maximal möglichen Wert für diesen Knoten, d. f (u) = max (f (v) + Kosten (v, u)) für jede eingehende Kante (v, du).
0 für die Antwort № 3
Es ist besser zu benutzen Topologische Sortierung Anstatt von Bellman Ford seit seiner DAG.
Quelle:- http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf
BEARBEITEN:-
G ist ein DAG mit negativen Kanten.
Einige Kanten reduzieren Ihren Profit und einige erhöhen Ihren Profit
- Kanten - Gewinn steigern - positiver Wert
- Kanten - Gewinn verringern - negativer Wert
Nach TS, für jeden Eckpunkt U in TS-Reihenfolge - jede ausgehende Kante entspannen.
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];