Sto facendo un ottimizzatore di layout grafico e ho bisogno di trovare percorsi dal nodo a al nodo b nel grafico g. È andato abbastanza bene finora, ma mi manca un algoritmo per fare il passo successivo.
Finora ho usato BFS per trovare il percorso migliore da a a b. Il prossimo passo sarebbe trovare tutti i percorsi da A a B, senza loop. D: Quali algoritmi possono farlo? Interessanti algoritmi CPU o GPU.
Ora per la parte difficile; prestazione. Il numero di nodi arriva fino a ~ 1000 e ciascuno si connette a ~ 10 altri nodi. Il numero di nodi in qualsiasi percorso è spesso 4-5 nodi per il percorso migliore e ~ 15 per un percorso errato. L'ottimizzatore viene utilizzato in un editor e quindi dovrebbe completare un layout in meno di un secondo. A causa di come funziona l'ottimizzatore (BFS applicato su un grafico implicitamente rappresentato), possiamo assumere che l'algoritmo sia esercitato forse 10-100 volte in un singolo passaggio. Fondamentalmente, deve essere trovato in meno di 10ms dato quei numeri. La piattaforma è un desktop di fascia alta con una quantità di memoria tale.
Non tutti i percorsi devono essere trovati immediatamente, e in effetti sono necessari pochissimi. Il risultato potrebbe anche essere una tupla del (n) percorso migliore, e lo script che genera il (n + 1) percorso migliore, dove (n) raramente supererà 10 poiché l'ottimizzatore ha molto probabilmente trovato una soluzione ottimale prima di ciò. Lo script verrà quindi valutato solo se l'ottimizzatore non ha trovato una soluzione con un costo inferiore a quella del percorso (n).