Per trovare il percorso più lungo in un DAG, sono a conoscenza di 2 algoritmi: algo 1: fai un ordinamento topologico + usa la programmazione dinamica sul risultato del tipo ~ o ~ algo 2: enumera tutto i percorsi nel DAG utilizzando DFS e registra il più lungo. Sembra che enumerare tutti i percorsi con DFS abbia una complessità migliore di algo 1. È vero?Percorso più lungo in un DAG
La seconda opzione non è corretta: DFS non esplora tutti i percorsi possibili, a meno che il grafico non sia un albero o una foresta e inizi dalle radici. Il secondo algoritmo che conosco è negare i pesi e trovare il percorso più breve, ma è leggermente più lento dello top sort + DP algorithm che hai elencato come # 1.
OK, intendevo DFS con riavvio da qualsiasi vertice che non è stato visitato nei precedenti passaggi DFS. Questo esplorerà l'intero DAG. Non dovrebbe essere più veloce di Topo sort + DP? – Frank
@Frank DFS con riavvio dai vertici che non sono stati visitati non esplorerà tutti i percorsi. Si consideri un grafico 'A-> B-> C'; si avvia DFS da B, si passa a C e si arresta; quindi ricomincia da A, vai a B e fermati di nuovo, perché hai già visitato C. Entrambi i percorsi trovati da DFS, 'B-C' e' A-B', sono di lunghezza 1; il percorso più lungo 'A-B-C' è di lunghezza 2. – dasblinkenlight
Perché dovresti iniziare da B? Devi avviare il DFS da fonti. – Frank
enumerare tutti percorsi in un DAG utilizzando "DFS":
def enumerate_dag(g):
def enumerate_r(n, paths, visited, a_path = []):
a_path += [n]
visited[n] = 1
if not g[n]:
paths += [list(a_path)]
else:
for nn in g[n]:
enumerate_r(nn, paths, visited, list(a_path))
paths, N = [], len(g)
visited = np.zeros((N), dtype='int32')
for root in range(N):
if visited[root]: continue
enumerate_r(root, paths, visited, [])
return paths
Hai provato a passare un grafico a doppio diamante a questo codice? Sembra che abbia una probabilità 50/50 di perdere il percorso più lungo. – dasblinkenlight
Ho appena provato con: [[1,2], [3], [3], [4], [5,6], [7], [7], [8], [9], [ ]]. Ottengo 4 percorsi: [[0, 1, 3, 4, 5, 7, 8, 9], [0, 1, 3, 4, 6, 7, 8, 9], [0, 2, 3, 4 , 5, 7, 8, 9], [0, 2, 3, 4, 6, 7, 8, 9]], che credo sia la risposta corretta. Per quanto posso dire (da molti altri test), questo algoritmo enumera correttamente i percorsi in un DAG. Topo sort si basa su un uso molto simile di DFS. A condizione che si avvii/si riavvii da fonti, DFS esplorerà * tutti * i nodi raggiungibili da ciascuna sorgente, quindi il codice sopra * completamente * esplora il DAG, non viene perso alcun vertice. – Frank
Ho frainteso l'uso di 'visited' nel tuo codice: lo hai impostato, ma non lo usi per decidere se continuare l'attraversamento. Questo non è ciò che viene chiamato [DFS] (http://en.wikipedia.org/wiki/Depth-first_search), perché DFS non visita i nodi che sono stati completamente esplorati. La più grande differenza tra DFS e il tuo codice è che il tuo codice è estremamente inefficiente. Prova a ripetere lo stesso modello di diamante cinquanta volte per vedere cosa intendo: il tuo programma esplorerà tutti i percorsi '2^50', e ci sono molti percorsi da esplorare. – dasblinkenlight
No DFS necessaria. Algoritmo: prende un DAG G. Ciascun arco contiene una variabile E
for each node with no predecessor :
for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
for each of his leaving arcs, E=max(E(entering arcs))+1.
max_path è la più alta E entro bordi quando tutti i nodi sono stati elaborati.
Questa è la risposta corretta; vedi https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths –
correlati a [CS.SE]: [Ricerca di percorsi più brevi e più lunghi tra due vertici in un DAG] (http://cs.stackexchange.com/q/11295/11177) – Palec