11
In termini di tempo di esecuzione, qual è l'algoritmo di chiusura transitoria più noto per i grafici diretti?Algoritmo di chiusura transitoria più noto per il grafico
Attualmente sto usando l'algoritmo di Warshall ma è O (n^3). Sebbene, a causa della rappresentazione grafica, la mia implementazione è leggermente migliore (invece di controllare tutti i bordi, controlla solo i bordi in uscita). Esiste un algoritmo di chiusura transitiva che è migliore di questo? In particolare, c'è qualcosa di specifico per le architetture multi-threaded di memoria condivisa?
Grazie in anticipo.
Raghava.
Grazie per la risposta. Immagino che l'accelerazione euristica sarebbe utile solo se ci sono molti componenti fortemente connessi nel grafico. Ho bisogno di osservare i grafici generati da diversi set di dati per vedere se questo è il caso. Ma se questo non è il caso, allora quello di Warshall è il migliore, no? Pensavo ci potesse essere dell'altro. – Raghava
Penso che l'approccio menzionato nel primo punto elenco del primo collegamento sia la strada da seguire. Sarà anche relativamente facile parallelizzare! –
@ Tom: A partire da ora, sto già utilizzando una libreria di grafi multi-thread. Quindi sto usando la loro rappresentazione grafica che non è una matrice. – Raghava