Come calcolare il percorso critico di un grafico aciclico direzionale?

Question

Qual è il modo migliore (per quanto riguarda le prestazioni) di calcolare il percorso critico di un grafico aciclico direzionale quando i nodi del grafico hanno peso?

Ad esempio, se ho la seguente struttura:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

Il percorso critico dovrebbe essere A - > B - > F (peso totale: 10)

Answer 1

Non ho idea di " percorsi critici " ;, ma suppongo che intendi questo .

Trovare il percorso più lungo in un grafico aciclico con pesi è possibile solo attraversando l'intero albero e quindi confrontando le lunghezze, poiché non si sa mai veramente come viene ponderato il resto dell'albero. Puoi trovare ulteriori informazioni sull'attraversamento degli alberi in Wikipedia . Ti suggerisco di procedere con il pre-ordine di attraversamento, poiché è facile e diretto da implementare.

Se hai intenzione di interrogare spesso, potresti anche voler aumentare i bordi tra i nodi con informazioni sul peso dei loro sottoalberi al momento dell'inserimento. Questo è relativamente economico, mentre la ripetuta traversata può essere estremamente costosa.

Ma non c'è nulla che ti salvi davvero da un attraversamento completo se non lo fai. L'ordine non ha molta importanza, purché tu faccia un attraversamento e non segua mai lo stesso percorso due volte.

Answer 2

Lo risolverei con una programmazione dinamica. Per trovare il costo massimo da S a T:

• Ordina topologicamente i nodi del grafico come S = x_0, x_1, ..., x_n = T. (Ignora tutti i nodi che possono raggiungere S o essere raggiunti da T.)
• Il costo massimo da S a S è il peso di S.
• Supponendo che tu abbia calcolato il costo massimo da S a x_i per tutti i < k, il costo massimo da S a x_k è il costo di x_k più il costo massimo per qualsiasi nodo con un bordo a x_k.

Answer 3

C'è un documento che pretende di avere un algoritmo per questo: " Percorso critico in una rete di attività con vincoli temporali " ;. Purtroppo, non sono riuscito a trovare un collegamento a una copia gratuita. A parte questo, posso solo secondare l'idea di modificare http://en.wikipedia.org/ wiki / Dijkstra% 27s_algorithm o http://en.wikipedia.org/wiki/A *

AGGIORNAMENTO: mi scuso per la formattazione scadente & # 8212; il motore di markdown sul lato server è apparentemente rotto.

Answer 4

La mia prima risposta, quindi mi scuso per qualsiasi cosa non standard dalla cultura dello stackoverflow.

Penso che la soluzione sia semplice. Basta negare i pesi ed eseguire il percorso più corto classico per DAG (modificato ovviamente per i pesi dei vertici). Dovrebbe funzionare abbastanza velocemente. (Forse la complessità temporale di O (V + E))

Penso che dovrebbe funzionare come quando negherai i pesi, il più grande diventerà il più piccolo, il secondo più grande sarà il secondo più piccolo e così via come se a > b quindi -a < -b. Quindi eseguire DAG dovrebbe essere sufficiente in quanto troverà la soluzione per il percorso più piccolo di quello negato e quindi trovare il percorso più lungo per quello originale

Answer 5

Prova il metodo A *.

A * Algoritmo di ricerca

Alla fine, per gestire le foglie, fai in modo che tutte conducano ad un punto finale, da stabilire come obiettivo.