Percorso ponderato massimo tra due vertici in un grafico aciclico diretto - algoritmo, grafico, teoria dei grafi, grafi diretti-aciclici

Adoro alcune indicazioni su questo problema:

G è un grafico aciclico diretto. Vuoi passare dal vertice c al vertice z. Alcuni bordi riducono il tuo profitto e alcuni aumentano il tuo profitto. Come si ottiene da c a z massimizzando il profitto. Qual è la complessità del tempo?

Grazie!

risposte:

1 per risposta № 1

Il problema ha una sottostruttura ottimale. Per trovare il percorso più lungo dal vertice c al vertice z, per prima cosa dobbiamo trovare il percorso più lungo da c a tutti i predecessori di z. Ogni problema è un altro sottoproblema più piccolo (il percorso più lungo da c a un predecessore specifico).

Denotiamo i predecessori di z come u1,u2,...,uk e dist[z] essere il percorso più lungo da c a z poi dist[z]=max(dist[ui]+w(ui,z))..

Ecco un'illustrazione con 3 predecessori che omettono i pesi impostati sugli spigoli:

Quindi, per trovare il percorso più lungo per z per prima cosa dobbiamo trovare il percorso più lungo per i suoi predecessori e prendere il massimo (i loro valori più i loro contorni a z).

Ciò richiede ogni volta che visitiamo un vertice u, tutto di u"I predecessori devono essere stati analizzati e calcolati.

Quindi la domanda è: per qualsiasi vertice u, come assicurarsi che una volta impostato dist[u], dist[u] non sarà mai cambiato in seguito? Mettilo in un altro modo: come assicurarsi di aver considerato tutti i percorsi da c a u prima di considerare qualsiasi bordo originato da u?

Poiché il grafico è aciclico, possiamo garantirlocondizione trovando un ordinamento topologico sul grafico. l'ordinamento topologico è come una catena di vertici in cui tutti gli archi puntano da sinistra a destra. Quindi se siamo al vertice vi quindi abbiamo considerato tutti i percorsi che portano a vi e hanno il valore finale di dist[vi].

La complessità del tempo: l'ordinamento topologico richiede O(V+E). Nel peggiore dei casi dove z è una foglia e tutti gli altri vertici puntano ad essa, visiteremo tutti i bordi del grafico che dà O(V+E).

---

0 per risposta № 2

Permettere f (u) sii il massimo profitto che puoi ottenere c a u nel tuo DAG. Quindi vuoi calcolare f (z). Questo può essere facilmente calcolato in tempo lineare usando la programmazione dinamica / l'ordinamento topologico.

Inizializzare f (u) = -infinità per ogni u diverso da c, e f (c) = 0. Quindi, continua a calcolare i valori di f in qualche ordine topologico del tuo DAG. Quindi, dato che l'ordine è topologico, per ogni fronte in ingresso del nodo che viene calcolato, vengono calcolati gli altri endpoint, quindi basta selezionare il valore massimo possibile per questo nodo, ad es. f (u) = max (f (v) + costo (v, u)) per ciascun bordo in entrata (v, u).

---

0 per risposta № 3

È meglio usare Ordinamento topologico invece di Bellman Ford dal suo DAG.

Fonte:- http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

MODIFICARE:-

G è un DAG con bordi negativi.

Alcuni bordi riducono il tuo profitto e alcuni aumentano il tuo profitto

• Bordi - aumentare il profitto - valore positivo
• Bordi - diminuire il profitto - valore negativo

Dopo TS, per ogni vertice U nell'ordine TS - rilassare ogni margine in uscita.

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];

---